Energy

We assume that the network is finite, that is $V$ and $E$ are finite sets. As usual We define the Hilbert space $l^2(V)$ of real functions on $V$ with inner product:

$$(f,g):=\sum _{x\in V}f(x)g(x)$$

We are interest in flows, so we extend the edge set $E$ to contain edges in both directrion, $e$ and $-e$, so that a flow is antisymmetric $\theta (-e)=-\theta (e)$. Thus we define $l_{-}^2(E)$ the hilbert space of antysimmetric functions on $E$ with inner product

$$(\theta ,{\theta }^{\prime }):=\frac{1}{2}\sum _{e\in E}\theta (e){\theta }^{\prime }(e)$$

Given a voltage function we can build currents, so we define the coboundary operator $d:l^2(V)\to l_{-}^2(E)$ by

$$(df)(e):=f(e^{-})-f(e^{+})$$

note that it’s linear.

Conversely, given an antisymetric function we can build an operator that computes the net our flow of a given vertex, the boundary operator $d^{\ast }:l_{-}^2(E)\to l^2(V)$ defined by

$$(d^{\ast }\theta )(x):=\sum _{e\in E:e^{-}=x}\theta (e)$$

which is also linear.

Oss The boundary and coboundary operator are adjoint of each other.

Proof We need to check that $\forall f,\theta$

$$(df,\theta )=(f,d^{\ast }\theta )$$

from the definition of inner product

$$\frac{1}{2}\sum _{e\in E}\left[f(e^{-})-f(e^{+})\right]\theta (e)$$ $$=\frac{1}{2}\sum _{e\in E}f(e^{-})\theta (e)-\frac{1}{2}\sum _{e\in E}f(e^{+})\theta (e)$$

we can rearrange the first term by highlighting terms $f(x)$

$$f(x)\left[\sum _{e^{-}=x}\theta (e)\right]$$

and summing. Similarly for the second term

$$\frac{1}{2}\sum _{x\in V}f(x)\left[\sum _{e^{-}=x}\theta (e)\right]-\frac{1}{2}\sum _{x\in V}f(x)\left[\sum _{e^{+}=x}\theta (e)\right]$$

but if $e^{+}=x$, then $-e=e^{-}$ of $x$, so that

$$=\sum _{x\in V}f(x)(d^{\ast }\theta )(x)=(f,d^{\ast }\theta )\square$$

With these definitions we can restate the laws: Let $i$ be a current, then

Ohm’s Law: $dv=ir$, that is $\forall e\in E$ $(dv)(e)=i(e)r(e)$ Kirchhoff’s node law: $d^{\ast }i(x)=0$ if $x\notin A\cup Z$.

We can think of a flow as a fuild flowing through a network of pipes. The scource are the vetices $a\in A$, the amount of fluid entering the network is just ${\sum }_{a\in A}{d}^{\ast }\theta (a)$, which is the same amount exiting the network in the sink $Z$. We call the total amount of current entering the network Def The Strenght of the flow is defined as

$$\text{Strenght}(\theta ):=\sum _{a\in A}(d^{\ast }\theta )(a)$$

Lemma (flow conservation) Let $G$ be a finite graph and $A$ and $Z$ be disjoint subsets of its vertices. If $\theta$ is a flow between $A$ and $Z$, then

$$\sum _{a\in A}(d^{\ast }\theta )(a)=-\sum _{z\in Z}(d^{\ast }\theta )(z)$$

Proof Since $\theta$ is a flow

$$\sum _{x\notin A\cup Z}(d^{\ast }\theta )(x)=0$$

so that

$$\sum _{a\in A}(d^{\ast }\theta )(a)+\sum _{z\in Z}(d^{\ast }\theta )(z)+\sum _{x\notin A\cup Z}(d^{\ast }\theta )(x)=\sum _{x\in V}(d^{\ast }\theta )(x)$$

but this can be written as the inner product

$$=(d^{\ast }\theta ,1)=(\theta ,d1)=(\theta ,0)=0\square$$

Lemma Let $G$ be a finite graph and $A$ and $Z$ two disjoint subsets of its vertices, and $\theta$ a flow from $A$ to $Z$ and $f$ is constant on $A$ and $Z$ with values $\alpha$ and $\xi$, respectively, then

$$(\theta ,df)=\text{Strength}(\theta )(\alpha -\xi )$$

Proof

$$(\theta ,df)=(d^{\ast }\theta ,f)=\sum _{x\in V}(d^{\ast }\theta )(x)f(x)$$ $$=\alpha \sum _{a\in A}(d^{\ast }\theta )(a)+\xi \sum _{z\in Z}(d^{\ast }\theta )(z)=\text{Strength}(\theta )(\alpha -\xi )\square$$

Def (Energy) For an antisymmetric function $\theta$, we define its energy to be

$$\mathcal{E}(\theta ):=\Vert \theta {\Vert }_r^2$$

where we have introduced the norm induced by the inner product which scales each component by the resistence:

$$(f,g{)}_r:=(fr,g)=(f,gr)$$

Now we are interested in the energy (dissipated) by a current, so that Kirchhoff’s and Ohm’s law hold:

$$\mathcal{E}(i)=(i,i{)}_r=(ir,i)=(dv,i)$$

now suppose that we are in the case of the previous lemma, with $f$ beeing a voltage function such taht $f(A)=v_a$ and $f(Z)=v_z$, then

$$\mathcal{E}(i)=\text{Strength}(i)(v_a-v_z)$$

using the relation

$$v_a-v_b=\text{Strength}(i)\mathcal{R}(A\leftrightarrow Z)$$

we can conclude that

$$\mathcal{E}(i)=\text{Strength}(i{)}^2\mathcal{R}(A\leftrightarrow Z)$$

Star and loop decomposition of $l_{-}^2$ §

Let’s introduce the signed characteristic function of an edge:

$${\chi }^e:=1_e-1_{-e}$$

clearly $({\chi }^e,\theta {)}_r=r(e)\theta (e)$.

With this we can rewrite Kirchhoff’s laws using the scalar procuct $(\cdot ,\cdot {)}_r$

$${\left(\sum _{e^{-}=x}{\chi }^{e}c(e),i\right)}_r=0\forall x\notin (A\cup Z)$$ $${\left(\sum _{i=1}^n{\chi }^{e_i},i\right)}_r=0\forall e_1,\dots ,e_n=e_1$$

Consider the subspaces $\star$ and $◊$, spanned by the functions in the left side of the inner products above:

Claim 1 $\star \perp ◊$ Proof Easy for the base elements, make a drawing. $\square$

Claim 2 We can decompose $l_{-}^2(E,r)=\star \oplus ◊$ Proof We show that if $\theta \perp \star$ and $\theta \perp ◊$ then $\theta =0$. Then $\theta$ satisfies Kirchhoff’s two law, so that there exists a potential $v$ so that $\theta (e)=dv(e)c(e)$. Since $\theta \perp ◊$, $v$ is harmonic everywhere, this implies $v=cost.$ so that $\theta =0$. $\square$

Now, since any current satisfies Kirchhoff’s second law, $i\perp ◊$ so that $i\in \star$. Now take any flow $\theta$ with the same source and sink of a current $i$. Then $\theta -i$ is a souce-less flow, and $\theta -i\perp \star$. We have just found our decomposition:

$$\theta =i+(\theta -i)$$

This implies that given the resistences, a current $i$ has the smallest norm (induced by the resistences) among any flow $\theta$ which shares the same soucres $A$ and sinks $Z$:

$$\Vert \theta {\Vert }_r^2=\Vert i{\Vert }_r^2+\Vert \theta -i{\Vert }_r^2$$

from this follows

Theorem (Thomson’s Principle) Let $G$ be a finite network, $\theta$ a flow from $A$ to $Z$ and $i$ a current from $A$ to $Z$ such thatr $d^{\ast }i=d^{\ast }\theta$. Then $\mathcal{E}(\theta )>\mathcal{E}(i)$ unless $\theta =i$. Proof Immediate consequence of the previous facts.

Theorem (The Nash-Williams inequality) If $a$ and $z$ are distinct vertices in a finite network that are separated by pairwise disjoint cutsets ${\Pi }_1,\dots ,{\Pi }_n$, then

$$\mathcal{R}(a\leftrightarrow z)\ge \sum _{k=1}^n{\left(\sum _{e\in {\Pi }_k}c(e)\right)}^{-1}$$

Proof We use the equivalence of the energy of a unit current and effective resistence. Consider the unit flow from $a$ to $z$, we can induce a new unit flow in a reduce network: call $K$ the set of vertices still reachable from $a$, and call $Z\subseteq V\setminus K$ the boundary of $\Pi$, . It’s easy to see using flow conservation that

$$\sum _{x\in Z}{d}^{\ast }i(z)=\sum _{e^{+}\in Z}i(e)=1$$

this is a unit flow from $a$ to $Z$. Then by the Cauchy-Schwarz inequality

$$\sum _{e\in \Pi }i(e{)}^{2}r(e)\sum _{e\in \Pi }c(e)\ge {\left(\sum _{e\in Pi}|i(e)|r(e{)}^{1/2}c(e{)}^{1/2}\right)}^2={\left(\sum _{e\in \Pi }|i(e)|\right)}^2$$ $$\ge {\left(\sum _{e^{-}\in Z}|i(e)|\right)}^2\ge 1$$

so that

$$\sum _{e\in \Pi }i(e{)}^{2}r(e)\ge {\left(\sum _{e\in \Pi }c(e)\right)}^{-1}$$

by summing over over $k$ we get our result. $\square$

Since enery is related to resistance, and resistance to infinity is realted to transience, we have the following usefull result.

Theorem (Rayleigh’s Monotonicity Principle) Let $G$ be a connected graph with two sets of non-negative weights $c$ and $c^{\prime }$ such that $c\le c^{\prime }$.

1. If $G$ is finite and $A$ and $Z$ two disjoint subsets, then

$${\mathcal{C}}_c(A\leftrightarrow Z)\le {\mathcal{C}}_{c^{\prime }}(A\leftrightarrow Z)$$

2. If $G$ is infinite then

$${\mathcal{C}}_c(A\leftrightarrow \infty )\le {\mathcal{C}}_{c^{\prime }}(A\leftrightarrow \infty )$$

in particular if $(G,c)$ is transient, then so is $(G,c^{\prime })$.

Proof $2.$ follows simply by $1.$ and taking the limit for a sequnce $G_n$ that exaust $G$. To prove $1.$ consider a unit flow from $A$ to $Z$. We have proven that

$$\mathcal{C}(A\leftrightarrow Z{)}^{-1}=\mathcal{E}(i)$$

now

$${\mathcal{E}}_c(i_c)\ge {\mathcal{E}}_{c^{\prime }}(i_c)\ge {\mathcal{E}}_{c^{\prime }}(i_{c^{\prime }})$$

the first inequality follows from the definition of energy (if $r=\frac{1}{c}\ge r^{\prime })$, the second from Thomson’s principle. $\square$