Counted across and counted down

What a map throws away works in two dimensions, where a matrix is square and the two ways of reading it — as rows and as columns — are hard to keep apart. Take a rectangular array and they come apart immediately.

Three rows of four. The rows are three vectors in a four-dimensional space, and asking how many are independent is a question about that space. The columns are four vectors in a three-dimensional space, and asking how many those are independent is a question about a different space of a different size, answered by a different computation.

There is no obvious reason for that, and it is one of the few facts in elementary linear algebra where the surprise survives knowing the proof.

Making the surprise clear #

It is worth stating how little the two questions have in common before the answer makes it look inevitable.

Take an array with $m$ rows and $n$ columns. The row rank is the dimension of the span of the $m$ row vectors, which live in $\mathbb{R}^n$. The column rank is the dimension of the span of the $n$ column vectors, which live in $\mathbb{R}^m$.

For a three-by-four array, the first is a number between $0$ and $3$ computed about a subspace of four-dimensional space; the second is a number between $0$ and $4$ computed about a subspace of three-dimensional space. Neither number’s range even matches the other’s. That both are at most $3$ is already a consequence of the theorem rather than an observation.

And the computations are genuinely separate. Eliminating down the rows adds multiples of rows to rows and never touches a column as an object; eliminating on the transpose does the reverse. The figures here run both, in exact fractions, and compare.

The proof, in the shape of a factorisation #

The argument that makes it inevitable is not an elimination at all; it is a statement about what a rank-$r$ array looks like.

Suppose the column rank is $r$. Then $r$ of the columns span all of them, so every column is a combination of those $r$. Write the chosen columns as an $m \times r$ array $B$, and the coefficients as an $r \times n$ array $C$; then $A = BC$.

Now read that product the other way. The rows of $A$ are combinations of the rows of $C$ — row $i$ of $BC$ is $\sum_k B_{ik} \cdot (\text{row } k \text{ of } C)$ — and there are $r$ rows of $C$. So the row rank is at most $r$, which is the column rank.

Apply the same to the transpose and the inequality reverses. So the two are equal, and the whole proof is the observation that a factorisation through an $r$-dimensional space constrains both readings symmetrically.

That is the content worth carrying: the rank is the smallest number of dimensions a map can be routed through. Rows and columns are two ways of looking at the routing, and the routing has one size.

What the number is about #

Read as a map rather than an array, the three descriptions coincide and each is useful somewhere.

The dimension of the image. The map sends $\mathbb{R}^n$ somewhere in $\mathbb{R}^m$, and what it reaches is a subspace of dimension $r$ — the span of the columns, since the columns are the images of the axis vectors.

The dimension of the row space. Equivalently, the number of genuinely different linear conditions the array imposes. A system $Ax = b$ has $r$ independent equations in it however many rows are written.

The size of the smallest factorisation. As above.

The number of independent directions the image keeps. Which is the same reading the square case gives when a matrix is looked at as an instruction for redrawing the grid: the rank is how many dimensions the redrawn grid still spans.

And $n - r$ is the nullity, the dimension of what the map kills. What a map throws away states rank plus nullity equals the source’s dimension in the square case; the rectangular statement is the same and the number to add to is the column count, not the row count — which is the one place the asymmetry of a rectangular array survives into the theorem.

Where the equality fails #

The theorem has no exceptions over a field, and that is worth testing against the places it looks as though it might.

Over the whole numbers it is still true, because rank is about spans over the fractions and a whole-numbered array is a fraction-numbered one. What is different is the finer structure — a whole-numbered array has a Smith normal form with divisibility conditions that a field cannot see — and none of it touches the rank.

Over a finite field it is true, and the proof above goes through unchanged, since it used nothing but linear combination. That matters in practice rather than as a curiosity: an error-correcting code is a subspace over a two-element field, its dimension is a rank, and the parity-check matrix’s rank is what says how many errors such a code can locate.

Over a ring with zero divisors it can fail, and that is the honest limit. The proof needs to choose $r$ spanning columns and express the others in terms of them, which requires dividing; in a ring where division is unavailable, several competing notions of rank appear and they disagree.

And in floating point it is meaningless. A rank is a count of exactly-zero rows, and after elimination in doubles nothing is exactly zero. Numerical practice replaces the question with a different one — how many singular values exceed a threshold — which is a genuinely different quantity with a tolerance in it, and it answers a question about how close the array is to one of lower rank rather than what its rank is. That is why every computation on this page is done in exact fractions, and it is not fussiness: the same array eliminated in doubles reports rank three about as often as rank two, depending on the order of operations.

The other half of the count is the part the square case draws directly, and it is worth seeing once before the rectangular version separates the two spaces it lives in.

The elimination, and why it is allowed #

There is a step every computation above takes without comment and it is the one the theorem’s usual proof turns on.

Row operations do not change the row space, since each replaces a row by a combination of rows and is reversible. So the row rank is unchanged.

Row operations do not change the column rank either, and this is less obvious. What they preserve is the set of dependencies among the columns: if some combination of columns is zero, the same combination of the reduced array’s columns is zero, because the operation acted on each column identically. So the columns’ independence pattern is untouched, and with it their rank.

Put those together and row reduction changes neither count. Reduce until the array is in echelon form, where the row rank is the number of non-zero rows and the column rank is the number of pivot columns — and those are the same number by inspection, since each non-zero row has exactly one pivot.

That is the standard proof and it is shorter than the factorisation argument. What it is not is explanatory: it establishes the equality by transporting both quantities to a form where they coincide, and gives no account of what they are both measuring. Both proofs are worth having and they answer different questions — one says yes, and the other says because the map factors through a space of that size.

The same fact in three other places #

The equality shows up under other names, and recognising them is worth more than the theorem.

The dimension of a space of solutions. A homogeneous system with $n$ unknowns and rank $r$ has a solution space of dimension $n - r$, whichever way the equations were written down. Adding a redundant equation changes the row count and not the rank, so it changes nothing — which is the statement that the count of equations is not a meaningful quantity and the rank is.

The size of a minimal generating set. The row space and the column space have the same dimension, so the smallest number of vectors needed to generate the image equals the smallest number of conditions needed to define it. Generating and constraining are dual descriptions of the same subspace, and they have the same complexity.

A decomposition into simple pieces. The factorisation $A = BC$ writes the array as a sum of $r$ products of a column by a row, each of which is an array of rank one. So the rank is the fewest rank-one arrays that add to it — and rank-one arrays are exactly the ones that are a single outer product, which is the smallest non-trivial thing an array can be. That reading is what the singular value decomposition sharpens into a graded list rather than a count.

And a bilinear form’s rank. A function $f(x, y)$ linear in each argument is given by an array; its rank is the least number of terms $\sum_k g_k(x) h_k(y)$ needed to write it. That number is symmetric in $x$ and $y$ by inspection of the expression, and the row-equals-column theorem is exactly that symmetry translated back.

The last reading is the one that makes the theorem look obvious, and it is worth noticing that it does so by moving to a description in which the two variables are visibly on the same footing. The surprise in the matrix version is an artefact of writing rows above columns, which is a fact about notation.

A rank is a distance, not only a count #

There is a reading of the number that the counting version hides, and it is the one that makes rank useful for anything approximate.

An array of rank $r$ lies in the set of arrays of rank at most $r$, which is a subset of all arrays — not a subspace, but a set with dimension and shape. Arrays of rank at most one form a surface; those of rank at most two a larger one; and the full-rank arrays are everything else, which is almost everything.

So asking for an array’s rank is asking which of these nested sets it sits in, and asking how far it is from the next one down is a meaningful question with a numerical answer. That answer is the smallest singular value, and it is what a numerical library computes when it is asked about rank — a distance rather than a count.

The counting version and the distance version answer different questions and the distance version is the robust one. An array of rank two that is perturbed by one part in a million has rank three and is a millionth of the way from rank two, and only the second statement is useful. The theorem of this essay is about the first, and everything in it is exact because the first is the only version that is exact.

Where it stops being true one dimension up #

The pleasant symmetry ends immediately if the array gains an index, and that is the sharpest available evidence that it was not obvious.

A three-dimensional array — entries $T_{ijk}$ — has three ways of being sliced and therefore three ranks, one per direction. They can all be different. And the factorisation reading, the smallest $r$ with $T = \sum_{k=1}^{r} a_k \otimes b_k \otimes c_k$, gives a fourth number, which is not any of the three and is in general not computable: deciding a three-dimensional array’s rank is NP-hard, proved in 1990. It is not an idle question: the rank of one particular three-dimensional array is the number of multiplications matrix multiplication needs, which is why the exponent in that problem is still unknown.

Worse, the rank can depend on the field. A specific three-by-three-by-two array has rank three over the reals and rank two over the complex numbers, so a question with a whole-numbered answer changes its answer depending on which numbers are allowed — something no matrix does.

So everything comfortable about rank is a two-index phenomenon, and the essay’s theorem is the thing that makes it comfortable. That is the right way to hold it: not as an obvious symmetry, but as a coincidence of small dimension that the whole subject is built on.

The four subspaces, and the two right angles #

Once the two counts are one number, four subspaces come with it and their relations are worth setting out, because the picture they make is the one that explains what a rectangular map does.

An $m \times n$ array gives a map from $\mathbb{R}^n$ to $\mathbb{R}^m$, and four subspaces:

• in the source: the row space, of dimension $r$, and the kernel, of dimension $n - r$;
• in the target: the column space, of dimension $r$, and the kernel of the transpose, of dimension $m - r$.

In each space the two dimensions add to that space’s dimension, which is rank–nullity applied twice — once to the map and once to its transpose. And in each space the two subspaces are at right angles: a vector in the kernel has zero dot product with every row by definition, so the kernel is exactly the orthogonal complement of the row space.

So the map’s whole behaviour is: the source splits into two perpendicular pieces, one of which is crushed to nothing and the other of which is carried one-to-one onto the column space; and the target splits into two perpendicular pieces, one of which is reached and the other of which is not.

That is the structure everything practical rests on. A system $Ax = b$ has a solution exactly when $b$ is in the column space; when it is not, the nearest thing to a solution is obtained by projecting $b$ onto the column space, which is least squares and is the reason the perpendicularity matters rather than being decoration. And when a solution exists it is unique modulo the kernel, so the solution set is a translate of a subspace of dimension $n - r$.

Every one of those statements needs the two counts to be the same number, since each involves an $r$ measured in the source and an $r$ measured in the target.

Two subspaces nobody can see #

Both grids show a finished elimination and neither shows one happening. The shaded rows are the independent ones after reduction; the process that found them — which row was subtracted from which — is not on the page, and the claim being made is about the final count rather than about the route to it.

The exactness is invisible. Every number in both grids is a small integer, which makes the arrays look easy; the point of computing in fractions is that the intermediate values are not integers and a rank computed in doubles would be untrustworthy. Nothing in the drawing shows an intermediate value at all.

And four dimensions is not drawn. The rows of the hero’s array are four vectors in four-dimensional space and the claim is about their span. What is drawn is the numbers; the span is a subspace nobody can see, and that the theorem is about two subspaces in two different unvisualisable spaces is what makes it worth proving.

Still open: the same count on a matrix nobody built #

The rank-nullity count is a statement about arrays and it does not care where the array came from. Apply it to a matrix built from a graph — a row for every edge, a column for every vertex — and the same arithmetic says that a graph’s independent cycles and its independent cuts add to its number of edges.

Nothing in that statement mentions a matrix, and neither of the two quantities in it is obviously a dimension. That is the cycles and the cuts.

Two counts and one quantity #

The habit is to notice when two apparently independent measurements are forced to agree, and to ask what they are both measurements of.

Row rank and column rank are two counts of two different collections in two different spaces, and their agreement is a theorem with a one-paragraph proof. What the proof supplies is a third object neither count mentioned: the smallest space the map factors through. Both counts were measuring that, and once it is named the agreement stops being a coincidence.

That move is available more often than it is used. When two quantities agree unexpectedly, the productive question is not why are these equal but what third thing are they both the size of — and the answer is usually the object the subject should have been about.