Lagmental Vicfred

Laplacian Nullity Counts Connected Components by Vicfred

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

A vector has zero Laplacian energy exactly when it is constant on each connected component. The point is to make the formal expression readable enough to audit line by line.

Set-up

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\mathbf1_C=0\quad\text{for every component }C $$

A reliable calculation names domain and codomain. The notation \(\mathsf{data}\mapsto\mathsf{claim}\) is harmless only after both \(\operatorname{dom}\) and \(\operatorname{cod}\) have been fixed.

$$ \dim\ker L=c(G) $$

The calculation

The middle display is intentionally dense: it is where signs, bounds, multiplicities, or normalising factors are most likely to be lost.

$$ x^{\mathsf T}Lx=0\Longleftrightarrow x_u=x_v\ \forall\{u,v\}\in E\Longleftrightarrow x\ \text{constant on components} $$

What survives abstraction

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\mathbf1_C=0\quad\text{for every component }C,\\[5pt] \mathsf{C}\;&:\quad \dim\ker L=c(G). \end{aligned} $$

The boundary

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] \dim\ker L=c(G) \end{gathered}} $$

The important habit is to remember what was fixed before the calculation began and what was proved only afterward. The final display preserves that order.

This article was posted on Tue 03 October 2017. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.