Multi-Page Printing

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 −1 AP ∈ 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 −1 AP ∈ 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.