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 −1 AP = 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.

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.