1.1. NONNEGATIVE MATRICES 3 Example 1.3. Let n = 3. What arrangement of 1, 2, 3,..., 9 into a 3×3 matrix gives the largest λmax? Some possibilities are 9 8 5 7 6 3 4 2 1 with λmax = 16.7409, and 9 8 5 7 6 2 4 3 1 with λmax = 16.74511. Notice how the interchange of 2 and 3 in the first matrix gives a larger λmax in the second matrix. Thus, not surprisingly, λmax is sensitive to small perturbations in the positions of the entries. In fact, the arrangement that gives the largest λmax is 9 8 4 7 6 3 5 2 1 with λmax = 16.7750. The arrangement of 1, 2, 3,...,n2 into an n × n matrix that gives the largest λmax is unknown in general—probably there is no general descrip- tion of a pattern that gives the maximum—but there is a 1964 theorem of Schwarz [7] which considerably reduces the number of patterns that needs to be considered. It holds for any sequence of n2 nonnegative numbers. Theorem 1.4. 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 each column: ai1 ai2 · · · ain (1 i n),a1j a2j · · · anj (1 j n). There may be matrices with the largest λmax that do not satisfy the monotone property stated in the theorem. Example 1.5. All of the matrices 1 1 1 1 1 1 1 0 0 , 1 1 1 1 1 0 1 0 1 , 1 1 1 1 0 1 1 1 0 have the largest λmax, namely 1 + 2, for the sequence 0, 0, 1, 1, 1, 1, 1, 1, 1. How does one prove such a theorem as Theorem 1.4 in which we have to compare λmax’s without knowing their values? There is a well-developed theory of nonnegative matrices going back to O. Perron and G. Frobenius (with additional contributions of H. Wielandt)— usually called the Perron-Frobenius theory of nonnegative matrices—that provides powerful techniques for such comparisons. Since eigenvalues and, in particular, the spectral radius, depend continuously on the entries of a matrix, any 0s among the numbers ci can be replaced by a small positive number , and thus we can assume that c1,c2,c3,...,cn2 are all positive. This allows us to avoid questions of reducibility (which we will address later) and to use the strongest possible theorems.
Previous Page Next Page