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