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


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.
Previous Page Next Page