The Laplacian Matrix

Graph Theory · Axiom Academy

Understanding the graph Laplacian: a fundamental matrix that captures both the structure and connectivity of graphs with powerful algebraic properties. D is the degree matrix (diagonal matrix with vertex degrees) A is the adjacency matrix (1 if edge exists, 0 otherwise) Let's visualize how the Laplacian matrix is constructed from a simple graph. We'll start with the graph, build the degree matrix D and adjacency matrix A, then compute L = D - A. The Laplacian matrix has a simple entry-wise characterization. Each entry L[i,j] can be directly computed based on the graph structure: L[i,i] = deg(i) - the degree of vertex i (diagonal) L[i,j] = -1 if vertices i and j are adjacent (off-diagonal) L[i,j] = 0 if vertices i and j are not adjacent (off-diagonal) Watch as we construct the Laplacian matrix entry by entry, showing how each value corresponds directly to the graph structure. The Laplacian matrix has several fundamental properties that make it extremely useful in graph theory and applications: Symmetric: L = L^T for undirected graphs Positive Semidefinite: All eigenvalues are non-negative (λ ≥ 0) Row/Column Sums Zero: Each row and column sums to 0 Singular: Always has eigenvalue 0 (with eigenvector of all 1's) Integer Entries: All entries are integers for simple graphs Let's visualize the zero row sum property, which shows that the Laplacian is always singular (non-invertible). 4. Incidence Matrix Representation

This is the written version of the interactive lesson above. See the full Graph Theory course.