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
Previous Page Next Page