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(≥)

=

An

max

∩

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 · · · cn2 .

First let n = 2. Then

N2≥) (

consists only of

4 3

2 1

and its transpose. Thus the function (1.1) is onto.

Now let n = 3. Then

N3≥) (

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.