The Laplacian Quadratic Form And Edge Energy

From the Laplacian to Edge Energy

The graph Laplacian turns local differences between neighboring vertex values into a single quadratic quantity. Its quadratic form measures how much a real-valued vector changes across the edges: a vector that assigns similar values to adjacent vertices has small energy, while a vector with large jumps across edges has larger energy. This tutorial derives that interpretation directly from the definition of the Laplacian and uses it to characterize exactly when the energy is zero.

Throughout, graphs are finite and simple, and vectors are real-valued. For a graph \(G=(V,E)\), the degree matrix \(\mathbf{D}\) has \(\deg(v)\) in the diagonal entry indexed by \(v\), and zeros elsewhere. The adjacency matrix \(\mathbf{A}\) has entry \(1\) at \(u,v\) when \(uv\in E\), and \(0\) otherwise. The Laplacian is \(\mathbf{L}=\mathbf{D}-\mathbf{A}\). We write \(x_v\) for the coordinate of a vector \(x\) at vertex \(v\).

The word “energy” here is a name for this particular quadratic form; no physical interpretation is needed. The crucial feature is that the contribution of an edge depends only on the difference between the values at its endpoints.

The Edge-Energy Identity

Proof. Since \(\mathbf{L}=\mathbf{D}-\mathbf{A}\), expand the quadratic form as $$ x^{\mathsf T}\mathbf{L}x =\sum_{v\in V}\deg(v)x_v^2-\sum_{u\in V}\sum_{v\in V} A_{uv}x_ux_v. $$ In the first sum, \(x_v^2\) occurs once for each edge incident with \(v\). Thus the first sum can be written \(\sum_{uv\in E}(x_u^2+x_v^2)\). In the second sum, each undirected edge \(uv\) contributes twice: once as \(A_{uv}x_ux_v\) and once as \(A_{vu}x_vx_u\). Because \(A_{uv}=A_{vu}=1\), the second sum is \(2\sum_{uv\in E}x_ux_v\). Subtracting gives $$ x^{\mathsf T}\mathbf{L}x =\sum_{uv\in E}(x_u^2+x_v^2-2x_ux_v) =\sum_{uv\in E}(x_u-x_v)^2. $$ The final equality uses \(a^2+b^2-2ab=(a-b)^2\) for each edge. If \(V\) is empty, both sums are empty and equal to zero, so the identity also holds in that case. \(\square\)

This identity also explains the connection with an oriented incidence matrix. If each edge is assigned a direction, the corresponding incidence-matrix coordinate of \(x\) is either \(x_u-x_v\) or \(x_v-x_u\), depending on that direction. Squaring removes the sign, so the sum of squared incidence coordinates is the same edge energy, whatever orientations are chosen.

When Is the Energy Zero?

Here a path is a sequence of distinct vertices with consecutive vertices adjacent, and two vertices are in the same connected component when there is a path between them (a vertex is also considered connected to itself). The equivalence says that zero energy imposes one equality for every edge; along paths, those equalities force all the values in a component to agree.

Proof. By the edge-energy identity, \(x^{\mathsf T}\mathbf{L}x\) is a finite sum of nonnegative real numbers, one term \((x_u-x_v)^2\) for each edge. The sum equals zero if and only if every term equals zero: if any term were positive, the sum would be positive, and if all terms are zero, their sum is zero. For a real number, \((x_u-x_v)^2=0\) holds exactly when \(x_u=x_v\). This proves the first equivalence, including the case \(E=\varnothing\), where the edge condition is vacuous and the energy is zero.

Now suppose every edge has equal endpoint values. If two vertices lie in the same connected component, there is a path \(v_0,v_1,\ldots,v_k\) between them. For each \(i\) with \(0\le i<k\), the edge \(v_iv_{i+1}\) gives \(x_{v_i}=x_{v_{i+1}}\). Chaining these equalities gives \(x_{v_0}=x_{v_k}\). Thus the vector is constant on each component. Conversely, if \(x\) is constant on each component, the endpoints of every edge belong to the same component, so each edge has equal endpoint values and every squared difference is zero. For an isolated vertex there is no incident edge imposing a constraint, and its component consists of that vertex alone. If \(V=\varnothing\), the unique empty vector is constant on every component vacuously. \(\square\)

Reading the Formula and Avoiding a Pitfall

Every edge contributes a nonnegative amount. An edge contributes zero exactly when its endpoints have the same value; changing the values at vertices that are not joined by a path does not, by itself, create energy between those components. The formula is also unchanged if the endpoints of an edge are written in the opposite order, because \((x_u-x_v)^2=(x_v-x_u)^2\).

Common mistake: counting an undirected edge twice. In the path example, the three edge contributions are \(4\), \(1\), and \(4\), so the energy is \(9\). A mistaken calculation might list both \(12\) and \(21\), both \(23\) and \(32\), and both \(34\) and \(43\) as separate edges, giving \(2(4+1+4)=18\). That is not the sum over \(E\): each undirected edge appears once in the edge sum. The adjacency-matrix part of the proof does count each edge twice, but that is precisely why it gives the term \(2x_ux_v\), which combines with the degree terms to produce one squared difference per edge.

The identity is useful whenever a Laplacian quadratic form needs a direct interpretation: instead of multiplying matrices, one can inspect differences across edges. Conversely, it lets us recognize zero energy without solving a matrix equation. The result here concerns the quadratic form itself; the componentwise description also indicates why disconnected graphs allow independent constant values on their different components.