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.