2 1. SOME FUNDAMENTALS

Figure 1.1

Taking the left vertices in order from top to bottom and also the right

vertices from top to bottom, the biadjacency matrix is the 3×4 (0,1)-matrix

⎡

⎣

1 1 1 0

1 0 0 1

0 1 0 1

⎤

⎦

.

Here the rows correspond to the left vertices and the columns correspond

to the right vertices. A entry equal to 1 indicates the presence of an edge

between a left vertex and a right vertex; an entry equal to 0 indicates the

absence of such an edge. If the edges are weighted, then in place of the

1s we use the corresponding weights. (One could then think of the 0s as

corresponding to edges of weight 0.)

The entries of the matrices in our problem are all positive. Hence the

theory of positive matrices, more generally the theory of nonnegative ma-

trices, applies. This theory tells us that all the matrices considered in the

problem have a positive real eigenvalue equal to its spectral radius, which we

denote by λmax (λmax(A) if we need to refer to a specific matrix A without

ambiguity). Thus we seek a pattern with the largest λmax.

Example 1.2. Let n = 2 so that we want the pattern of 1, 2, 3, 4 in a

2 × 2 matrix that gives the largest spectral radius. It is easy to check that

this largest spectral radius is attained by the matrix

4 3

2 1

,

whose eigenvalues are

5±

√

35

2

. Thus we can say that λmax =

5+

√

35

2

= 5.3723.

In general, there are

(n2)!

possible arrangements of 1, 2,

3,...,n2

into an

n × n matrix. Some of these matrices will be permutation similar, that is,

obtained from one another by simultaneous row and column permutations,

and so related as in B = P

−1AP

where P is a permutation matrix; others

will be transposes of one another, and thus will have the same eigenvalues

and so the same spectral radius. This reduces

(n2)!

to

(n2)!

2n!

, still a very large

number.