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.
Previous Page Next Page