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

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.