Perhaps the most powerful of the many connections between graphs and matrices is the Laplacian matrix of a graph. The definition is easy -- start with an undirected graph, put the vertex degrees on the diagonal, and put -1 in each off-diagonal position where there's an edge. The consequences are profound, ranging from data mining and analysis (spectral clustering, Fourier analysis of graphs), to parallel computing (spectral partitioning), to graph algorithms (flows in networks), to topological graph theory (the planar separator theorem), to applications in ecology (genetic connectivity of populations), electrical engineering (resistive networks, graph signal processing), PDEs (Laplacians on manifolds), and many more. The material of this course will range over both theoretical and applied aspects of graph Laplacians. What can they be used for? What is the mathematics behind them? How can we compute with them in practice?
The prerequisites are some basic knowledge of linear algebra and graph theory. While this background is elementary, the course will move at a quick pace. The work for the course will consist of approximately 5 problem sets, plus a final project that may be either computational or theoretical.