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.
