You are here

Eigenvalues, Multiplicities and Graphs

Charles R. Johnson and Carlos M. Saiago
Cambridge University Press
Publication Date: 
Number of Pages: 
Cambridge Tracts in Mathematics 211
[Reviewed by
Miklós Bóna
, on

The title should be more precise. The current title allows the reader to think that this will be a book on spectral graph theory, that is, a field that studies graphs, with matrices and their spectra serving as tools. This book does the opposite. The subject is matrices, their eigenvalues, and the multiplicities of those eigenvalues. Graphs are only a tool; their role is simply to describe the arrangement of the nonzero entries of a square matrix. The graph that does that is called the graph of the matrix.

The book is a research monograph. The authors focus on symmetric matrices with real entries, and on complex Hermitian matrices. For such matrices, the notions of geometric and algebraic eigenvalues coincide.

It has long been known that the theory of graphs of matrices is richest when those graphs are trees, and therefore, most of the book covers such cases. For instance, we see results on the minimum number of distinct eigenvalues for a symmetric matrix whose graph is a tree, on how to construct the multiplicities that do occur, and on multiplicity lists that belong to specific trees. The book ends with an appendix that consist of the multiplicity lists that belong to all trees on less than 12 vertices.

There are no exercises of any kind, nor are there lists of open problems. While the book is admittedly a research monograph, this still leaves a feeling of incompleteness. The reader can learn a lot of facts from the book, but what next?

Miklós Bóna is Professor of Mathematics at the University of Florida.

1. Introduction
2. Parter-Wiener, etc. theory
3. Maximum multiplicity for trees, I
4. Multiple eigenvalues and structure
5. Maximum multiplicity, II
6. The minimum number of distinct eigenvalues
7. Construction techniques
8. Multiplicity lists for generalized stars
9. Double generalized stars
10. Linear trees
11. Non-trees
12. Geometric multiplicities for general matrices over a field.