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, 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 and gives the height difference across every pipe.
From a Network to the Incidence Matrix
An arrow on a pipe does not mean water can only flow one way. It only fixes our subtraction order as End−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:
Factor out the node heights into a column vectorPutting −1 in the column of the starting node, +1 in the column of the ending node, and 0 everywhere else builds our 5×4 matrix:
Next, we want to find all tank heights x that give zero height difference across every pipe (Ax=0), leaving the water completely still.
The Nullspace of A and Grounding a Node
Ax1x2x3x4=00000
x=?
Because every row of A has one −1 and one +1 in the columns of the two nodes it connects, giving all four tanks the same height c cancels every difference:
Acccc=cA1111=00000
Since that 1-dimensional line of constant vectors is the entire nullspace of A, a connected network with n nodes always has rank:
rank(A)=n−1
For our 4-node network, rank(A)=4−1=3. To solve for unique heights, we ground one node, such as setting x4=0, which crosses out Column 4 of A and leaves 3 independent columns.
Raising or lowering all four tanks by the same amount c shifts the height vector x by c(1,1,1,1) while leaving all five edge differences Ax=xend−xstart unchanged, and setting all four tanks to the same height always gives 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, at most 3 of the 5 rows of A can be independent. We want to see which edges make the rows of A dependent, and what condition a vector of target height differences b=(b1,b2,b3,b4,b5) must satisfy for Ax=b to have a solution.
Loops, Trees, and Kirchhoff's Voltage Law
Walking around any closed loop brings you back to the starting node, so the rows of A and the height changes b=Ax along that loop must cancel out.
Text solution
Follow the top triangle (1→2→3→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
Follow the bottom triangle (1→3→4→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
Every closed loop in the network creates a linear dependency among its rows in A, and removing loop edges until all four nodes are connected with no loops always leaves a spanning tree of n−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) back to the four nodes using AT, and find which pipe flows can circulate when no external hoses are attached (ATy=0).
Pipe Flows and Kirchhoff's Current Law
In each row of AT, incoming arrows at that node have +1 and outgoing arrows have −1, so multiplying by y gives the net flow arriving at each node:
Setting ATy=0 is Kirchhoff's Current Law: flow into every node equals flow out. Since A has m=5 rows and rank r=3, this left nullspace N(AT) has dimension m−r=5−3=2, and its basis comes from sending water around the two small triangles.
Text solution
Send 1 gal/sec around the top triangle (1→2→3→1)Moving with Edges 1 and 2 (+1) and against Edge 3 (−1) gives the first basis vector for N(AT):
yloop1=11−100
Send 1 gal/sec around the bottom triangle (1→3→4→1)Moving with Edges 3 and 5 (+1) and against Edge 4 (−1) gives the second basis vector for N(AT):
yloop2=001−11
Notice that our two loop equations for b to lie in the column space of A are simply yloop1⋅b=0 and yloop2⋅b=0, showing why the column space C(A) is orthogonal to the left nullspace N(AT).
Any combination of loop flows y=c1yloop1+c2yloop2 keeps the net flow ATy equal to 0 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=f
Now we attach external hoses that pump inflows or drains f=(f1,f2,f3,f4) into the four nodes, and we want a single equation that connects the node heights x directly to the external flows f.
Conductances and the Equilibrium Equation AᵀCAx = 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 measures End−Start while water flows downhill from higher to lower (Start−End=−e), multiplying by the diagonal conductance matrix C=diag(c1,c2,c3,c4,c5) gives the pipe flows:
y=−Ce=−CAx
Match external inflow to net pipe flow leaving each nodeSince ATy calculates Pipe Flow In−Pipe Flow Out, any external flow f pumped into the nodes must leave through the pipes:
−ATy=f
Substitute the pipe flows into the node balancePlugging y=−CAx into −ATy=f cancels the two minus signs:
equilibrium equationATCAx=f
Because every column of AT has one +1 and one −1, adding all the rows of −ATy=f always gives 0 on the left, which forces the entries of f to sum to zero:
f1+f2+f3+f4=0
6
The Graph Laplacian ATA
When every pipe has conductance 1 (C=I), the equilibrium matrix becomes ATA, and we can read its entries straight from the network without multiplying matrices.
The Graph Laplacian AᵀA
A=−10−1−101−10000110−100011
ATA=?
Taking the dot product of each column of A with itself counts how many edges touch that node, and taking the dot product of two different columns gives −1 if an edge connects them and 0 if not:
So the three pipes leaving Node 1 carry 0.5+1.0+2.5=4.0 gal/sec away from the inflow hose, and the two pipes reaching Node 4 deliver 2.5+1.5=4.0 gal/sec to the drain.
Wherever we place the +4 gal/sec inflow hose and −4 gal/sec drain hose (with one node grounded at 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, 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 A 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
1
2
3
4
1
2
3
4
5
Nodes−Edges+Loops=?
For any connected network with n nodes and m edges, the rank of A is r=n−1, and the number of independent loops in N(AT) is m−r=m−(n−1). Rearranging puts all three counts on the left:
Nodes−Edges+Independent Loops=n−m+(m−n+1)=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), so there is one interior face for each independent loop, and counting the outside region around the drawing adds 1 more face to the total number of faces F:
Euler’s FormulaV−E+F=2
In our network, V=4 vertices, E=5 edges, and 2 triangular interior faces plus 1 outside region give F=3 faces, so 4−5+3=2. On a test, remember that F includes the unbounded outside region: if you only count the enclosed interior loops dimN(AT)=m−r, then V−E+Interior Faces equals 1, not 2.
Key concepts
When a problem asks for directed edge differences e=Ax or has pipes with different conductances C=diag(c1,…,cm), build the m×n incidence matrix A by placing −1 at each arrow's starting node and +1 at its ending node (so Edge 1: 1→2 gives row [−1100] and e1=x2−x1). When all pipes have conductance 1 (C=I) and you only need to solve ATAx=f for the node heights, skip building A and write the Graph Laplacian ATA directly from the network: put each node's degree on the diagonal, −1 where two nodes share an edge, and 0 everywhere else.
For any connected network with n nodes and m edges, the nullspace N(A) is the 1-dimensional line of constant vectors x=c(1,…,1). That gives rank(A)=n−1, so any spanning tree of n−1 edges with no closed loop (such as Edges {1,2,4}) is a basis for the row space. A vector b lies in the column space C(A) (Ax=b has a solution) only when the height differences add up to zero around every closed loop (b1+b2−b3=0, Kirchhoff's Voltage Law). Going the other way, ATy gives Pipe Flow In−Pipe Flow Out at each node. The left nullspace N(AT) (ATy=0, Kirchhoff's Current Law) has dimension m−(n−1), with one basis vector per independent loop (such as yloop1=(1,1,−1,0,0)). On a flat planar graph, those m−r loops are the interior faces, and adding 1 for the outside region gives V−E+F=2.
To connect heights to external inflows f, combine y=−CAx and −ATy=f into ATCAx=f, which has a solution only when total inflow equals total outflow (f1+⋯+fn=0). To solve it, ground one node (x4=0) to cross out its row and column. Instead of doing full row reduction, use the shortcut that any node with fi=0 and identical pipes sits at the average height of its neighbors (such as x2=21(x1+x3)), and then find the pipe flows from y=−CAx.
9
Practice
1
A 3-node triangle network has directed edges Edge 1: 1→2, Edge 2: 2→3, and Edge 3: 1→3. Write the 3×3 incidence matrix A, calculate the height difference vector e=Ax when the tank heights are x=(12,5,8), and state whether water in Edge 2 flows with or against the arrow.
For each row of A, which node does the arrow leave (−1) and which node does it enter (+1)? Once you find e2, compare the heights at Nodes 2 and 3 to see which direction is downhill.
Placing −1 at each arrow's start node and +1 at its end node gives the 3×3 incidence matrix A, and multiplying by x=(12,5,8) gives e=Ax:
(Be careful not to subtract Start−End, which flips the signs to (7,−3,4), and do not assume a positive e2=+3 means water flows with the arrow: e2=x3−x2=+3>0 means the pipe goes uphill from Node 2 to Node 3.) Since water flows downhill from Node 3 (8) to Node 2 (5), water in Edge 2 flows against the arrow.
2
In the 4-node, 5-edge network (Edge 1: 1→2, Edge 2: 2→3, Edge 3: 1→3, Edge 4: 1→4, Edge 5: 3→4), explain why Rows 1, 2, and 3 do not form a basis for the row space of A, 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, so a basis must be 3 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). (Be careful not to say every 3-edge subset besides {1,2,3} works: the bottom triangle {3,4,5} also forms a closed loop with Row 3+Row 5−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} and {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). Find the values of b3 and b5 so that Ax=b has a solution, and then find the node heights x when Node 4 is grounded (x4=0).
Walk around the top loop (1→2→3→1) and the bottom loop (1→3→4→1) to write Kirchhoff's Voltage Law for b3 and b5, paying attention to which arrow you walk against.
By Kirchhoff's Voltage Law around the top and bottom loops:
With Node 4 grounded (x4=0), Edge 4 (1→4) gives x4−x1=70. (Watch out for the order of subtraction here: setting x1=70 instead of solving 0−x1=70 flips the sign and gives the wrong heights (70,110,100,0).) Solving from x4=0 gives:
In the same 4-node, 5-edge network with no external hoses (ATy=0), you measure pipe flows y1=3 gal/sec on Edge 1 and y5=−2 gal/sec on Edge 5. Find the remaining pipe flows y2,y3, and y4, and write the vector y as a linear combination of the basis loops yloop1=(1,1,−1,0,0) and yloop2=(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 to find y2 and y4, then use Node 3 to find y3.
Conservation of flow (ATy=0) at Node 2 gives y1−y2=0, so y2=3. At Node 4, both Edge 4 and Edge 5 point into Node 4, so y4+y5=0, giving y4=2 (be careful not to treat one arrow as leaving Node 4, which gives y4=−2). At Node 3, Edges 2 and 3 enter and Edge 5 leaves:
y2+y3−y5⟹3+y3−(−2)⟹y3=0=0=−5
(Don't add y5=−2 instead of subtracting the outgoing arrow, which gives y3=−1.) Matching y1=3 on Edge 1 and y5=−2 on Edge 5 gives:
y=(3,3,−5,2,−2)=3yloop1−2yloop2
5
Suppose the five pipes in our 4-node, 5-edge network have conductances C=diag(2,1,3,1,2) and the node heights are x=(10,6,4,0). Find the pipe flow vector y=−CAx and the external inflow vector f=−ATy=ATCAx, and check that the entries of f add up to 0 so f lies in the column space of AT.
Don't drop the minus sign in y=−Ce, which would make all five flows negative.
Find the five height differences e=Ax first, multiply each by −ck to get yk, and then calculate Pipe Flow Out−Pipe Flow In at each node.
The edge height differences are e=Ax=(−4,−2,−6,−10,−4). Multiplying by −C (don't drop the minus sign in y=−Ce, which would make all five flows negative) gives the pipe flow vector:
Four nodes form a square ring connected by 4 identical pipes of conductance 1 around the outside: (1,2),(2,3),(3,4), and (4,1), with no diagonal pipes. Write the 4×4 Graph Laplacian ATA directly from the network, and solve ATAx=f when 6 gal/sec is pumped into Node 1 and 6 gal/sec is drained from Node 3 (f=(6,0,−6,0)), with Node 3 grounded (x3=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 2, and opposite corners (1,3) and (2,4) share no edge, giving:
ATA=2−10−1−12−100−12−1−10−12
Grounding Node 3 sets x3=0 and crosses out Row 3 and Column 3. Since Nodes 2 and 4 have zero external flow (f2=f4=0), each sits at the average of its neighbors Node 1 and Node 3: x2=21(x1+0)=21x1 and x4=21(x1+0)=21x1. Substituting into Row 1 (2x1−x2−x4=6) (don't forget to subtract x2 and x4 in Row 1, as solving 2x1=6 gives the wrong answer (3,1.5,0,1.5)):
2x1−21x1−21x1⟹x1⟹x=6=6=(6,3,0,3)
7
A connected planar graph is drawn flat with no crossing edges. Its incidence matrix A has rank r=5, and its left nullspace N(AT) has dimension 4. Find the number of nodes n, the number of edges m, and the total number of faces F (including the outside region), and verify Euler's Formula.
How does the rank r of a connected graph relate to the number of nodes n, and how does dimN(AT)=m−r relate to both the number of edges m and the number of enclosed interior faces?
Since the graph is connected, r=n−1=5 gives n=6 nodes (V=6). From dimN(AT)=m−r=4, the number of edges is m=5+4=9 (E=9). The 4 independent loops in N(AT) outline 4 interior faces, and adding 1 for the outside region gives F=4+1=5 faces (don't forget the outside region and set F=4, which gives 6−9+4=1 instead of 2):