Lagmental Vicfred

The Laplacian Quadratic Form Is an Edge-Energy Sum by Vicfred

Last updated: Tue 11 June 2024

tags: mathematics, spectral graph theory, random walks, electrical networks

The quadratic form of L measures squared variation across edges. The formulas are more useful when each symbol has a job rather than merely decorating the theorem.

Objects and notation

The graph Laplacian \(L=D-A\) is positive semidefinite and turns combinatorial connectivity into linear algebra. A random walk uses \(P=D^{-1}A\) when degrees are positive.

$$ L=D-A $$

The definition determines which expressions are legal; only then does the identity become meaningful. An equality in \(\mathcal A\) may change ambient meaning, so I keep \(\mathsf D\) separate from \(\mathsf C\).

$$ x^{\mathsf T}Lx=\sum_{\{u,v\}\in E}(x_u-x_v)^2 $$

Push the symbols

A worked instance is useful here because it exposes every index that the compressed statement hides.

$$ x^{\mathsf T}Lx=\sum_ud_ux_u^2-2\sum_{\{u,v\}\in E}x_ux_v=\sum_{\{u,v\}\in E}(x_u^2-2x_ux_v+x_v^2) $$

Structural reading

The two-row display is also a debugging tool: if the conclusion changes when only notation changes, some hidden choice has entered the argument.

$$ \begin{aligned} \mathsf{D}\;&:\quad L=D-A,\\[5pt] \mathsf{C}\;&:\quad x^{\mathsf T}Lx=\sum_{\{u,v\}\in E}(x_u-x_v)^2. \end{aligned} $$

A hypothesis worth keeping

Normalized and unnormalized Laplacians have different eigenvalues and orthogonality measures. Formulas must state which one is being used.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] x^{\mathsf T}Lx=\sum_{\{u,v\}\in E}(x_u-x_v)^2 \end{gathered}} $$

A symbolic summary is trustworthy only because the example and limitation remain visible beside it. The box compresses the conclusion without hiding its origin.

This article was posted on Wed 20 January 2021. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.