## The Smallest Eigenvalues of a Graph Laplacian

Given a graph $G = (V, E)$, its adjacency matrix $A$ contains an entry at $A_{ij}$ if vertices $i$ and $j$ have an edge between them. The degree matrix $D$ contains the degree of each vertex along its diagonal.

The graph laplacian of $G$ is given by $D - A$.

Several popular techniques leverage the information contained in this matrix. This blog post focuses on the two smallest eigenvalues.

First, we look at the eigenvalue 0 and its eigenvectors. A very elegant result about its multiplicity forms the foundation of spectral clustering.

Then we look at the second smallest eigenvalue and the corresponding eigenvector. A slightly more involved result (YMMV) allows us to partition the graph in question. A recent publication by John Urschel (who apparently moonlights as a sportsperson) focused on this quantity.

The insights provided here sacrifice some rigor for the sake of brevity. I find such descriptions help me study without getting bogged down too much with details. A bibliography provided at the end contains links to actual proofs.

Fortior Per Mentem
(c) Shriphani Palakodety 2013-2018