Why do the rows sum to zero?

Each diagonal degree equals the sum of the edge weights subtracted elsewhere in that row.

Is the usual graph Laplacian invertible?

No. The all-ones vector is in its nullspace, so additional constraints or an appropriate generalized solution are needed for related linear systems.

Is a normalized Laplacian the same matrix?

No. It incorporates degree scaling and has related but different formulas and interpretations.

AI Glossary / Mathematics and optimization / Intermediate

Laplacian matrix

Definition

A Laplacian matrix is a matrix that represents differences across connections in a graph. For an undirected graph with nonnegative edge weights, its usual unnormalized form is L=D−A, where A is the weighted adjacency matrix and D places each node's weighted degree on the diagonal. It is widely used in graph analysis and numerical modeling.

What it means

An adjacency matrix records which nodes are connected. The Laplacian combines those connections with the total weight around each node. Applying it to a vector of node values compares each node with its neighbors, producing a measure of local disagreement.
This article uses a finite, undirected graph without self-loops and the positive-semidefinite convention L=D−A. Other settings use normalized Laplacians, directed variants, or the opposite sign. Naming the convention is therefore necessary before comparing formulas or software outputs.
In AI, graphs may connect similar documents, users, measurements, or other examples. A Laplacian can help express a preference for connected nodes to have similar representations or predictions. Whether that preference is appropriate depends on what the edges actually mean.

How it works

For each node i, add its incident edge weights to obtain dᵢ. Put dᵢ on the diagonal of L and put −wᵢⱼ in the off-diagonal position for an edge between i and j. An absent edge contributes zero.
For a node-value vector x, the i-th component of Lx is the sum of wᵢⱼ(xᵢ−xⱼ) over its neighbors. The quadratic expression xᵀLx equals the sum of wᵢⱼ(xᵢ−xⱼ)² over undirected edges counted once. It is nonnegative, which explains the positive-semidefinite property.
Every constant vector has zero energy. More generally, zero energy means the values are constant within each connected component of the positive-weight graph. The matrix is consequently singular, and its zero-eigenvalue multiplicity records the number of connected components under these assumptions.

Three practical examples

A document-analysis system can use a similarity graph's Laplacian in a spectral representation before clustering.
A model can penalize large prediction differences between connected examples when those connections justify a smoothness assumption.
A simulation can use a graph operator to represent exchange between neighboring locations, with the sign and time-update convention stated explicitly.

Think of it this way

Think of connected points joined by springs that resist differences in their assigned positions. Stronger connections make disagreement more costly. The analogy captures the squared-difference energy, but the graph need not describe physical springs, and a real mechanical system may require additional masses, geometry, forces, and boundary conditions.

Worked example

Consider an original graph with three nodes. Nodes 1 and 2 share an edge of weight 2; nodes 2 and 3 share an edge of weight 1; nodes 1 and 3 have no edge. The weighted degrees are 2, 3, and 1. Therefore L has rows (2,−2,0), (−2,3,−1), and (0,−1,1).
Give the nodes values x=(1,3,2)ᵀ. Multiplication gives Lx=(−4,5,−1)ᵀ. Taking the dot product with x gives xᵀLx=−4+15−2=9. The edge formula gives the same result: 2(1−3)²+1(3−2)²=8+1=9.
Now give every node the value 7. Each difference is zero, so L(7,7,7)ᵀ=0. This demonstrates why L has no ordinary inverse: a nonzero vector lies in its nullspace. Adding the same constant to all entries of x also leaves the energy unchanged, because all pairwise differences remain unchanged.
Finally, consider the indicator vector z=(1,0,0)ᵀ for the set containing node 1. Its energy is zᵀLz=2, equal to the weight of the only edge crossing from that set to the remaining nodes. This connects the same matrix with both smoothness of numerical values and the weight of a graph cut.

Illustrative case study

In a fictional research-document service, analysts connect papers using a reviewed similarity measure and build an undirected weighted graph. They examine a Laplacian-based embedding as one way to explore groups of related documents.
Before interpreting a separated group as a meaningful topic, they check whether the graph accidentally disconnected papers written in a less common language. They also compare results after reasonable changes to edge construction. The numerical method can reveal structure in the chosen graph, but it cannot establish that the chosen graph faithfully represents every useful relationship. This is a hypothetical workflow, not a measured product result.

Common misconceptions and mistakes

Do not confuse the adjacency matrix with the Laplacian or assume all Laplacian conventions are interchangeable. Do not claim positive semidefiniteness for an arbitrary directed or negative-weight construction using the undirected argument.
When summing over every ordered pair of nodes rather than each undirected edge once, the quadratic-form formula needs a factor of one-half. Also, the zero eigenvalue is expected, not automatically a numerical defect. A normalized Laplacian changes the role of degrees, and isolated nodes require an explicit convention where inverse degrees appear.

Business use

For business applications, graph construction is often as consequential as the subsequent matrix calculation. Document what a node represents, what an edge means, how weights are scaled, and whether connections are symmetric. Inspect disconnected components and unusually high-degree nodes before drawing conclusions from an embedding or partition.
If a model uses Laplacian smoothness, verify that neighboring nodes should actually have similar targets. Connections can also link contrasting roles or competing entities. Treating every connection as evidence of similarity can impose the wrong preference even when the matrix computation is correct.

Check your understanding

For one edge of weight 4 joining nodes with values 2 and 5, what is its contribution to xᵀLx?

Answer: 4(2−5)²=36, counting that undirected edge once.

Related terms

Graph
Eigenvalue
Spectral clustering
Regularization
Adjacency matrix
degree matrix
positive-semidefinite matrix
graph cut
graph signal

Learn next

Next, build L for a four-node graph with two disconnected pairs and find two independent zero-energy vectors. Then compare an unnormalized Laplacian with a degree-normalized version to understand why the convention affects an analysis.

Graph

Sources

Primary reference: Daniel A. Spielman, Spectral Graph Theory, Lecture 2: The Laplacian, original Yale lecture notes, especially the matrix and quadratic-form derivations: https://cs.yale.edu/homes/spielman/561/lect02-15.pdf . The weighted three-node calculation is original.

Previous: Laplace smoothing Next: Laplacian smoothing