Nathan Reff (Binghamton)

Combinatorial Matrix Theory

Abstract for the Combinatorics Seminar
2010 April 20

The Study of algebraic properties of matrices associated to graphs (such as, for example, the Laplacian) poses many challenging questions. For example, it is very difficult to precisely determine the eigenvalues of a graphical matrix using purely combinatorial arguments.
An "inclusion region" for eigenvalues refers to a region in the complex plane guaranteed to contain the set of eigenvalues for a given matrix. These inclusion regions can be used to produce bounds on the eigenvalues of graphical matrices. Several classical theorems, such as Gershgorin's theorem, the Brauer ovals of Cassini, the Courant-Fischer-Weyl theorem (min-max theorem) and field of values, determine such regions.
In this talk I will cover these theorems and will include many basic examples where these may be useful as well as combinatorial examples from spectral graph theory.


To the Combinatorics Seminar Web page.