1.1. NONNEGATIVE MATRICES 5 Then n i=1 (μi − λmax)xiyi = n i=1 (μiyi)xi − n i=1 (λmaxxi)yi = n i=1 ⎛ ⎝ n j=1 aijyj⎠ ⎞ xi − n i=1 ⎛ ⎝ n j=1 xjaji⎠ ⎞ yi = n i=1 n j=1 (aijxiyj − ajixjyi) = 0. Now xiyi 0 for i = 1, 2,...,n. Thus if all the μi are equal to the same number μ, that is, y is a positive eigenvector of A with eigenvalue μ, then, since by the above n i=1 (μ − λmax)xiyi = 0, we have μ = λmax. Thus PF3 holds. If not all the μi are equal, then ∑ n i=1 (μi − λmax)xiyi = 0 implies that min{μi : 1 ≤ i ≤ n} λmax max{μi : 1 ≤ i ≤ n}, from which we get PF4 and PF5. PF6 now follows from PF5. PF7 follows from PF5 and PF6 by taking y to be the vector jn of n 1s. We are now in a position to prove Theorem 1.4. Proof. Let An be the set of all n × n matrices whose n2 entries are the numbers c1,c2,c3,...,cn2. Let ρ be the largest λmax attainable by a matrix in An. Let Amax n be the subset of An consisting of those matrices with ρ as an eigenvalue. Finally, let A = [aij] be a matrix in Amax, n and let x = (x1,x2,...,xn)t be a positive vector such that Ax = ρx. After simultaneous permutations of rows and columns, we may assume that x1 ≥ x2 ≥ · · · ≥ xn 0. Suppose we interchange two consecutive entries in some row of A, say we interchange akl and ak,l+1 to get a matrix B ∈ An. Then Bx − ρx = Bx − Ax = z, where z has only one possible nonzero entry, namely the entry (ak,l+1 − akl)(xl − xl+1) in the kth position. If xl = xl+1, then Bx = ρx. Thus B is also in Amax. n Now suppose that xl xl+1 and ak,l+1 akl. Then the only nonzero entry of z is positive, and hence Bx ≥ ρx but Bx = ρx. By PF4, λmax(B) ρ, a contradiction. Thus, if xl xl+1, we must have akl ≥ ak,l+1. Since k and l were arbitrary, we now conclude that there is a matrix A ∈ Amax n obtained from A by rearranging the entries in each row, such that the entries in each row are monotone non- increasing. Repeating the above argument on (A )t, we conclude that there is a matrix A ∈ An max obtained from A by rearranging the entries in each column, such that the entries in each column are monotone nonincreasing. The proof is completed by noting (an exercise) that the entries in each row

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2011 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.