Laplacian matrix

The Laplacian matrix (or graph Laplacian) of a graph G with n vertices is defined as L = D − A, where D is the degree matrix (a diagonal matrix with vertex degrees on the diagonal) and A is the adjacency matrix. The Laplacian is the central object of algebraic graph theory: its eigenvalues — the spectrum of the graph — encode structural properties that are invisible to combinatorial inspection.

The smallest eigenvalue of L is always zero, with multiplicity equal to the number of connected components. The second smallest eigenvalue — the algebraic connectivity or spectral gap — governs the convergence rate of random walks, the stability of consensus dynamics, and the quality of graph partitions. In spectral clustering, the eigenvectors of the normalized Laplacian provide a low-dimensional embedding in which clusters become geometrically separable.

The Laplacian also appears in continuous settings as the discrete analogue of the Laplace operator. Just as the continuous Laplacian measures how much a function at a point differs from its average over neighboring points, the graph Laplacian measures the difference between a vertex's value and the average of its neighbors' values. This connection makes the graph Laplacian the natural operator for diffusion processes, electrical networks, and harmonic analysis on graphs.