Lagmental Vicfred

Effective Resistance Is a Laplacian Pseudoinverse Distance by Vicfred

Last updated: Sun 07 May 2023

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

Electrical resistance between two vertices is a quadratic form in the Moore--Penrose pseudoinverse. The example is deliberately concrete; it is a test of the statement, not a substitute for it.

Start locally

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.

$$ b_{uv}=e_u-e_v $$

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\).

$$ R_{\mathrm{eff}}(u,v)=b_{uv}^{\mathsf T}L^+b_{uv} $$

Compute before generalising

The following line is the smallest calculation that still exercises the mechanism. It keeps nested delimiters and the order of operations explicit.

$$ Lv=b_{uv},\quad v\perp\mathbf1\Longrightarrow R_{\mathrm{eff}}(u,v)=v_u-v_v=\sum_{\{i,j\}\in E}(v_i-v_j)^2 $$

The global view

The abstraction earns its keep by explaining why the same computation reappears. The notation compresses repeated reasoning without erasing the hypothesis that licenses it.

$$ \begin{aligned} \mathsf{D}\;&:\quad b_{uv}=e_u-e_v,\\[5pt] \mathsf{C}\;&:\quad R_{\mathrm{eff}}(u,v)=b_{uv}^{\mathsf T}L^+b_{uv}. \end{aligned} $$

Edge conditions

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] R_{\mathrm{eff}}(u,v)=b_{uv}^{\mathsf T}L^+b_{uv} \end{gathered}} $$

The notation is dense, but it is doing honest work: every delimiter records scope and every index records dependence. Removing one should require a mathematical reason.

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