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.