CHAPTER 1
Some Fundamentals
In this chapter, motivated by a natural problem, we introduce some of
the fundamental concepts and ideas of nonnegative and symmetric matrices
that we shall use throughout this book.
1.1. Nonnegative Matrices
We begin with a motivating problem:
Let n be a positive integer and consider the numbers 1, 2,
3,...,n2.
How
should these numbers be arranged in an n × n matrix to give the largest
spectral radius? Equivalently, how should the edges of the complete bipar-
tite graph Kn,n be given the weights 1,
2,...,n2
in order that its (weighted)
biadjacency matrix has the largest spectral radius?
Note that in this question we are not asking for the largest spectral
radius—although that would certainly be of interest if it could be writ-
ten down—but only the pattern of the numbers that achieves the maxi-
mum spectral radius. Thus the question is a combinatorial question—the
pattern—about a linear algebraic concept—the spectral radius.
Before proceeding with this question, we explain some of the terms used.
If A is an n × n complex matrix, then A has n eigenvalues λ1,λ2,...,λn.
The spectral radius of A is
ρ(A) = max{|λ1|, |λ2|,..., |λn|},
the maximum modulus of the eigenvalues of A. A bipartite graph is a graph
whose vertices can be bipartitioned (partitioned into two sets) so that each
edge joins a vertex in one set and a vertex in another set. The bipartite
graph is complete provided it contains all possible edges between the two
parts of the bipartition; if the two parts have m and n vertices, respectively,
we get the complete bipartite graph Km,n. We usually think of and draw
a bipartite graph with one set of vertices in a vertical line on the left (the
left vertices) and the other set of vertices in a vertical line on the right (the
right vertices).
Example 1.1. A bipartite graph G K3,4 with 3 left vertices and 4
right vertices is shown in Fig. 1.1.
1
http://dx.doi.org/10.1090/cbms/115/01
Previous Page Next Page