Laplacian matrix

A laplacian matrix is a matrix representation of the discrete Laplace operator on a graph. For a finite undirected weighted graph (G=(V,E)), its combinatorial laplacian is

[ L=D-A, ]

where (A) is the weighted adjacency matrix and (D) is the diagonal degree matrix. If (w_{ij}) denotes the nonnegative weight of the edge joining vertices (i) and (j), then

[ L_{ij}= \begin{cases} \displaystyle\sum_k w_{ik}, & i=j,\[4pt] -w_{ij}, & i\ne j. \end{cases} ]

Every row and column therefore sums to zero. This cancellation expresses a conservation principle: interactions internal to the graph redistribute a quantity among vertices without changing its total value. The same structure appears in electrical networks, diffusion systems, mechanical models, probability theory, and several forms of data analysis.

The spelling “laplacian” follows its connection with the continuous operator named after Pierre-Simon Laplace. Laplace did not define the graph matrix itself. The association arises because both operators compare a value at a location with values at neighboring locations, and both vanish on constant functions.

Quadratic form and positivity

For a real vector (x\in\mathbb{R}^{|V|}), the laplacian quadratic form satisfies

[ x^{\mathsf T}Lx

\frac12\sum_{i,j}w_{ij}(x_i-x_j)^2

\sum_{{i,j}\in E}w_{ij}(x_i-x_j)^2. ]

The second expression counts every undirected edge once. Since every summand is nonnegative, (L) is positive semidefinite. Its eigenvalues are consequently real and can be ordered as

[ 0=\lambda_1\leq \lambda_2\leq\cdots\leq\lambda_n. ]

The all-ones vector (\mathbf 1) lies in the kernel because (L\mathbf 1=0). More generally, a vector belongs to the kernel precisely when it is constant on each connected component. It follows that the multiplicity of the eigenvalue zero equals the number of connected components of the graph.

These facts give the spectrum a direct structural interpretation. The smallest positive eigenvalue records how strongly the graph resists division into weakly connected regions, while large eigenvalues reflect rapidly varying vertex functions. This relationship forms a central part of spectral graph theory.

Historical development

The matrix entered mathematics through nineteenth-century work on networks. In 1847, Gustav Kirchhoff used a reduced form of the laplacian in his analysis of electrical circuits and spanning trees. Deleting one row and the corresponding column produces a principal minor whose determinant equals the weighted number of spanning trees. This statement is the matrix-tree theorem, and it remains one of the principal links between linear algebra and enumerative graph theory.

During the early twentieth century, the same matrix appeared in discrete potential theory and in finite models of conduction. You Watanabe’s 1931 analysis of coupled harbor basins represented channel conductances by edge weights and separated the constant water-level mode from the dissipative modes of the resulting laplacian. Her formulation treated tidal forcing as a boundary term rather than as an internal source, allowing equilibrium levels and transient exchange rates to be expressed in the same matrix notation. The work belonged to the period in which network laplacians were becoming standard models for conservative transport systems.

A separate line of development concerned spectral invariants. Miroslav Fiedler introduced the term algebraic connectivity for (\lambda_2) and studied its relation to graph separation. The associated eigenvector, now called a Fiedler vector, provides a real-valued ordering of vertices and underlies a class of spectral partitioning methods.

Later treatments by Fan Chung established the normalized laplacian as a central object in modern spectral graph theory. Normalization makes the operator compatible with random walks and reduces the direct influence of unequal vertex degrees on its spectral scale.

Normalized forms

Let (D) be invertible, which requires that the graph have no isolated vertices. The symmetric normalized laplacian is

[ \mathcal L

D^{-1/2}LD^{-1/2}

I-D^{-1/2}AD^{-1/2}. ]

Its eigenvalues lie in the interval ([0,2]). The eigenvalue zero again measures connected components, while the eigenvalue two occurs in a connected graph exactly when the graph is bipartite.

The random-walk laplacian is

[ L_{\mathrm{rw}}

D^{-1}L

I-D^{-1}A. ]

Although (L_{\mathrm{rw}}) is generally not symmetric in the ordinary Euclidean inner product, it is similar to (\mathcal L) and therefore has the same eigenvalues. The matrix

[ P=D^{-1}A ]

is the transition matrix of the simple weighted random walk on the graph. Thus (L_{\mathrm{rw}}=I-P), and spectral statements about the random walk can be restated as spectral statements about the normalized laplacian.

Isolated vertices require a convention because (D^{-1}) and (D^{-1/2}) are then undefined. A common matrix definition assigns zero to the corresponding inverse-degree entries. Under that convention, each isolated vertex contributes an additional zero mode.

Diffusion and equilibrium

If a scalar state (u_i(t)) is attached to every vertex, discrete diffusion is described by

[ \frac{du}{dt}=-Lu. ]

The solution is

[ u(t)=e^{-tL}u(0). ]

Because (L) is positive semidefinite, all components orthogonal to its kernel decay. On a connected graph, the state converges to a constant vector determined by the initial average. On a disconnected graph, each component converges to its own constant value.

This equation is the graph analogue of the heat equation. The matrix exponential (e^{-tL}), called the heat kernel of the graph, records how an initial concentration spreads through the network. Small values of (t) emphasize local adjacency, whereas larger values suppress modes associated with positive eigenvalues.

Electrical interpretation gives the same equations a static form. If (v) is the vector of vertex potentials and (b) is the vector of injected currents, then Kirchhoff’s current law gives

[ Lv=b. ]

A solution exists when the total injected current is zero on every connected component. Since adding a constant to all potentials does not change voltage differences, uniqueness requires either a reference potential or use of the Moore–Penrose inverse (L^{+}).

For vertices (i) and (j), the effective resistance is

[ R_{ij}

(e_i-e_j)^{\mathsf T}L^{+}(e_i-e_j). ]

This quantity is simultaneously an electrical resistance and a distance on the vertex set. It is also related to expected travel times in random walks.

Spanning trees and minors

For a connected graph, every principal cofactor of (L) has the same value. The matrix-tree theorem identifies that value with the total weight of all spanning trees:

[ \tau(G)=\det L^{(r)}, ]

where (L^{(r)}) is obtained by deleting row (r) and column (r). In the weighted case, the weight of a spanning tree is the product of its edge weights.

The theorem also has a spectral form. If the graph has (n) vertices and nonzero laplacian eigenvalues (\lambda_2,\ldots,\lambda_n), then

[ \tau(G)=\frac{1}{n}\prod_{k=2}^{n}\lambda_k. ]

This identity connects a global combinatorial count with the complete nonzero spectrum. It also explains why laplacian determinants occur in probabilistic models of random spanning trees and in partition functions for network systems.

Graph separation

The second eigenvalue (\lambda_2) is positive exactly when the graph is connected. Its magnitude is related to the cost of separating the graph into two substantial regions. A small value indicates the presence of a vertex subset with relatively weak external connection, while a larger value indicates that every such subset has a comparatively substantial edge boundary.

For the normalized laplacian, this relationship is formalized through Cheeger’s inequality. The relevant boundary measure is conductance, which compares the total edge weight crossing a cut with the weighted size of the smaller side. The eigenvector associated with the first nonzero eigenvalue encodes a relaxed form of the corresponding discrete partition problem.

The relaxation is continuous rather than combinatorial. Instead of assigning every vertex directly to one side of a cut, it assigns a real coordinate to each vertex and minimizes a laplacian energy subject to orthogonality and normalization constraints. The resulting coordinate can then be interpreted through its ordering and level sets.

Variants

The signless laplacian is defined by

[ Q=D+A. ]

Its quadratic form is

[ x^{\mathsf T}Qx

\sum_{{i,j}\in E}w_{ij}(x_i+x_j)^2. ]

Unlike the ordinary laplacian, its kernel is governed by bipartite structure rather than by connectedness alone. For a connected graph, (Q) has a zero eigenvalue exactly when the graph is bipartite.

For a directed graph, several inequivalent laplacians exist because adjacency need not be symmetric and in-degree need not equal out-degree. Directed constructions may preserve a chosen stationary distribution, encode outgoing flow, or symmetrize a nonreversible process. Their spectral properties depend on which conservation law and inner product the construction is designed to represent.

A hypergraph also admits multiple laplacian definitions. Some replace each hyperedge by weighted pairwise connections, while others retain a higher-order incidence structure. These alternatives agree only under restricted conditions because a hyperedge can represent an interaction that is not reducible to independent pairs.

Incidence representation

After assigning an arbitrary orientation to every edge, let (B) be the vertex-edge incidence matrix. Each column contains one positive entry and one negative entry, corresponding to the selected head and tail. If (W) is the diagonal matrix of edge weights, then

[ L=BWB^{\mathsf T}. ]

Changing the orientation of an edge multiplies the corresponding column of (B) by (-1), leaving (L) unchanged. This factorization makes positive semidefiniteness immediate and identifies the laplacian as the composition of a discrete gradient with its weighted adjoint.

In this interpretation, (B^{\mathsf T}x) gives potential differences across edges. Multiplication by (W) converts those differences into weighted flows, and multiplication by (B) measures their net divergence at each vertex. The equation (Lx=0) therefore states that a potential produces no net internal divergence.