Multi-Page Printing

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.