The cycles and the cuts

The rank–nullity count is a statement about arrays: what a map kills and what it keeps add to the dimension it started from. Nothing in it mentions where the array came from, and the most instructive place to apply it is one where nobody would have built an array on purpose.

Take a graph, and write down a matrix with a row for every edge and a column for every point, carrying a $-1$ at the edge’s start and a $+1$ at its end.

Rank plus nullity is a statement about whichever space the map starts from, and this array can be read from either end — which is where the theorem comes from. Read it as acting on edge-labellings and its nullity is the number of independent cycles while its rank is the number of independent cuts, and they add to the number of edges.

What the two spaces are #

The array is $E \times V$: it acts on assignments of a number to each point and produces an assignment of a number to each edge. Read that way, an input is a potential — a value at every point — and the output is the difference across each edge. So the image is the space of edge-labellings that arise as potential differences, and the kernel is the space of potentials that are flat across every edge.

The transpose is where the interesting space lives. It acts on assignments of a number to each edge — a flow — and produces, at each point, the net amount arriving. So its kernel is the space of flows that balance everywhere: the circulations.

Two names for the two spaces:

The cycle space is the kernel of the transpose — flows with no net accumulation at any point. Walking round a cycle and putting $+1$ on each forward edge and $-1$ on each backward one gives such a flow, and those generate the space.

The cut space is the image of the original array — the potential differences. Assigning $1$ to the points on one side of a division and $0$ to the rest gives a labelling that is $\pm 1$ on the edges crossing the division and $0$ elsewhere, which is a cut, and those generate it.

Rank–nullity applied to the transpose says $\dim(\text{cut space}) + \dim(\text{cycle space}) = E$.

Both counts, from the drawing #

The dimensions have formulas and each is computable by walking the graph, which is what makes the theorem checkable rather than merely stated.

The rank is $V - c$, where $c$ is the number of connected pieces. A potential is flat across every edge exactly when it is constant on each piece, so the kernel of the original array has dimension $c$ — one free value per piece — and the rank is $V - c$.

The nullity of the transpose is $E - V + c$, by subtraction. That number is the cyclomatic number or first Betti number, and it counts the independent cycles: take a spanning forest, which uses $V - c$ edges, and each of the remaining $E - V + c$ edges closes exactly one cycle.

Disconnecting the graph changes the rank and not the arithmetic, which is what the count of components in the formula is for.

The right angle between them #

There is more structure than the dimensions, and it is the part that makes the pair of spaces natural rather than two answers that happen to add up.

The cycle space and the cut space are orthogonal complements inside the space of edge-labellings. A circulation and a cut have dot product zero, and the reason is a conservation statement: a cut’s labelling is $\pm 1$ on the edges crossing a division, and a circulation crosses any division as much one way as the other, so the terms cancel.

That is the four-subspaces picture with the two subspaces of the target being the two things a graph is made of. The edges split into circulations and potential differences, at right angles, and every edge-labelling is uniquely one of each.

The decomposition has a name outside this subject — the discrete Hodge decomposition — and the continuous version of it is the statement that a vector field splits into a curl-free part and a divergence-free part, which is a theorem of a completely different-looking kind.

It is worth noticing what the right angle is a right angle in. The space of edge-labellings has a dot product only because a basis has been chosen — one coordinate per edge — and that choice is natural here in a way it usually is not: the edges are a set, and a set has a canonical basis. The perpendicularity is therefore a genuine feature of the graph rather than an artefact of coordinates, which is not true of most orthogonality statements in linear algebra and is why this one carries content.

Working the smallest case by hand #

The hero figure’s graph is small enough to do completely, and doing it once makes the two spaces concrete.

Four points $a, b, c, d$ and five edges: $ab$, $bc$, $ca$, $cd$, $da$. The matrix has five rows and four columns, with a $-1$ and a $+1$ in each row.

The kernel of the original map is the potentials flat across every edge. Since the graph is connected, that is the constants: one dimension. So the rank is $4 - 1 = 3$.

The cycle space therefore has dimension $5 - 3 = 2$, and the two circulations are easy to name: round the triangle $a \to b \to c \to a$, and round the triangle $a \to c \to d \to a$. Any balanced flow is a combination of those two, and a third cycle — the outer quadrilateral $a \to b \to c \to d \to a$ — is their sum rather than a new direction, which is exactly what independent is measuring.

The cut space has dimension three, and a basis is the three divisions that isolate one point at a time: $\{a\}$, $\{b\}$, $\{c\}$. Isolating $d$ gives a cut that is the negative of the sum of those three, for the same reason the constants are the kernel — the four one-point cuts add to nothing.

Two plus three is five. Each number was obtained from the drawing and neither consulted the other, which is the whole check the figures run at every graph.

Where it settles something #

Circuits. A network of resistors is an edge-labelling problem: currents are a flow and voltages are a potential difference. Kirchhoff’s current law says the current is a circulation; his voltage law says the voltage drops are a potential difference; and the two laws are exactly lies in the cycle space and lies in the cut space. Kirchhoff wrote this down in 1847, seventy years before anybody called it linear algebra, and the count $E - V + 1$ is the number of independent loop equations a circuit needs — which is what a student is taught to find by inspection and what the nullity computes.

Spanning trees. The rank $V - c$ is the size of a spanning forest, which is why the greedy algorithms for minimum spanning trees terminate where they do: a forest is an independent set in the cut space’s matroid, and independence there is exactly contains no cycle. Counting spanning trees by a determinant is the next fact along, and it is about the same matrix — the determinant in question is of the incidence matrix times its transpose with one row and column deleted.

Planarity and duality. For a graph drawn in the plane without crossings, the cycle space of the graph is the cut space of its dual and the other way round. So the two spaces exchange, the numbers $E - V + c$ and $V - c$ exchange, and Euler’s formula falls out of the exchange being consistent — which is the corner count arriving from linear algebra rather than from counting faces.

What is being borrowed, and what is not #

It is worth being careful about what the array reading supplies, because it is easy to overstate.

It supplies the dimensions and the complementarity for free. That independent cycles and independent cuts add to the edge count is rank–nullity and nothing else, and it needs no argument about graphs at all.

It does not supply a basis. A basis of the cycle space is a set of $E - V + c$ independent circulations, and producing one means finding a spanning forest and using the remaining edges — a graph algorithm. The linear algebra says how many and is silent about which.

And which basis is chosen matters for everything downstream: a spanning tree picked one way gives short fundamental cycles and picked another gives long ones, and a circuit solver’s numerical behaviour depends on it. Choosing a tree to make the cycles small is a real optimisation problem that the dimension count cannot see at all.

And it does not see everything the graph has. Two graphs with the same incidence matrix up to relabelling are isomorphic, so nothing is lost in principle; but the rank is a very coarse summary, and two completely different graphs with the same $V$, $E$ and $c$ have identical numbers here. The array reading answers questions about dimension and no others.

That division is the usual one when a combinatorial object is handed to linear algebra. The counting comes free and the construction does not, which is the same trade a character sum makes in a different subject: a formula that computes a number and produces none of the objects it counts.

Over which numbers, and why it matters here #

Everything above is over the rational numbers, and changing that changes which theorem is obtained — which is unusual for a construction this simple and is worth a paragraph.

Over the two-element field the signs disappear, since $+1$ and $-1$ are the same thing. The incidence matrix becomes a matrix of ones and zeros, the cycle space becomes the even subgraphs — sets of edges with every degree even — and the cut space becomes the edge cuts. The dimensions are unchanged, $E - V + c$ and $V - c$, and the theorem reads the same.

But the objects are different. Over the rationals a cycle is a flow with a direction and a magnitude; over the two-element field it is a set of edges, and orientation has no meaning. The even subgraphs of a graph are exactly the ones that admit a closed walk using every edge, so the two-element version of this theorem is where Euler’s criterion lives — and the rational version has nothing to say about walks at all.

That both versions have the same dimensions is not automatic, and it fails for a general matrix: rank over the rationals and rank over a finite field can differ, because a determinant can be a non-zero integer divisible by the field’s characteristic. What rescues the incidence matrix is that it is totally unimodular — every square submatrix has determinant $0$ or $\pm 1$ — so no minor can vanish modulo anything without vanishing outright. That is the same property that makes a bipartite assignment problem’s corners whole, arriving here as the reason two ranks agree.

Where the same count is already familiar under another name #

The number $E - V + c$ turns up in several places in this collection and in one place outside it, and collecting them is the fastest way to see that it is a dimension rather than a formula.

A maze has one route if and only if it has no cycles. A maze whose graph is a tree has $E = V - 1$ and nullity nought, so any two points are joined by exactly one path; adding one corridor adds one independent cycle and one alternative route. The count of independent cycles is the count of genuinely different ways to go round.

A circuit’s loop equations. Named above, and worth repeating because it is the place the number is used daily: an engineer analysing a network writes $E - V + 1$ loop equations, and that is a dimension rather than a rule of thumb.

A program’s branch structure. The cyclomatic complexity of a piece of code is $E - V + 2$ on its control-flow graph, introduced by McCabe in 1976 as a measure of how many independent paths through it there are. The $+2$ rather than $+1$ is a convention about adding an edge from exit back to entry; the quantity is this essay’s nullity.

And a surface’s first Betti number. For a graph drawn on a surface, $E - V + c$ is the rank of the first homology group of the graph as a topological space — which is the same count with the word dimension replaced by rank of an abelian group, and it is where this whole construction points.

The pattern in all four is worth naming. Each is a count of independent alternatives, and in each case the naive count — of cycles, of loops, of paths — is too large because the alternatives are not independent. The dimension is the honest number, and getting it needs the linear structure rather than the drawing.

Neither space appears in any figure #

The two spaces are drawn as numbers and not as objects. The figures give the rank and the nullity and mark the matrix’s entries; neither a circulation nor a cut appears in any of them. A figure showing a basis of the cycle space would be a picture of the graph with cycles marked, and it is a different figure from the one that establishes the count.

The orthogonality is stated and not measured. That a circulation and a cut are perpendicular is argued in the prose; no figure computes a dot product. It would be an easy thing to check and it is not what these figures are of.

And every graph here has at most six edges. The formula $E - V + c$ is uninteresting at that size — a reader can count the cycles directly — and it is the only available way to answer the question at a size where nobody can. The figures show the mechanism where the mechanism is unnecessary, which is the standing limitation of drawing a general theorem.

Still open here: how much of a graph its matrix knows #

The rank sees very little. Two graphs are hard to tell apart by any single number, and the natural refinement — the eigenvalues of the incidence matrix’s product with its transpose, which is the Laplacian — sees a great deal more: it gives the spanning-tree count, bounds on connectivity, and the mixing time of a random walk.

It does not see everything. There are non-isomorphic graphs with identical Laplacian spectra, and how common they are is an old and unsettled question; the current guess, from computation rather than proof, is that almost all graphs are determined by their spectrum, and nobody can prove that almost any are.

The other direction leads where all of this was always going: the incidence matrix is the boundary map of a one-dimensional complex, its cycle space is the first homology, and the whole apparatus generalises to surfaces and higher dimensions — where rank–nullity becomes the statement that homology is the kernel modulo the image, and the Euler characteristic is an alternating sum of these ranks.

A theorem borrowed from nowhere #

The habit is the one worth taking from all of it.

Rank–nullity is a fact about arrays and it is proved with no example in mind. Handing it a matrix somebody built for a completely different reason — because a graph has edges and points and a sign is the natural thing to put at each end — produces a theorem about drawings that would be a real piece of work to prove directly.

The transfer costs nothing and it is not luck. It works because the graph’s structure was genuinely linear to begin with: flows add, potentials add, and the constraint that a flow balances is linear in the flow. The array was not imposed on the graph; it was the graph’s own arithmetic written down.

So the question to ask of any combinatorial object is which of its constraints are linear, and to write the array those constraints define. The counting theorems then apply for free, and the answers are usually the quantities the subject had already named by hand.