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 An

max

be the subset of An consisting of those matrices

with ρ as an eigenvalue. Finally, let A = [aij] be a matrix in An

max,

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 An

max.

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 ∈ An

max

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