Linear AlgebraApplications3 of 6
Applications · 3

Graphs and Networks: The Incidence Matrix

To see how water, electric current, or forces distribute across a network too large to inspect by eye, we need a way to record its connections in a matrix.

1

From a Network to the Incidence Matrix

Suppose four water tanks sit at heights x1,x2,x3,x4\height{x_1}, \height{x_2}, \height{x_3}, \height{x_4}, connected by five pipes. Water flows through a pipe whenever the two tanks at its ends sit at different heights, so we want a matrix that takes the four tank heights x\height{x} and gives the height difference across every pipe.

11
22
33
44
11
22
33
44
55
x1\height{x_1}
x2\height{x_2}
x3\height{x_3}
x4\height{x_4}
From a Network to the Incidence Matrix
11
x1\height{x_1}
22
x2\height{x_2}
33
x3\height{x_3}
44
x4\height{x_4}

An arrow on a pipe does not mean water can only flow one way. It only fixes our subtraction order as End−Start\height{\text{End}} - \height{\text{Start}} so we measure every pipe the same way.

Text solution
Subtract start height from end height along each arrowEach pipe gives one row of height differences e=Ax\hdiff{e} = A\height{x}:
Edge 1 (1→2):e1=x2−x1Edge 2 (2→3):e2=x3−x2Edge 3 (1→3):e3=x3−x1Edge 4 (1→4):e4=x4−x1Edge 5 (3→4):e5=x4−x3\displaystyle \begin{aligned} \text{Edge 1 } (1 \to 2): &\quad \hdiff{e_1} = \height{x_2} - \height{x_1} \\ \text{Edge 2 } (2 \to 3): &\quad \hdiff{e_2} = \height{x_3} - \height{x_2} \\ \text{Edge 3 } (1 \to 3): &\quad \hdiff{e_3} = \height{x_3} - \height{x_1} \\ \text{Edge 4 } (1 \to 4): &\quad \hdiff{e_4} = \height{x_4} - \height{x_1} \\ \text{Edge 5 } (3 \to 4): &\quad \hdiff{e_5} = \height{x_4} - \height{x_3} \end{aligned}
Factor out the node heights into a column vectorPutting −1-1 in the column of the starting node, +1+1 in the column of the ending node, and 00 everywhere else builds our 5×45 \times 4 matrix:
[−11000−110−1010−100100−11]⏟incidence matrix A[x1x2x3x4]⏟node heights x=[x2−x1x3−x2x3−x1x4−x1x4−x3]⏟edge differences Ax\displaystyle \underbrace{\begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{bmatrix}}_{\text{incidence matrix } A} \underbrace{\begin{bmatrix} \height{x_1} \\ \height{x_2} \\ \height{x_3} \\ \height{x_4} \end{bmatrix}}_{\text{node heights } \height{x}} = \underbrace{\hdiff{\begin{bmatrix} \height{x_2} - \height{x_1} \\ \height{x_3} - \height{x_2} \\ \height{x_3} - \height{x_1} \\ \height{x_4} - \height{x_1} \\ \height{x_4} - \height{x_3} \end{bmatrix}}}_{\text{edge differences } \hdiff{Ax}}
2

The Nullspace of AA and Grounding a Node

Next, we want to find all tank heights x\height{x} that give zero height difference across every pipe (Ax=0\hdiff{Ax} = 0), leaving the water completely still.

The Nullspace of A and Grounding a Node
A[x1x2x3x4]=[00000]\displaystyle A\begin{bmatrix} \height{x_1} \\ \height{x_2} \\ \height{x_3} \\ \height{x_4} \end{bmatrix} = \begin{bmatrix} \hdiff{0} \\ \hdiff{0} \\ \hdiff{0} \\ \hdiff{0} \\ \hdiff{0} \end{bmatrix}
x\displaystyle \height{x} =  ?\displaystyle = \;?

Because every row of AA has one −1-1 and one +1+1 in the columns of the two nodes it connects, giving all four tanks the same height c\height{c} cancels every difference:

A[cccc]=c A[1111]=[00000]\displaystyle A\begin{bmatrix} \height{c} \\ \height{c} \\ \height{c} \\ \height{c} \end{bmatrix} = \height{c}\,A\begin{bmatrix} \height{1} \\ \height{1} \\ \height{1} \\ \height{1} \end{bmatrix} = \begin{bmatrix} \hdiff{0} \\ \hdiff{0} \\ \hdiff{0} \\ \hdiff{0} \\ \hdiff{0} \end{bmatrix}

Since that 11-dimensional line of constant vectors is the entire nullspace of AA, a connected network with nn nodes always has rank:

rank⁡(A)\displaystyle \operatorname{rank}(A) =n−1\displaystyle = n - 1

For our 44-node network, rank⁡(A)=4−1=3\operatorname{rank}(A) = 4 - 1 = 3. To solve for unique heights, we ground one node, such as setting x4=0\height{x_4} = \height{0}, which crosses out Column 4 of AA and leaves 33 independent columns.

Raising or lowering all four tanks by the same amount c\height{c} shifts the height vector x\height{x} by c(1,1,1,1)\height{c}(\height{1, 1, 1, 1}) while leaving all five edge differences Ax=xend−xstart\hdiff{Ax} = \height{x_{\text{end}}} - \height{x_{\text{start}}} unchanged, and setting all four tanks to the same height always gives Ax=0\hdiff{Ax} = 0.

Shifting all four tanks up or down together changes their heights without changing the drop along any pipe, and level tanks always have zero drop everywhere.
3

Loops, Trees, and Kirchhoff's Voltage Law

Since rank⁡(A)=3\operatorname{rank}(A) = 3, at most 33 of the 55 rows of AA can be independent. We want to see which edges make the rows of AA dependent, and what condition a vector of target height differences b=(b1,b2,b3,b4,b5)\hdiff{b} = (\hdiff{b_1}, \hdiff{b_2}, \hdiff{b_3}, \hdiff{b_4}, \hdiff{b_5}) must satisfy for Ax=bA\height{x} = \hdiff{b} to have a solution.

Loops, Trees, and Kirchhoff's Voltage Law
11
22
33
44
11
22
33
44
55
b1=100\hdiff{b_1 = 100}
b2=50\hdiff{b_2 = 50}
b3= ?\hdiff{b_3} = \ ?
two loops\text{two loops}
11
22
33
44
11
22
33
44
55
spanning tree\text{spanning tree}
11
22
33
44
11
22
44
3\htmlClass{lc-mute}{3}
5\htmlClass{lc-mute}{5}

Walking around any closed loop brings you back to the starting node, so the rows of AA and the height changes b=Ax\hdiff{b} = A\height{x} along that loop must cancel out.

Text solution
Follow the top triangle (1→2→3→1\loopone{1 \to 2 \to 3 \to 1})Going forward along Edge 1 and Edge 2 and returning against Edge 3 gives the first row dependency and loop condition (Kirchhoff's Voltage Law):
Row 1+Row 2−Row 3=[0000]⟹b1+b2−b3=0\displaystyle \loopone{\text{Row 1} + \text{Row 2} - \text{Row 3}} = \begin{bmatrix} 0 & 0 & 0 & 0 \end{bmatrix} \quad \Longrightarrow \quad \hdiff{b_1} + \hdiff{b_2} - \hdiff{b_3} = 0
Follow the bottom triangle (1→3→4→1\looptwo{1 \to 3 \to 4 \to 1})Going forward along Edge 3 and Edge 5 and returning against Edge 4 gives the second row dependency and loop condition:
Row 3+Row 5−Row 4=[0000]⟹b3+b5−b4=0\displaystyle \looptwo{\text{Row 3} + \text{Row 5} - \text{Row 4}} = \begin{bmatrix} 0 & 0 & 0 & 0 \end{bmatrix} \quad \Longrightarrow \quad \hdiff{b_3} + \hdiff{b_5} - \hdiff{b_4} = 0

Every closed loop in the network creates a linear dependency among its rows in AA, and removing loop edges until all four nodes are connected with no loops always leaves a spanning tree of n−1=3n - 1 = 3 independent rows.

Every closed loop in the network makes a matrix row redundant, while any spanning tree connecting all 4 nodes with no loops leaves 3 independent rows.
4

Pipe Flows and Kirchhoff's Current Law

Now we go in the reverse direction, from the five pipe flows y=(y1,y2,y3,y4,y5)\flow{y} = (\flow{y_1}, \flow{y_2}, \flow{y_3}, \flow{y_4}, \flow{y_5}) back to the four nodes using ATA^T, and find which pipe flows can circulate when no external hoses are attached (ATy=0A^T\flow{y} = 0).

Pipe Flows and Kirchhoff's Current Law
11
22
33
44
11
22
33
44
55
y1\flow{y_1}
y2\flow{y_2}
y3\flow{y_3}
y4\flow{y_4}
y5\flow{y_5}
ATy= ?\large A^{T}\flow{y} = \ ?

In each row of ATA^T, incoming arrows at that node have +1+1 and outgoing arrows have −1-1, so multiplying by y\flow{y} gives the net flow arriving at each node:

[−10−1−101−10000110−100011]⏟AT[y1y2y3y4y5]⏟pipe flows y=[−y1−y3−y4y1−y2y2+y3−y5y4+y5]⏟Pipe Flow In−Pipe Flow Out\displaystyle \underbrace{\begin{bmatrix} -1 & 0 & -1 & -1 & 0 \\ 1 & -1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & -1 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}}_{A^T} \underbrace{\begin{bmatrix} \flow{y_1} \\ \flow{y_2} \\ \flow{y_3} \\ \flow{y_4} \\ \flow{y_5} \end{bmatrix}}_{\text{pipe flows } \flow{y}} = \underbrace{\begin{bmatrix} -\flow{y_1} - \flow{y_3} - \flow{y_4} \\ \flow{y_1} - \flow{y_2} \\ \flow{y_2} + \flow{y_3} - \flow{y_5} \\ \flow{y_4} + \flow{y_5} \end{bmatrix}}_{\flow{\text{Pipe Flow In}} - \flow{\text{Pipe Flow Out}}}

Setting ATy=0A^T\flow{y} = 0 is Kirchhoff's Current Law: flow into every node equals flow out. Since AA has m=5m = 5 rows and rank r=3r = 3, this left nullspace N(AT)\flow{N(A^T)} has dimension m−r=5−3=2m - r = 5 - 3 = 2, and its basis comes from sending water around the two small triangles.

Text solution
Send 1 gal/sec\loopone{1}\text{ gal/sec} around the top triangle (1→2→3→1\loopone{1 \to 2 \to 3 \to 1})Moving with Edges 1 and 2 (+1\loopone{+1}) and against Edge 3 (−1\loopone{-1}) gives the first basis vector for N(AT)\flow{N(A^T)}:
yloop1=[11−100]\displaystyle \loopone{y_{\text{loop1}}} = \begin{bmatrix} \loopone{1} \\ \loopone{1} \\ \loopone{-1} \\ \loopone{0} \\ \loopone{0} \end{bmatrix}
Send 1 gal/sec\looptwo{1}\text{ gal/sec} around the bottom triangle (1→3→4→1\looptwo{1 \to 3 \to 4 \to 1})Moving with Edges 3 and 5 (+1\looptwo{+1}) and against Edge 4 (−1\looptwo{-1}) gives the second basis vector for N(AT)\flow{N(A^T)}:
yloop2=[001−11]\displaystyle \looptwo{y_{\text{loop2}}} = \begin{bmatrix} \looptwo{0} \\ \looptwo{0} \\ \looptwo{1} \\ \looptwo{-1} \\ \looptwo{1} \end{bmatrix}

Notice that our two loop equations for b\hdiff{b} to lie in the column space of AA are simply yloop1⋅b=0\loopone{y_{\text{loop1}}} \cdot \hdiff{b} = 0 and yloop2⋅b=0\looptwo{y_{\text{loop2}}} \cdot \hdiff{b} = 0, showing why the column space C(A)\hdiff{C(A)} is orthogonal to the left nullspace N(AT)\flow{N(A^T)}.

Any combination of loop flows y=c1yloop1+c2yloop2\flow{y} = c_1 \loopone{y_{\text{loop1}}} + c_2 \looptwo{y_{\text{loop2}}} keeps the net flow ATyA^T\flow{y} equal to 00 at every node, and sending water around both triangles at the same rate cancels the flow on the shared middle pipe to give a single flow around the outer loop.

Any combination of the two triangle loops keeps flow in equal to flow out at every node, and spinning both the same way at the same speed cancels the flow in the middle pipe to make one big outer loop.
5

Conductances and the Equilibrium Equation ATCAx=fA^T C A \height{x} = \inflow{f}

Now we attach external hoses that pump inflows or drains f=(f1,f2,f3,f4)\inflow{f} = (\inflow{f_1}, \inflow{f_2}, \inflow{f_3}, \inflow{f_4}) into the four nodes, and we want a single equation that connects the node heights x\height{x} directly to the external flows f\inflow{f}.

Conductances and the Equilibrium Equation AᵀCAx = f
11
22
33
44
11
22
33
44
55
x1\height{x_1}
x2\height{x_2}
x3\height{x_3}
x4\height{x_4}
f1\inflow{f_1}
f2\inflow{f_2}
f3\inflow{f_3}
f4\inflow{f_4}
x →? f\large \height{x} \ \xrightarrow{\quad ?\quad}\ \inflow{f}

Two minus signs show up along the way because of how we defined our directions, and they cancel when we combine the steps.

Text solution
Multiply the downhill drops by the pipe conductancesBecause e=Ax\hdiff{e} = A\height{x} measures End−Start\height{\text{End}} - \height{\text{Start}} while water flows downhill from higher to lower (Start−End=−e\height{\text{Start}} - \height{\text{End}} = -\hdiff{e}), multiplying by the diagonal conductance matrix C=diag⁡(c1,c2,c3,c4,c5)C = \operatorname{diag}(c_1, c_2, c_3, c_4, c_5) gives the pipe flows:
y\displaystyle \flow{y} =−Ce\displaystyle = -C\hdiff{e} =−CAx\displaystyle = -CA\height{x}
Match external inflow to net pipe flow leaving each nodeSince ATyA^T\flow{y} calculates Pipe Flow In−Pipe Flow Out\flow{\text{Pipe Flow In}} - \flow{\text{Pipe Flow Out}}, any external flow f\inflow{f} pumped into the nodes must leave through the pipes:
−ATy\displaystyle -A^T\flow{y} =f\displaystyle = \inflow{f}
Substitute the pipe flows into the node balancePlugging y=−CAx\flow{y} = -CA\height{x} into −ATy=f-A^T\flow{y} = \inflow{f} cancels the two minus signs:
ATCAx=f⏟equilibrium equation\displaystyle \underbrace{A^T C A\height{x} = \inflow{f}}_{\text{equilibrium equation}}

Because every column of ATA^T has one +1+1 and one −1-1, adding all the rows of −ATy=f-A^T\flow{y} = \inflow{f} always gives 00 on the left, which forces the entries of f\inflow{f} to sum to zero:

f1+f2+f3+f4\displaystyle \inflow{f_1} + \inflow{f_2} + \inflow{f_3} + \inflow{f_4} =0\displaystyle = 0
6

The Graph Laplacian ATAA^T A

When every pipe has conductance 11 (C=IC = I), the equilibrium matrix becomes ATAA^T A, and we can read its entries straight from the network without multiplying matrices.

The Graph Laplacian AᵀA
A=[−11000−110−1010−100100−11]\displaystyle A = \begin{bmatrix} -1 & 1 & 0 & 0 \\ 0 & -1 & 1 & 0 \\ -1 & 0 & 1 & 0 \\ -1 & 0 & 0 & 1 \\ 0 & 0 & -1 & 1 \end{bmatrix}
ATA\displaystyle A^{T}A =  ?\displaystyle = \;?

Taking the dot product of each column of AA with itself counts how many edges touch that node, and taking the dot product of two different columns gives −1-1 if an edge connects them and 00 if not:

ATA⏟Graph Laplacian=[3−1−1−1−12−10−1−13−1−10−12]\displaystyle \underbrace{A^T A}_{\text{Graph Laplacian}} = \begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 2 & -1 & 0 \\ -1 & -1 & 3 & -1 \\ -1 & 0 & -1 & 2 \end{bmatrix}
7

Solving ATAx=fA^T A \height{x} = \inflow{f} for Heights and Flows

Let's solve ATAx=fA^T A\height{x} = \inflow{f} on our network when 4 gal/sec\inflow{4}\text{ gal/sec} is pumped into Node 1 and 4 gal/sec\inflow{4}\text{ gal/sec} is drained from Node 4, so f=(4,0,0,−4)\inflow{f} = (\inflow{4}, \inflow{0}, \inflow{0}, \inflow{-4}).

Solving AᵀAx = f for Heights and Flows
[3−1−1−1−12−10−1−13−1−10−12]ATA x=f\displaystyle \overset{A^{T}A}{\begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 2 & -1 & 0 \\ -1 & -1 & 3 & -1 \\ -1 & 0 & -1 & 2 \end{bmatrix}}\,\height{x} = \inflow{f}
f\displaystyle \inflow{f} =(4,0,0,−4)\displaystyle = (\inflow{4}, \inflow{0}, \inflow{0}, \inflow{-4})
x\displaystyle \height{x} =  ?\displaystyle = \;?
11
22
33
44
11
22
33
44
55
f1=+4 gal/sec\inflow{f_1 = +4}\ {\small\text{gal/sec}}
f4=−4 gal/sec\inflow{f_4 = -4}\ {\small\text{gal/sec}}
x1=2.5\height{x_1 = 2.5}
x2=2.0\height{x_2 = 2.0}
x3=1.5\height{x_3 = 1.5}
x4=0.0\height{x_4 = 0.0}
0.5\flow{0.5}
0.5\flow{0.5}
1.0\flow{1.0}
2.5\flow{2.5}
1.5\flow{1.5}
Text solution
Ground Node 4 to remove the nullspaceSetting x4=0\height{x_4} = \height{0} crosses out Column 4 and Row 4 of ATAx=fA^T A\height{x} = \inflow{f}, leaving an invertible 3×33 \times 3 system:
[3−1−1−12−1−1−13][x1x2x3]=[400]\displaystyle \begin{bmatrix} 3 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 3 \end{bmatrix} \begin{bmatrix} \height{x_1} \\ \height{x_2} \\ \height{x_3} \end{bmatrix} = \begin{bmatrix} \inflow{4} \\ \inflow{0} \\ \inflow{0} \end{bmatrix}
Write Node 2's height as the average of its neighborsBecause Node 2 has no external hose (f2=0\inflow{f_2} = \inflow{0}), Row 2 gives −x1+2x2−x3=0-\height{x_1} + 2\height{x_2} - \height{x_3} = 0:
x2\displaystyle \height{x_2} =12(x1+x3)\displaystyle = \frac{1}{2}(\height{x_1} + \height{x_3})
Substitute x2\height{x_2} into Row 3 to write x1\height{x_1} and x2\height{x_2} in terms of x3\height{x_3}Plugging x2\height{x_2} into −x1−x2+3x3=0-\height{x_1} - \height{x_2} + 3\height{x_3} = 0 connects the three unknown heights:
−x1−12x1−12x3+3x3=0⟹52x3=32x1⟹x1=53x3,x2=43x3\displaystyle \begin{aligned} -\height{x_1} - \frac{1}{2}\height{x_1} - \frac{1}{2}\height{x_3} + 3\height{x_3} &= 0 \\ \Longrightarrow \quad \frac{5}{2}\height{x_3} &= \frac{3}{2}\height{x_1} \\ \Longrightarrow \quad \height{x_1} &= \frac{5}{3}\height{x_3}, \\ \height{x_2} &= \frac{4}{3}\height{x_3} \end{aligned}
Substitute into Row 1 to find the node heightsPlugging x1\height{x_1} and x2\height{x_2} into 3x1−x2−x3=43\height{x_1} - \height{x_2} - \height{x_3} = \inflow{4} gives x3\height{x_3} and then all four tank heights x\height{x}:
3(53x3)−43x3−x3=83x3=4⟹x3=1.5⟹x=[2.52.01.50.0]\displaystyle \begin{aligned} 3\left(\frac{5}{3}\height{x_3}\right) - \frac{4}{3}\height{x_3} - \height{x_3} &= \frac{8}{3}\height{x_3} = \inflow{4} \\ \Longrightarrow \quad \height{x_3} &= \height{1.5} \\ \Longrightarrow \quad \height{x} &= \begin{bmatrix} \height{2.5} \\ \height{2.0} \\ \height{1.5} \\ \height{0.0} \end{bmatrix} \end{aligned}
Subtract xstart−xend\height{x_{\text{start}}} - \height{x_{\text{end}}} to find the five pipe flowsSince each pipe has conductance 11, the downhill drops y=−Ax\flow{y} = -A\height{x} give the flows in all five pipes:
y=[2.5−2.02.0−1.52.5−1.52.5−0.01.5−0.0]=[0.50.51.02.51.5] gal/sec\displaystyle \flow{y} = \begin{bmatrix} \height{2.5} - \height{2.0} \\ \height{2.0} - \height{1.5} \\ \height{2.5} - \height{1.5} \\ \height{2.5} - \height{0.0} \\ \height{1.5} - \height{0.0} \end{bmatrix} = \begin{bmatrix} \flow{0.5} \\ \flow{0.5} \\ \flow{1.0} \\ \flow{2.5} \\ \flow{1.5} \end{bmatrix}\text{ gal/sec}

So the three pipes leaving Node 1 carry 0.5+1.0+2.5=4.0 gal/sec\flow{0.5} + \flow{1.0} + \flow{2.5} = \inflow{4.0}\text{ gal/sec} away from the inflow hose, and the two pipes reaching Node 4 deliver 2.5+1.5=4.0 gal/sec\flow{2.5} + \flow{1.5} = \inflow{4.0}\text{ gal/sec} to the drain.

Wherever we place the +4 gal/sec\inflow{+4}\text{ gal/sec} inflow hose and −4 gal/sec\inflow{-4}\text{ gal/sec} drain hose (with one node grounded at height 0\height{0}), the inflow tank sits highest and the drain tank sits lowest. The flows leaving the inflow node and arriving at the drain node each add up to 4 gal/sec\inflow{4}\text{ gal/sec}, and any node with no hose settles at the average height of its neighbors.

Wherever you place the inflow and drain hoses, the inflow node ends up highest, the drain node lowest, and every other node settles at the average height of its neighbors.
8

Euler's Formula from the Four Subspaces

Finally, counting the dimensions of the subspaces of AA shows why the vertices, edges, and faces of any connected, flat, non-crossing graph obey Euler's Formula.

Euler's Formula from the Four Subspaces
11
22
33
44
11
22
33
44
55
Nodes−Edges+Loops= ?\text{Nodes} - \text{Edges} + \text{Loops} = \ ?

For any connected network with nn nodes and mm edges, the rank of AA is r=n−1r = n - 1, and the number of independent loops in N(AT)\flow{N(A^T)} is m−r=m−(n−1)m - r = m - (n - 1). Rearranging puts all three counts on the left:

Nodes−Edges+Independent Loops\displaystyle \text{Nodes} - \text{Edges} + \text{Independent Loops} =n−m+(m−n+1)\displaystyle = n - m + (m - n + 1) =1\displaystyle = 1

When a connected planar graph is drawn flat with no crossing edges, the loops around the enclosed interior faces form a basis for N(AT)\flow{N(A^T)}, so there is one interior face for each independent loop, and counting the outside region around the drawing adds 11 more face to the total number of faces FF:

V−E+F=2⏟Euler’s Formula\displaystyle \underbrace{V - E + F = 2}_{\text{Euler's Formula}}

In our network, V=4V = 4 vertices, E=5E = 5 edges, and 22 triangular interior faces plus 11 outside region give F=3F = 3 faces, so 4−5+3=24 - 5 + 3 = 2. On a test, remember that FF includes the unbounded outside region: if you only count the enclosed interior loops dim⁡N(AT)=m−r\dim \flow{N(A^T)} = m - r, then V−E+Interior FacesV - E + \text{Interior Faces} equals 11, not 22.

Key concepts

When a problem asks for directed edge differences e=Ax\hdiff{e} = A\height{x} or has pipes with different conductances C=diag⁡(c1,…,cm)C = \operatorname{diag}(c_1, \dots, c_m), build the m×nm \times n incidence matrix AA by placing −1-1 at each arrow's starting node and +1+1 at its ending node (so Edge 1: 1→21 \to 2 gives row [−1100]\begin{bmatrix} -1 & 1 & 0 & 0 \end{bmatrix} and e1=x2−x1\hdiff{e_1} = \height{x_2} - \height{x_1}). When all pipes have conductance 11 (C=IC = I) and you only need to solve ATAx=fA^T A\height{x} = \inflow{f} for the node heights, skip building AA and write the Graph Laplacian ATAA^T A directly from the network: put each node's degree on the diagonal, −1-1 where two nodes share an edge, and 00 everywhere else.

For any connected network with nn nodes and mm edges, the nullspace N(A)\height{N(A)} is the 11-dimensional line of constant vectors x=c(1,…,1)\height{x} = \height{c}(\height{1, \dots, 1}). That gives rank⁡(A)=n−1\operatorname{rank}(A) = n - 1, so any spanning tree of n−1n - 1 edges with no closed loop (such as Edges {1,2,4}\{1, 2, 4\}) is a basis for the row space. A vector b\hdiff{b} lies in the column space C(A)\hdiff{C(A)} (Ax=bA\height{x} = \hdiff{b} has a solution) only when the height differences add up to zero around every closed loop (b1+b2−b3=0\hdiff{b_1} + \hdiff{b_2} - \hdiff{b_3} = 0, Kirchhoff's Voltage Law). Going the other way, ATyA^T\flow{y} gives Pipe Flow In−Pipe Flow Out\flow{\text{Pipe Flow In}} - \flow{\text{Pipe Flow Out}} at each node. The left nullspace N(AT)\flow{N(A^T)} (ATy=0A^T\flow{y} = 0, Kirchhoff's Current Law) has dimension m−(n−1)m - (n - 1), with one basis vector per independent loop (such as yloop1=(1,1,−1,0,0)\loopone{y_{\text{loop1}}} = \loopone{(1, 1, -1, 0, 0)}). On a flat planar graph, those m−rm - r loops are the interior faces, and adding 11 for the outside region gives V−E+F=2V - E + F = 2.

To connect heights to external inflows f\inflow{f}, combine y=−CAx\flow{y} = -CA\height{x} and −ATy=f-A^T\flow{y} = \inflow{f} into ATCAx=fA^T C A\height{x} = \inflow{f}, which has a solution only when total inflow equals total outflow (f1+⋯+fn=0\inflow{f_1} + \dots + \inflow{f_n} = 0). To solve it, ground one node (x4=0\height{x_4} = \height{0}) to cross out its row and column. Instead of doing full row reduction, use the shortcut that any node with fi=0\inflow{f_i} = \inflow{0} and identical pipes sits at the average height of its neighbors (such as x2=12(x1+x3)\height{x_2} = \frac{1}{2}(\height{x_1} + \height{x_3})), and then find the pipe flows from y=−CAx\flow{y} = -CA\height{x}.

9

Practice

1

A 3-node triangle network has directed edges Edge 1: 1→21 \to 2, Edge 2: 2→32 \to 3, and Edge 3: 1→31 \to 3. Write the 3×33 \times 3 incidence matrix AA, calculate the height difference vector e=Ax\hdiff{e} = A\height{x} when the tank heights are x=(12,5,8)\height{x} = (\height{12}, \height{5}, \height{8}), and state whether water in Edge 2 flows with or against the arrow.

For each row of AA, which node does the arrow leave (−1-1) and which node does it enter (+1+1)? Once you find e2\hdiff{e_2}, compare the heights at Nodes 2 and 3 to see which direction is downhill.

Placing −1-1 at each arrow's start node and +1+1 at its end node gives the 3×33 \times 3 incidence matrix AA, and multiplying by x=(12,5,8)\height{x} = (\height{12}, \height{5}, \height{8}) gives e=Ax\hdiff{e} = A\height{x}:
A=[−1100−11−101],e=Ax=[5−128−58−12]=[−73−4]\displaystyle \begin{aligned} A &= \begin{bmatrix} -1 & 1 & 0 \\ 0 & -1 & 1 \\ -1 & 0 & 1 \end{bmatrix}, \\ \hdiff{e} &= A\height{x} = \begin{bmatrix} \height{5} - \height{12} \\ \height{8} - \height{5} \\ \height{8} - \height{12} \end{bmatrix} = \begin{bmatrix} \hdiff{-7} \\ \hdiff{3} \\ \hdiff{-4} \end{bmatrix} \end{aligned}
(Be careful not to subtract Start−End\height{\text{Start}} - \height{\text{End}}, which flips the signs to (7,−3,4)(7, -3, 4), and do not assume a positive e2=+3\hdiff{e_2} = \hdiff{+3} means water flows with the arrow: e2=x3−x2=+3>0\hdiff{e_2} = \height{x_3} - \height{x_2} = \hdiff{+3} > 0 means the pipe goes uphill from Node 2 to Node 3.) Since water flows downhill from Node 3 (8\height{8}) to Node 2 (5\height{5}), water in Edge 2 flows against the arrow.
2

In the 4-node, 5-edge network (Edge 1: 1→21 \to 2, Edge 2: 2→32 \to 3, Edge 3: 1→31 \to 3, Edge 4: 1→41 \to 4, Edge 5: 3→43 \to 4), explain why Rows 1, 2, and 3 do not form a basis for the row space of AA, and identify which subsets of 3 edges do form a basis.

What shape do Edges 1, 2, and 3 form in the network drawing, and which other 3-edge subset forms the same kind of closed shape?

The row space has dimension rank⁡(A)=n−1=3\operatorname{rank}(A) = n - 1 = 3, so a basis must be 33 linearly independent rows (a spanning tree with no loops). Edges 1, 2, and 3 form a closed triangle loop, making their rows linearly dependent (Row 1+Row 2−Row 3=0\loopone{\text{Row 1} + \text{Row 2} - \text{Row 3}} = 0). (Be careful not to say every 3-edge subset besides {1,2,3}\loopone{\{1, 2, 3\}} works: the bottom triangle {3,4,5}\looptwo{\{3, 4, 5\}} also forms a closed loop with Row 3+Row 5−Row 4=0\looptwo{\text{Row 3} + \text{Row 5} - \text{Row 4}} = 0.) The subsets of 3 edges that form a basis for the row space are all 3-edge subsets except {1,2,3}\loopone{\{1, 2, 3\}} and {3,4,5}\looptwo{\{3, 4, 5\}}.
3

For the same 4-node, 5-edge network, suppose the target edge height differences are b=(40,−10,b3,70,b5)\hdiff{b} = (\hdiff{40}, \hdiff{-10}, \hdiff{b_3}, \hdiff{70}, \hdiff{b_5}). Find the values of b3\hdiff{b_3} and b5\hdiff{b_5} so that Ax=bA\height{x} = \hdiff{b} has a solution, and then find the node heights x\height{x} when Node 4 is grounded (x4=0\height{x_4} = \height{0}).

Walk around the top loop (1→2→3→1\loopone{1 \to 2 \to 3 \to 1}) and the bottom loop (1→3→4→1\looptwo{1 \to 3 \to 4 \to 1}) to write Kirchhoff's Voltage Law for b3\hdiff{b_3} and b5\hdiff{b_5}, paying attention to which arrow you walk against.

By Kirchhoff's Voltage Law around the top and bottom loops:
b1+b2−b3=0⟹40+(−10)−b3=0⟹b3=30b3+b5−b4=0⟹30+b5−70=0⟹b5=40\displaystyle \begin{aligned} \hdiff{b_1} + \hdiff{b_2} - \hdiff{b_3} = 0 &\quad \Longrightarrow \quad \hdiff{40} \\ &\quad + (\hdiff{-10})- \hdiff{b_3} \\ &= 0 \\ &\Longrightarrow \quad \hdiff{b_3} = \hdiff{30} \\ \hdiff{b_3} + \hdiff{b_5} - \hdiff{b_4} = 0 &\quad \Longrightarrow \quad \hdiff{30} \\ &\quad + \hdiff{b_5}- \hdiff{70} \\ &= 0 \\ &\Longrightarrow \quad \hdiff{b_5} = \hdiff{40} \end{aligned}
With Node 4 grounded (x4=0\height{x_4} = \height{0}), Edge 4 (1→41 \to 4) gives x4−x1=70\height{x_4} - \height{x_1} = \hdiff{70}. (Watch out for the order of subtraction here: setting x1=70\height{x_1} = 70 instead of solving 0−x1=70\height{0} - \height{x_1} = \hdiff{70} flips the sign and gives the wrong heights (70,110,100,0)(70, 110, 100, 0).) Solving from x4=0\height{x_4} = \height{0} gives:
x1=−70,x2=x1+40=−30,x3=x1+30=−40,x=(−70,−30,−40,0)\displaystyle \begin{aligned} \height{x_1} &= \height{-70}, \\ \height{x_2} &= \height{x_1} + \hdiff{40} = \height{-30}, \\ \height{x_3} &= \height{x_1} + \hdiff{30} = \height{-40}, \\ \height{x} &= (\height{-70}, \height{-30}, \height{-40}, \height{0}) \end{aligned}
4

In the same 4-node, 5-edge network with no external hoses (ATy=0A^T\flow{y} = 0), you measure pipe flows y1=3 gal/sec\flow{y_1} = \flow{3}\text{ gal/sec} on Edge 1 and y5=−2 gal/sec\flow{y_5} = \flow{-2}\text{ gal/sec} on Edge 5. Find the remaining pipe flows y2,y3,\flow{y_2}, \flow{y_3}, and y4\flow{y_4}, and write the vector y\flow{y} as a linear combination of the basis loops yloop1=(1,1,−1,0,0)\loopone{y_{\text{loop1}}} = \loopone{(1, 1, -1, 0, 0)} and yloop2=(0,0,1,−1,1)\looptwo{y_{\text{loop2}}} = \looptwo{(0, 0, 1, -1, 1)}.

Start at the two nodes touched by only two pipes (Node 2 and Node 4) using Pipe Flow In−Pipe Flow Out=0\flow{\text{Pipe Flow In}} - \flow{\text{Pipe Flow Out}} = 0 to find y2\flow{y_2} and y4\flow{y_4}, then use Node 3 to find y3\flow{y_3}.

Conservation of flow (ATy=0A^T\flow{y} = 0) at Node 2 gives y1−y2=0\flow{y_1} - \flow{y_2} = 0, so y2=3\flow{y_2} = \flow{3}. At Node 4, both Edge 4 and Edge 5 point into Node 4, so y4+y5=0\flow{y_4} + \flow{y_5} = 0, giving y4=2\flow{y_4} = \flow{2} (be careful not to treat one arrow as leaving Node 4, which gives y4=−2\flow{y_4} = -2). At Node 3, Edges 2 and 3 enter and Edge 5 leaves:
y2+y3−y5=0⟹3+y3−(−2)=0⟹y3=−5\displaystyle \begin{aligned} \flow{y_2} + \flow{y_3} - \flow{y_5} &= 0 \\ \Longrightarrow \quad \flow{3} + \flow{y_3} - (\flow{-2}) &= 0 \\ \Longrightarrow \quad \flow{y_3} &= \flow{-5} \end{aligned}
(Don't add y5=−2\flow{y_5} = \flow{-2} instead of subtracting the outgoing arrow, which gives y3=−1\flow{y_3} = -1.) Matching y1=3\flow{y_1} = \flow{3} on Edge 1 and y5=−2\flow{y_5} = \flow{-2} on Edge 5 gives:
y\displaystyle \flow{y} =(3,3,−5,2,−2)\displaystyle = \flow{(3, 3, -5, 2, -2)} =3yloop1−2yloop2\displaystyle = 3\loopone{y_{\text{loop1}}} - 2\looptwo{y_{\text{loop2}}}
5

Suppose the five pipes in our 4-node, 5-edge network have conductances C=diag⁡(2,1,3,1,2)C = \operatorname{diag}(2, 1, 3, 1, 2) and the node heights are x=(10,6,4,0)\height{x} = (\height{10}, \height{6}, \height{4}, \height{0}). Find the pipe flow vector y=−CAx\flow{y} = -CA\height{x} and the external inflow vector f=−ATy=ATCAx\inflow{f} = -A^T\flow{y} = A^T C A\height{x}, and check that the entries of f\inflow{f} add up to 00 so f\inflow{f} lies in the column space of ATA^T.

Find the five height differences e=Ax\hdiff{e} = A\height{x} first, multiply each by −ck-c_k to get yk\flow{y_k}, and then calculate Pipe Flow Out−Pipe Flow In\flow{\text{Pipe Flow Out}} - \flow{\text{Pipe Flow In}} at each node.

The edge height differences are e=Ax=(−4,−2,−6,−10,−4)\hdiff{e} = A\height{x} = (\hdiff{-4}, \hdiff{-2}, \hdiff{-6}, \hdiff{-10}, \hdiff{-4}). Multiplying by −C-C (don't drop the minus sign in y=−Ce\flow{y} = -C\hdiff{e}, which would make all five flows negative) gives the pipe flow vector:
y=−Ce=[−2(−4)−1(−2)−3(−6)−1(−10)−2(−4)]=[8218108]\displaystyle \flow{y} = -C\hdiff{e} = \begin{bmatrix} -2(\hdiff{-4}) \\ -1(\hdiff{-2}) \\ -3(\hdiff{-6}) \\ -1(\hdiff{-10}) \\ -2(\hdiff{-4}) \end{bmatrix} = \begin{bmatrix} \flow{8} \\ \flow{2} \\ \flow{18} \\ \flow{10} \\ \flow{8} \end{bmatrix}
Computing f=−ATy\inflow{f} = -A^T\flow{y} (be careful to compute −ATy=Pipe Flow Out-A^T\flow{y} = \flow{\text{Pipe Flow Out}} −Pipe Flow In{}- \flow{\text{Pipe Flow In}} rather than ATyA^T\flow{y}, which flips the signs to (−36,6,12,18)(-36, 6, 12, 18)) gives:
f=−ATy=[y1+y3+y4−y1+y2−y2−y3+y5−y4−y5]=[36−6−12−18],36−6−12−18=0\displaystyle \begin{aligned} & \inflow{f} = -A^T\flow{y} = \begin{bmatrix} \flow{y_1} + \flow{y_3} + \flow{y_4} \\ -\flow{y_1} + \flow{y_2} \\ -\flow{y_2} - \flow{y_3} + \flow{y_5} \\ -\flow{y_4} - \flow{y_5} \end{bmatrix} \\ &\quad = \begin{bmatrix} \inflow{36} \\ \inflow{-6} \\ \inflow{-12} \\ \inflow{-18} \end{bmatrix}, \\ & 36 - 6 - 12 - 18 = 0 \end{aligned}
6

Four nodes form a square ring connected by 4 identical pipes of conductance 1 around the outside: (1,2)(1, 2), (2,3)(2, 3), (3,4)(3, 4), and (4,1)(4, 1), with no diagonal pipes. Write the 4×44 \times 4 Graph Laplacian ATAA^T A directly from the network, and solve ATAx=fA^T A\height{x} = \inflow{f} when 6 gal/sec\inflow{6}\text{ gal/sec} is pumped into Node 1 and 6 gal/sec\inflow{6}\text{ gal/sec} is drained from Node 3 (f=(6,0,−6,0)\inflow{f} = (\inflow{6}, \inflow{0}, \inflow{-6}, \inflow{0})), with Node 3 grounded (x3=0\height{x_3} = \height{0}).

How many pipes touch each corner of the square, and which pairs of nodes lie across the diagonals with no pipe between them? Once Node 3 is grounded, use the neighbor-averaging rule at Nodes 2 and 4.

Each node has degree 22, and opposite corners (1,3)(1, 3) and (2,4)(2, 4) share no edge, giving:
ATA=[2−10−1−12−100−12−1−10−12]\displaystyle A^T A = \begin{bmatrix} 2 & -1 & 0 & -1 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ -1 & 0 & -1 & 2 \end{bmatrix}
Grounding Node 3 sets x3=0\height{x_3} = \height{0} and crosses out Row 3 and Column 3. Since Nodes 2 and 4 have zero external flow (f2=f4=0\inflow{f_2} = \inflow{f_4} = \inflow{0}), each sits at the average of its neighbors Node 1 and Node 3: x2=12(x1+0)=12x1\height{x_2} = \frac{1}{2}(\height{x_1} + \height{0}) = \frac{1}{2}\height{x_1} and x4=12(x1+0)=12x1\height{x_4} = \frac{1}{2}(\height{x_1} + \height{0}) = \frac{1}{2}\height{x_1}. Substituting into Row 1 (2x1−x2−x4=62\height{x_1} - \height{x_2} - \height{x_4} = \inflow{6}) (don't forget to subtract x2\height{x_2} and x4\height{x_4} in Row 1, as solving 2x1=62\height{x_1} = \inflow{6} gives the wrong answer (3,1.5,0,1.5)(3, 1.5, 0, 1.5)):
2x1−12x1−12x1=6⟹x1=6⟹x=(6,3,0,3)\displaystyle \begin{aligned} 2\height{x_1} - \frac{1}{2}\height{x_1} - \frac{1}{2}\height{x_1} &= \inflow{6} \\ \Longrightarrow \quad \height{x_1} &= \height{6} \\ \Longrightarrow \quad \height{x} &= (\height{6}, \height{3}, \height{0}, \height{3}) \end{aligned}
7

A connected planar graph is drawn flat with no crossing edges. Its incidence matrix AA has rank r=5r = 5, and its left nullspace N(AT)\flow{N(A^T)} has dimension 44. Find the number of nodes nn, the number of edges mm, and the total number of faces FF (including the outside region), and verify Euler's Formula.

How does the rank rr of a connected graph relate to the number of nodes nn, and how does dim⁡N(AT)=m−r\dim \flow{N(A^T)} = m - r relate to both the number of edges mm and the number of enclosed interior faces?

Since the graph is connected, r=n−1=5r = n - 1 = 5 gives n=6n = 6 nodes (V=6V = 6). From dim⁡N(AT)=m−r=4\dim \flow{N(A^T)} = m - r = 4, the number of edges is m=5+4=9m = 5 + 4 = 9 (E=9E = 9). The 44 independent loops in N(AT)\flow{N(A^T)} outline 44 interior faces, and adding 11 for the outside region gives F=4+1=5F = 4 + 1 = 5 faces (don't forget the outside region and set F=4F = 4, which gives 6−9+4=16 - 9 + 4 = 1 instead of 22):
V−E+F\displaystyle V - E + F =6−9+5\displaystyle = 6 - 9 + 5 =2\displaystyle = 2