6 1. SOME FUNDAMENTALS
of A continue to be monotone nonincreasing, after rearranging the entries
in each column of A to be monotone nonincreasing.
Example 1.6. Let n = 3 and consider the nine numbers 1, 1, 1, 1, 2, 2, 2, 2, 2.
Then, using Theorem 1.4 and the fact that a matrix and its transpose have
the same λmax, we see that one of the following matrices attains the smallest
λmax among all the 3 × 3 matrices whose entries are four 1s and five 2s:
A1 =
⎡
⎣
2 2 2
2 2 1
1 1 1
⎤
⎦
, A2 =
⎡
⎣
2 2 2
2 1 1
2 1 1
⎤
⎦
,
In fact,
λmax(A1) = 4.7913 4.8284 = λmax(A2).
In a similar way one can prove the following theorem.
Theorem 1.7. Let n be a positive integer and let c1,c2,c3,...,cn2 be
a sequence of nonnegative real numbers. Then an arrangement of these
numbers into an n × n matrix with the largest λmax can be found among
those matrices A = [aij] which are monotone nonincreasing in each row and
monotone nondecreasing in each column:
ai1 ≥ ai2 ≥ · · · ≥ ain (1 ≤ i ≤ n),a1j ≤ a2j ≤ · · · ≤ anj (1 ≤ j ≤ n).
For later reference we remark that the properties PF1 to PF7 hold for
all square, irreducible nonnegative matrices. Here a matrix A is reducible
provided there exists a permutation matrix P such that
P
−1AP
=
A1 Or,n−r
A21 A2
for some integer r with 0 r n, and is irreducible otherwise. If A is
reducible, then the eigenvalues of A are those of A1 taken together with
those of A2, and λmax(A) = max{λmax(A1),λmax(A2)}. If A is reducible,
then λmax is a nonnegative (not necessarily positive) eigenvalue of A with
a nonnegative (not necessarily positive) eigenvector, but λmax may not be
a simple eigenvalue since it may be an eigenvalue of both A1 and A2. In
general, if X is an n × n matrix, there exists a permutation matrix Q such
that we get the triangular block form
Q−1XQ
=
⎡
⎢
⎢
⎢
⎢
⎢
⎣
X1 O O · · · O
X21 X2 O · · · O
X31 X32 X3 · · · O
.
.
.
.
.
.
.
.
.
...
.
.
.
Xs1 Xs2 Xs3 · · · Xs
⎤
⎥
⎥
⎥
⎥
⎥
⎦
where s is a positive integer and X1,X2,...,Xs are irreducible square ma-
trices. The matrices X1,X2,...,Xs are the irreducible components of X and
they are uniquely determined up to simultaneous permutations of their rows
and columns.
