10 1. SOME FUNDAMENTALS

There is an analogue of Theorem 1.4 for symmetric, nonnegative matri-

ces with 0s on the main diagonal due to Brualdi and Hoffman [3], and we

discuss it now.

Let n ≥ 2 be an integer and let c1,c2,...,c(n)

2

be nonnegative numbers.

Let Sn be the set of all n×n symmetric matrices with 0s on the main diagonal

whose entries above the main diagonal are the numbers c1,c2,...,c(n).

2

Let

Sn≥) (

be the subset of Sn consisting of those matrices A = [aij] such that

whenever i j, then akl ≥ aij for all k l with k ≤ i and l ≤ j; equivalently,

the entries in each row and column above the main diagonal are monotone

nonincreasing.

The following theorem is a strong symmetric analogue of Theorem 1.4.

Theorem 1.9. If A is a matrix in Sn with the largest λmax, then there

is an n × n permutation matrix P such that P

−1AP

∈

Sn≥).(

Proof. Let ρ be the largest λmax attainable by a matrix in Sn, and let

A = [aij] be a matrix in Sn with λmax = ρ. Since A is a nonnegative matrix,

there exists a nonnegative eigenvector x =

(x1,x2,...,xn)t

of A for its

eigenvalue ρ where

xtx

= 1. Since P

−1AP

∈ Sn for every A ∈ Sn and every

n × n permutation matrix P , we may assume that x1 ≥ x2 ≥ · · · ≥ xn ≥ 0.

First suppose that there exists p and q with p q such that ap,q+1 apq. Let

B be the matrix in Sn obtained by switching apq and ap,q+1, and switching

aqp and aq+1,p. Then

xtBx

− ρ =

xtBx

−

xtAx

= 2(ap,q+1 − apq)xp(xq − xq+1) ≥ 0.

Hence by S2, λmax(B) ≥ ρ with strict inequality if xp(xq − xq+1) = 0. Thus

xp = 0 or xq = xq+1. To complete the proof, we show that each of these

possibilities leads to a contradiction.

Suppose that xp 0. Then xq = xq+1 and

xtBx

= ρ, so that Bx = ρx.

On the other hand, the qth component of Bx and that of Ax differ by

(ap,q+1 − apq)xp 0, a contradiction. Thus xp = 0, and for some s ≤ p − 1,

xs 0 = xs+1 = · · · = xn = 0. Therefore, ρ = λmax(A[1, 2,...,s]). If

there were an off-diagonal 0 in A[1, 2,...,s], then since (x1,x2,...,xs) is

a positive vector, we could move ap,q+1 to its position (and move aq+1,p

to the symmetrically opposite position) and, by S2, increase the λmax, a

contradiction. Thus A[1, 2,...,s] contains only positive entries off the main

diagonal and thus is irreducible. An (s + 1) × (s + 1) matrix B defined by

B =

A[1, 2,...,s] z

zt

0

,

where z has a positive entry followed by all 0s, is irreducible and by PF6

for irreducible matrices, satisfies λmax(B) λmax(A[1, 2,...,s]) = ρ. Since

ap,q+1 is positive, there is a matrix B in Sn containing B as a principal

submatrix; hence by S5, λmax(B ) ρ, another contradiction.

In a similar way we can get a contradiction if there are integers p and q

with p + 1 q and ap+1,q apq.