1.1. NONNEGATIVE MATRICES 3
Example 1.3. Let n = 3. What arrangement of 1, 2, 3,..., 9 into a 3×3
matrix gives the largest λmax? Some possibilities are


9 8 5
7 6 3
4 2 1


with λmax = 16.7409, and


9 8 5
7 6 2
4 3 1


with λmax = 16.74511.
Notice how the interchange of 2 and 3 in the first matrix gives a larger
λmax in the second matrix. Thus, not surprisingly, λmax is sensitive to small
perturbations in the positions of the entries. In fact, the arrangement that
gives the largest λmax is


9 8 4
7 6 3
5 2 1


with λmax = 16.7750.
The arrangement of 1, 2,
3,...,n2
into an n × n matrix that gives the
largest λmax is unknown in general—probably there is no general descrip-
tion of a pattern that gives the maximum—but there is a 1964 theorem of
Schwarz [7] which considerably reduces the number of patterns that needs
to be considered. It holds for any sequence of
n2
nonnegative numbers.
Theorem 1.4. Let n be a positive integer and let c1,c2,c3,...,cn2 be
a sequence of nonnegative real numbers. Then an arrangement of these
numbers into an n × n matrix with the largest λmax can be found among
those matrices A = [aij] which are monotone nonincreasing in each row and
each column:
ai1 ai2 · · · ain (1 i n),a1j a2j · · · anj (1 j n).
There may be matrices with the largest λmax that do not satisfy the
monotone property stated in the theorem.
Example 1.5. All of the matrices


1 1 1
1 1 1
1 0 0


,


1 1 1
1 1 0
1 0 1


,


1 1 1
1 0 1
1 1 0


have the largest λmax, namely 1 +

2, for the sequence 0, 0, 1, 1, 1, 1, 1, 1, 1.
How does one prove such a theorem as Theorem 1.4 in which we have
to compare λmax’s without knowing their values?
There is a well-developed theory of nonnegative matrices going back to
O. Perron and G. Frobenius (with additional contributions of H. Wielandt)—
usually called the Perron-Frobenius theory of nonnegative matrices—that
provides powerful techniques for such comparisons. Since eigenvalues and,
in particular, the spectral radius, depend continuously on the entries of a
matrix, any 0s among the numbers ci can be replaced by a small positive
number , and thus we can assume that c1,c2,c3,...,cn2 are all positive.
This allows us to avoid questions of reducibility (which we will address later)
and to use the strongest possible theorems.
Previous Page Next Page