What a map throws away

A matrix is a picture of what a linear map does to the grid, and the determinant says by how much it multiplies area. Both of those descriptions quietly assume the map does not destroy anything. When the determinant is zero they stop being informative — area multiplied by zero is zero, and that single number cannot distinguish a map that flattens the plane onto a line from one that crushes it to a point.

What separates those two cases is not a measurement of area at all. It is a count of dimensions.

Two lines are visible in that picture and they do different jobs. The one on the left is everything the map destroys. The one on the right is everything the map produces. The first is called the kernel and the second the image, and the theorem this essay is about says their dimensions add to two.

Where the lost line comes from #

The matrix drawn above sends the point (x, y) to (2x + y, 4x + 2y). The second coordinate is exactly twice the first, whatever the input, so every output lies on the line where the second coordinate is double the first. That is the image, and it is one-dimensional.

For the kernel, ask which inputs give (0, 0). The condition 2x + y = 0 forces y = −2x, and the second equation 4x + 2y = 0 says the same thing again — it is the first multiplied by two and carries no new information. So the inputs killed by the map are the multiples of (1, −2), which is a line.

Both lines were found by solving rather than by looking, and the figure checks them by trying: forty points along the kernel line are pushed through the map and required to land within a millionth of a millionth of the origin, and six hundred points scattered over the plane are pushed through and required to land on the image line to the same tolerance.

The redundancy in the two equations is the whole phenomenon. The rows of the matrix are not independent; the second says nothing the first did not. One equation, one constraint, one dimension removed.

It is worth noticing how little of the plane the map’s failure is visible in. A reader shown only the image of a single point, or of a small patch away from the origin, would see a perfectly ordinary point or patch and nothing amiss. What gives the collapse away is a comparison: two points that started in different places arriving at the same place. A map is not invertible precisely when it identifies things, and identification is a relation between two inputs rather than a property of one — which is why the kernel, a set of inputs that all arrive together at the origin, is the right object to name.

A projection is the clearest case to hold on to, because both counts are obvious in advance. Projecting the plane onto a line keeps one dimension and destroys one, and the dot product is exactly the machinery that computes what survives. Every singular map of the plane is a projection followed by a stretch of the line it lands on, which makes the general case less exotic than the picture suggests.

The two counts, and why they add #

The rank of a map is the dimension of its image: how many directions of output are actually reachable. The nullity is the dimension of its kernel: how many independent directions of input are destroyed.

The rank-nullity theorem says the two always add to the dimension of the space being mapped from. In the plane, rank 2 and nullity 0, or rank 1 and nullity 1, or rank 0 and nullity 2 — and no other combination.

The reason is a bookkeeping argument that is easier than it looks. Choose a basis for the kernel — a set of independent directions that are all destroyed. Extend it to a basis for the whole space by adding more directions until every direction is a combination of them. Then the images of the added directions span the image, and they are independent, so they are a basis for it. The count of added directions is the rank, the count of kernel directions is the nullity, and together they are the count of directions in the space.

Every step of that argument is about counting basis vectors and none of it is about the plane in particular. It works in three dimensions, in ten, and for the spaces of functions where linear algebra earns most of its living.

What zero determinant was hiding #

For a map of the plane, the determinant tells the whole story of whether anything is lost — non-zero means rank 2, zero means rank at most 1 — and this is the coincidence that makes two dimensions a poor guide to the general case.

In three dimensions a matrix with determinant zero could have rank 2, flattening space onto a plane, or rank 1, flattening it onto a line, or rank 0. One number cannot report which. And in a rectangular case — three inputs and two outputs, say — there is no determinant to compute at all, while rank and nullity are perfectly well defined and still add to three.

So the determinant is not a weaker version of the rank. It is a different quantity that happens to answer the same yes-or-no question in the square case, and it stops being able to answer it as soon as more than one dimension can be lost.

The rank is the number of independent columns #

There is a second reading of the rank that is more useful for computing and just as visual.

The columns of a matrix are the images of the basis vectors, and the image of the map is everything that can be built from those images. So the rank is the number of independent columns, and for the singular matrix above the two columns are (2, 4) and (1, 2), which are multiples of each other. One independent column, rank one.

The same count taken along the rows gives the same answer — the row rank and the column rank of any matrix are equal, which is a genuinely surprising fact that no picture makes obvious and every treatment of the subject proves early. The rows of the singular matrix are (2, 1) and (4, 2), again multiples, again one independent row. That the two counts always agree, for any matrix of any shape, is what makes it possible to speak of the rank at all.

What the kernel says about solving #

The most common reason to want any of this is that a system of equations has to be solved, and the two counts answer both of the questions a solver asks.

A system asks for the inputs a map sends to a particular target. If the target is outside the image there are no solutions at all, and whether it is outside the image is a question about the rank. If the target is inside the image there is at least one solution, and then every solution is that one plus anything in the kernel — because adding something the map destroys cannot change where the answer lands.

So the solution set, when it is not empty, is a copy of the kernel shifted to sit on one solution. Nullity zero means the answer is unique; nullity one means a line of answers; nullity two means a plane of them. The two counts between them say whether a system is solvable and how badly under-determined it is, and neither question has anything to do with the numbers on the right-hand side.

That last figure is the reason the singular case deserves attention out of proportion to how rare it looks. Eigenvectors are defined by an equation whose whole content is that a certain map has a non-trivial kernel: a number λ is an eigenvalue exactly when the map M − λ has something other than the origin sent to the origin. Every eigenvalue computation is a hunt for the values of a parameter at which a determinant becomes zero, which is to say a hunt for the parameter values that make the rank drop. The degenerate case is not a corner of the theory; it is where the theory’s most-used quantity is defined.

Where it fails to be a useful description #

The theorem is exact and the trouble is entirely in getting the numbers.

Rank is a discontinuous function of a matrix. Change the entry 2 in the singular matrix above to 2.000001 and the determinant becomes small but non-zero, so the rank jumps from one to two and the kernel vanishes. Nothing about the map has meaningfully changed; the plane is still very nearly flattened, and every computation involving it will behave as though a dimension has been lost.

That is a serious practical problem rather than a technicality, and it is why numerical work replaces the rank with a graded quantity — a list of singular values, each saying how much survives in one direction — rather than a count. Deciding where in that list to draw the line between “kept” and “lost” is then a judgement, and the judgement depends on the accuracy of the numbers being fed in. Rank as an integer is a fact about exact arithmetic and nothing else.

The clean statement and the messy computation sit either side of a boundary that runs through a good deal of applied mathematics: the theorem is about a matrix, the difficulty is about a matrix that came from measurements.

What it costs #

Rank is computed by elimination: sweep the matrix into a staircase shape and count the rows that survive with a leading entry. For an n by n matrix that costs about n³/3 operations, the same as solving a system, and it gives the kernel as a by-product — the free columns of the staircase are exactly the directions that can be varied without changing the output.

Computing the determinant to decide invertibility, by contrast, is a bad idea for anything but the smallest matrices. Its size scales like the nth power of the entries, so it overflows or underflows long before the matrix is large, and a determinant of 10⁻²⁰ is not evidence of anything at all when the matrix is a hundred by a hundred. Elimination answers the same question, in the same time, without producing a number too large to hold.

That distinction is one worth stating plainly, since the determinant is often taught as the test for invertibility: it is the test for a matrix written on paper, and elimination is the test for a matrix in a machine.

What the picture cannot show #

The figures here are all two-dimensional, and two dimensions is the one case where the whole subject collapses into a single number. Everything genuinely interesting about rank happens when there are several dimensions to lose and the determinant can no longer say how many went.

Nor can the drawings show the kernel of a map between spaces of functions, which is where the theorem does its most useful work. Differentiation is a linear map, its kernel is the constants — one dimension, the reason an antiderivative is only determined up to a constant — and its image is everything, so the rank is infinite and the counting has to be done with more care than the finite argument above allows.

And there is a rank the figure cannot draw at all. A map from three dimensions to two has a kernel that is a line and an image that is the whole target: nothing about the picture of a square becoming a parallelogram suggests that a whole line of space is being discarded on the way.

The ladder from here #

Rungs above: the rank-nullity theorem stated for a map between different spaces, where the count is of the source’s dimension and not the target’s. Row rank equals column rank, proved rather than reported. The four fundamental subspaces — kernel, image, and the two belonging to the transpose — and the right angles between them. Elimination as the algorithm that produces all four at once. The singular value decomposition, where the sharp count of dimensions becomes a graded list and the directions a map leaves alone reappear as its two sets of axes. Least squares, which is what to do when the system has no solution because the target lies outside the image. And the same theorem in a different subject entirely: for a graph, the number of independent cycles and the number of independent cuts add to the number of edges, which is rank-nullity applied to a matrix built from the graph’s incidences.

The shape of the idea #

Two quantities that add to a fixed total is one of the most reliable patterns in mathematics, and it is worth collecting the instances.

Here it is dimensions kept and dimensions lost. In Euler’s formula it is corners and faces against edges. In Pick’s theorem it is interior points and boundary points against area. Each time, a quantity that was hard to see directly is pinned down by an accounting identity, and each time the identity is proved by finding a way to count the same thing twice.

What makes this instance carry more weight than most is that neither side of it is a number that was being sought. Nobody sets out to measure the dimension of a kernel. It is the accounting that makes the kernel worth naming — once the two dimensions have to add to a known total, finding either one determines the other, and a map’s failure to be invertible becomes something quantitative rather than a fact about a determinant being zero.