You are here

The Mutually Beneficial Relationship of Graphs and Matrices

Richard A. Brualdi
American Mathematical Society
Publication Date: 
Number of Pages: 
BLL Rating: 

The Basic Library List Committee suggests that undergraduate mathematics libraries consider this book for acquisition.

[Reviewed by
Russell Jay Hendel
, on

This is a delightful short book which could be used as a supplemental course book in an upper level undergraduate course or first year graduate course in graph theory. The book could also be used to provide a short (say 2 week) supplemental module in a standard undergraduate linear algebra course. Although the book has no homework problems, its contents are beautiful, current, relevant, accessible to undergraduates, and have the potential to entice the audience to want to learn more.

The book contains 10 chapters, each of which shows how certain properties of graphs are associated with matrices and how certain algebraic properties of matrices shed light on graphical properties. The table of contents gives a good sense of what is included.

Although the author believes his book primarily relevant for research mathematicians and graduate students, I disagree. It would also be relevant in a standard undergraduate course. By analogy with calculus, the modern textbook approach is to present multiple applications when teaching standard courses. Multiple applications should be presented in Linear Algebra also! In linear algebra, Anton’s and Rorres’ Applications of Linear Algebra comes to mind, a book with about two dozen chapters, each showing some unexpected applications of solving linear systems — for example, three dimensional viewing or touching up photographs. Many of the applications in this classic work of Anton are now found in the “Applications Version” of Anton’s linear algebra book. Brualdi’s book goes a step further than Anton, since the linear algebra applications are not applications of solving linear systems but new interpretations of the matrix concept — the matrix is no longer the coefficients of a linear system “without the variables,” it has a life of its own.

My reasons for advocating using this book as a second text in a senior or first year graduate graph theory course is twofold. First, the book illustrates how mathematically defined objects — in this case matrices — acquire a life of their own and find applicability in unforeseen ways: the matrix is defined as an abstraction to deal with linear systems and yet it mysteriously can completely describe a graph. Second, the book also illustrates a modern concept we would like all undergraduates to learn: that mathematics frequently progresses by two disparate disciplines — in this case matrix theory and graph theory — joining together.

Russell Jay Hendel, RHendel@Towson.Edu, holds a Ph.D. in theoretical mathematics and an Associateship from the Society of Actuaries. He teaches at Towson University. His interests include discrete number theory, applications of technology to education, problem writing, actuarial science and the interaction between mathematics, art and poetry.

  • Some fundamentals
  • Eigenvalues of graphs
  • Rado-Hall theorem and applications
  • Colin de Verdière number
  • Classes of matrices of zeros and ones
  • Matrix sign patterns
  • Eigenvalue inclusion and diagonal products
  • Tournaments
  • Two matrix polytopes
  • Digraphs and eigenvalues of (0,1)-matrices
  • Index