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 −1 AP 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.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2011 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.