Math 621: Matrix Theory 1

From MathWiki
Revision as of 16:43, 3 April 2013 by Ls5 (Talk | contribs) (moved Math 621 to Math 621: Matrix Theory 1)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Catalog Information


Matrix Theory 1.

Credit Hours



Math 570.


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

Additional topics

Courses for which this course is prerequisite

Math 622