Session 12 · Unit 1

Graphs, Networks, Incidence Matrices

Real matrices come from applications, and the best source is a graph. The incidence matrix of a graph carries all its structure, and the four fundamental subspaces turn out to say physical things: the null space is constant potentials, the null space of A transpose is Kirchhoff's Current Law, loops are dependencies, trees are independence — and counting dimensions proves Euler's formula.

▶ Lecture video Session on OCW ↗

Matrices that come from somewhere

Strang opens with a confession. When he needs an example of a null space or a row space, he invents a little matrix on the spot — and he feels a little guilty about it, “because the truth is that real linear algebra uses matrices that come from somewhere.” They come from applications, they have definite structure, and everyone who works with them uses that structure. Chemistry professors row-reduce matrices that record how many molecules of each kind go into a reaction and what comes out. The people at Mathworks build Matlab around exactly these computations.

So today’s lecture is about what Strang calls “the most important model in applied math” — and its discrete version is a graph. A graph is a source of matrices, and the matrix it produces is the star of this lecture.

A graph and its incidence matrix

A graph has nodes and edges. Strang draws a small one: $n = 4$ nodes and $m = 5$ edges. Edge 1 runs from node 1 to node 2, edge 2 from node 2 to node 3, edge 3 from node 1 to node 3, edge 4 from node 1 to node 4, and edge 5 from node 3 to node 4. Each edge gets an arrow — a direction, chosen arbitrarily — so that a current flowing along it counts as positive with the arrow and negative against it. (Real interest would be in the graph of all websites, or all telephones, or all people in the world; four nodes is enough to see everything.)

The language will be electrical — potentials, potential differences, currents — but the same picture describes a hydraulic network carrying water or oil, or a structure like a bridge or a Buckminster Fuller dome.

For Strang’s graph, with five edges and four nodes:

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}

A big graph would give a big matrix — but a very sparse one: every row has exactly two nonzeros, so the number of nonzeros is exactly $2m$ . That is structure, and it can be used.

Notice something already. Edges 1, 2, 3 form a loop in the graph — and look at rows 1, 2, 3 of $A$ : row 1 plus row 2 equals row 3. Loops correspond to linearly dependent rows. Hold that thought.

The null space of A: potentials up to a constant

First question, always: what is the null space? Are the four columns independent? Solve $A\mathbf{x} = \mathbf{0}$ with $\mathbf{x} = (x_1, x_2, x_3, x_4)$ :

A\mathbf{x} = \begin{bmatrix} x_2 - x_1 \\ x_3 - x_2 \\ x_3 - x_1 \\ x_4 - x_1 \\ x_4 - x_3 \end{bmatrix}

The matrix we built computes differences across every edge. Interpret $\mathbf{x}$ as potentials at the nodes; then $A\mathbf{x}$ gives the potential differences across the edges. When are all five differences zero? When all the potentials are equal:

\mathbf{x} = c\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}

So the null space is one-dimensional — the line through $(1, 1, 1, 1)$ — and the rank is $r = n - 1 = 3$ . Any three columns of $A$ are independent.

Physically: the potentials can only be determined up to a constant. Potential differences are what make current flow; if all potentials equal $c$ , nothing moves. It’s the same arbitrary constant as ranking football teams, or measuring temperature in Celsius versus from absolute zero, or the $+c$ in every indefinite integral from calculus. The standard fix is to ground a node — set its potential to zero. That removes one column, the remaining three are independent, and all other potentials can then be computed.

The null space of A transpose: Kirchhoff’s Current Law

Now the equation Strang calls “probably the most fundamental equation of applied mathematics”: $A^T\mathbf{y} = \mathbf{0}$ . Here $A^T$ is $4 \times 5$ , and $\mathbf{y} = (y_1, \ldots, y_5)$ holds the currents on the edges.

Its dimension we know in advance: $\dim N(A^T) = m - r = 5 - 3 = 2$ .

But what does the equation say? Write out the rows of $A^T\mathbf{y} = \mathbf{0}$ :

\begin{aligned} -y_1 - y_3 - y_4 &= 0 \\ y_1 - y_2 &= 0 \\ y_2 + y_3 - y_5 &= 0 \\ y_4 + y_5 &= 0 \end{aligned}

Each equation belongs to a node. The first says the net current leaving node 1 is zero — edges 1, 3, 4 all leave node 1, so $y_1 + y_3 + y_4 = 0$ . The second says $y_1 = y_2$ : current in equals current out at node 2. This is Kirchhoff’s Current Law: a balance equation, a conservation law. Charge doesn’t accumulate at the nodes; it travels around.

Worked example — finding the null space of A transpose from the graph

We could do elimination — the last row of $R$ would be all zeros, since the rank is only 3 — but “here in a real example, we can find them by thinking.” We need two independent current patterns that satisfy KCL. Send one amp around the loop formed by edges 1, 2, 3: take $y_1 = 1$ , then $y_2 = 1$ (forced by node 2), then $y_3 = -1$ to close the loop, with $y_4 = y_5 = 0$ . Any current around a loop satisfies the Current Law. Then send one amp around the loop formed by edges 3, 4, 5: $y_3 = 1$ , $y_5 = 1$ , $y_4 = -1$ .

\mathbf{y}_1 = \begin{bmatrix} 1 \\ 1 \\ -1 \\ 0 \\ 0 \end{bmatrix}, \qquad \mathbf{y}_2 = \begin{bmatrix} 0 \\ 0 \\ 1 \\ -1 \\ 1 \end{bmatrix}

Those are independent — a basis for $N(A^T)$ . What about current around the big outside loop, $(1, 1, 0, -1, 1)$ ? It satisfies KCL too, but it isn’t a third basis vector: it’s the sum of the two loop currents. On the shared edge 3 the currents cancel.

Trees and Euler’s formula

What about the row space of $A$ — the column space of $A^T$ ? Its dimension is the rank, 3. But the first three columns of $A^T$ are not a basis: they correspond to edges 1, 2, 3, which form a loop, and the loop vector in $N(A^T)$ says column 1 plus column 2 equals column 3. The pivot columns are 1, 2, and 4 — edges 1, 2, 4, which form a subgraph with the same four nodes, three edges, and no loop. The independent edges are exactly the ones without a loop.

Now look once more at the dimension formula $\dim N(A^T) = m - r$ , and read every symbol off the graph. The dimension of $N(A^T)$ is the number of independent loops. $m$ is the number of edges. And $r = n - 1$ : the rank is the number of nodes minus one, because of the vector $(1, 1, 1, 1)$ in the null space. So the number of loops equals $m - (n - 1)$ , and rearranging:

Check it on the lecture’s graph: $4 - 5 + 2 = 1$ . Strang draws a messier graph with five nodes, seven edges, three loops: $5 - 7 + 3 = 1$ . “And Euler’s right, I always get one.” Euler’s formula is a great fact of topology, true for any graph — and linear algebra proves it, just by computing the dimension of $N(A^T)$ two ways. “We see Euler again — that guy never stopped.”

The framework of applied mathematics

The lecture closes with the picture Strang calls the great picture of applied mathematics, built from three steps.

Start with the potentials $\mathbf{x}$ at the nodes. First, $A$ computes potential differences across the edges:

\mathbf{e} = A\mathbf{x}

Second, Ohm’s Law: the current on an edge is a number — the conductance, one over the resistance — times the potential drop. A diagonal matrix $C$ of physical constants connects them:

\mathbf{y} = C\mathbf{e}

Third, Kirchhoff’s Current Law balances the currents at the nodes. With no outside source, $A^T\mathbf{y} = \mathbf{0}$ . To make something actually happen, add external current sources $\mathbf{f}$ going into and out of the nodes (batteries in the edges are the other option), and KCL becomes $A^T\mathbf{y} = \mathbf{f}$ .

Chain the three steps together — multiply by $A$ , then $C$ , then $A^T$ — and you get the basic equation of applied math in equilibrium (no time, no Newton’s law; everything has settled down):

A^T C A\,\mathbf{x} = \mathbf{f}

Rectangular matrices came from the real application, but they arrive together with their transposes — which is exactly why the four subspaces are the right things to know. Strang’s final question: what can you say about the matrix $A^T C A$ , or even $A^T A$ ? It is always symmetric.

Back of the chalk tray — what to remember

The incidence matrix of a graph has a row per edge ( $-1$ leaves, $+1$ enters) and a column per node; it is very sparse, with exactly $2m$ nonzeros.
$A\mathbf{x}$ computes potential differences across edges. $N(A)$ is the line of constant vectors $c(1, \ldots, 1)$ , so $r = n - 1$ and potentials are determined only up to a constant — fix it by grounding a node.
$A^T\mathbf{y} = \mathbf{0}$ is Kirchhoff’s Current Law: current balances at every node. $\dim N(A^T) = m - r$ equals the number of independent loops, and loop currents form its basis.
Loops in the graph correspond to dependent rows of $A$ ; the pivot edges form a tree, a graph with no loops.
Counting $\dim N(A^T) = m - r$ two ways proves Euler’s formula: nodes $-$ edges $+$ loops $= 1$ .
The framework of applied math: $\mathbf{e} = A\mathbf{x}$ (differences), $\mathbf{y} = C\mathbf{e}$ (Ohm’s Law), $A^T\mathbf{y} = \mathbf{f}$ (balance), combining into $A^T C A\,\mathbf{x} = \mathbf{f}$ , with $A^T C A$ always symmetric.

Problems

Work these before revealing the solutions — everything you need is in the lecture.

Problem 12.1 Building an incidence matrix

A directed graph has 3 nodes and 3 edges: edge 1 from node 1 to node 2, edge 2 from node 2 to node 3, edge 3 from node 1 to node 3. Write the incidence matrix $A$ , find its rank, and give a basis for $N(A)$ . Which rows are dependent, and why does the graph tell you so before any elimination?

Show solution

A = \begin{bmatrix} -1 & 1 & 0 \\ 0 & -1 & 1 \\ -1 & 0 & 1 \end{bmatrix}

$A\mathbf{x} = (x_2 - x_1,\ x_3 - x_2,\ x_3 - x_1)$ , which is zero exactly when $x_1 = x_2 = x_3$ . So $N(A)$ has basis $(1, 1, 1)$ , its dimension is 1, and the rank is $r = n - 1 = 2$ .

The three edges form a loop, so the rows must be dependent: row 1 plus row 2 equals row 3. One loop, and indeed $m - r = 3 - 2 = 1$ dependency.

Problem 12.2 Kirchhoff by thinking, not eliminating

A directed graph has 4 nodes and 5 edges: edge 1 from node 1 to node 2, edge 2 from node 2 to node 3, edge 3 from node 3 to node 4, edge 4 from node 4 to node 1, and edge 5 from node 1 to node 3 (a diagonal). Without elimination, find the dimension of $N(A^T)$ and write down a basis of loop currents. Then express the current around the outer loop (edges 1, 2, 3, 4) in terms of your basis.

Show solution

Here $n = 4$ , $m = 5$ , so $r = n - 1 = 3$ and $\dim N(A^T) = m - r = 5 - 3 = 2$ : two independent loops.

Loop A uses edges 1, 2, 5: one amp along edge 1, then edge 2, returning against edge 5’s arrow gives

\mathbf{y}_A = (1, 1, 0, 0, -1)

Loop B uses edges 5, 3, 4: one amp with edge 5, then edges 3 and 4, gives

\mathbf{y}_B = (0, 0, 1, 1, 1)

Both satisfy current balance at every node.

The outer loop sends one amp along edges 1, 2, 3, 4: $(1, 1, 1, 1, 0)$ . That is exactly $\mathbf{y}_A + \mathbf{y}_B$ — the currents on the shared diagonal edge 5 cancel, so the outer loop is dependent, not a third basis vector.

Problem 12.3 Euler's formula as dimension count

A connected graph has 6 nodes and 9 edges. (a) What is the rank of its incidence matrix $A$ ? (b) What is $\dim N(A^T)$ , and how many independent loops does the graph have? (c) How many edges must you remove to leave a tree, and how many edges does that tree have?

Show solution

(a) The rank is $r = n - 1 = 5$ : the only dependency among the columns is the constant vector $(1, \ldots, 1)$ in $N(A)$ .

(b) $\dim N(A^T) = m - r = 9 - 5 = 4$ , so there are 4 independent loops. Check with Euler: nodes $-$ edges $+$ loops $= 6 - 9 + 4 = 1$ . ✓

(c) A tree has no loops, so removing one well-chosen edge per independent loop — 4 edges — leaves a tree with $9 - 4 = 5$ edges. That matches the general fact: a tree on $n$ nodes has $n - 1$ edges, exactly the rank of $A$ .

Problem 12.4 The symmetric product

Let $A$ be any $m \times n$ incidence matrix and $C$ a diagonal matrix of positive conductances. (a) Show that $K = A^T C A$ is symmetric. (b) For the 3-node loop graph of Problem 12.1 with $C = I$ , compute $A^T A$ and identify the vector in its null space. What does that mean for solving $A^T C A\,\mathbf{x} = \mathbf{f}$ ?

Show solution

(a) Transpose the product, reversing the order: $K^T = (A^T C A)^T = A^T C^T (A^T)^T = A^T C A = K$ , since the diagonal matrix satisfies $C^T = C$ . So $K$ is symmetric — always.

(b) With $A$ from Problem 12.1:

A^T A = \begin{bmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{bmatrix}

Each row sums to zero, so $(1, 1, 1)$ is in the null space of $A^T A$ — the same constant vector that was in $N(A)$ . The matrix is singular, which says the potentials are only determined up to a constant. To solve $A^T C A\,\mathbf{x} = \mathbf{f}$ in practice, ground a node: fix one potential at zero, delete that row and column, and the remaining system is invertible.