1.2. SYMMETRIC MATRICES 7 In [7], motivated by Theorem 1.4 the following fascinating question was considered. We continue with the notation used in the proof of Theorem 1.4. Question: Let c1,c2,c3,...,cn2 be n2 distinct nonnegative numbers ar- ranged so that 0 ≤ c1 c2 c3 · · · cn2. Let An (≥) be the subset of An consisting of those matrices in which the entries in each row and in each column are decreasing, and let An max(≥) = Amax n ∩ An (≥) . By Theorem 1.4, An max(≥) = ∅. Similarly, let Nn (≥) be the set of all matrices whose entries are 1, 2, 3,...,n2 with the entries in each row and each column decreasing. A matrix A in An belongs to An (≥) if and only if the matrix g(A) obtained from A by replacing each ci with i belongs to Nn (≥) . Determine the range of the function (1.1) g : An max(≥) → Nn≥),( over all possible 0 ≤ c1 c2 c3 · · · c n2 . First let n = 2. Then N (≥) 2 consists only of 4 3 2 1 and its transpose. Thus the function (1.1) is onto. Now let n = 3. Then N (≥) 3 consists of 21 matrices and their transposes. As shown in [7], the range of (1.1) consists only of the three matrices ⎡ ⎣ 9 8 5 7 4 3 6 2 1 ⎤ ⎦ , ⎡ ⎣ 9 8 4 7 6 3 5 2 1 ⎤ ⎦ , ⎡ ⎣ 9 8 4 7 5 3 6 2 1 ⎤ ⎦ , and their transposes. Thus for n = 3, we have a test set of size 3 to deter- mine the biggest λmax. For the smallest λmax, a test set of 13 matrices is determined in [7], but it is not shown that this test set is minimal. In case c1,c2,...,cn2 only contains 0s and 1s, say e 1s and n2−e 0s, then the matrices in An are the biadjacency matrices of bipartite graphs with 2n vertices and e edges (equivalently, adjacency matrices of digraphs with n vertices and e edges some of which may be loops). Friedland [5] determined those (0, 1)-matrices with e 1s (digraphs with e edges) with the largest λmax for several classes of values of e. For a summary of these and other results, see [2]. 1.2. Symmetric Matrices We begin this section by reviewing some of the basic facts about real symmetric matrices. Let A = [aij] be an n × n real symmetric matrix.

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.