Math 621: Matrix Theory 1
Matrix Theory 1.
Symmetric matrices, spectral graph theory, interlacing, the Laplacian matrix of a graph.
Desired Learning Outcomes
Minimal learning outcomes
1. Students will learn simple relations between properties of an undirected graph and the eigenvalues of its adjacency matrix (called the spectrum of the graph).
2. Students will know the spectra of several simple classes of graphs: complete graphs, paths, cycles, stars, etc.
3. Students will be able to apply the theory of nonnegative matrices to spectral graph theory.
4. Students will know the characterization of a bipartite graph in terms of its graph spectrum.
5. Students will learn how graph parameters such as the clique number and chromatic number can be estimated by means of the spectrum of the graph.
6. Students will know the basic properties of the Laplacian matrix of a graph.
7. Students will understand the proof of the matrix tree theorem, know two forms of the theorem, and how to apply it.
8. Students will learn some of the deeper relationships between the Laplacian matrix and structural properties of a graph.
Possible textbooks for this course include (but are not limited to):
Richard A Brualdi and Herbert J Ryser, Combinatorial Matrix Theory
Dragos Cvetkovic, Peter Rowlinson, and Slobodan Simic, An Introduction to the Theory of Graph Spectra
Chris Godsil and Gordon Royle, Algebraic Graph Theory
Courses for which this course is prerequisite