📶Rank & the Shape of Solutions

A matrix with five rows looks like five pieces of information. Often it is not. Two of those rows may say the same thing twice, and a third may be the first two added together. The rank is the honest count: how many of the rows are genuinely new.

To find it, reduce the matrix and count the pivots — the leading 1s. Every non-zero row of a reduced matrix has exactly one, and a row of nothing but zeros has none at all, because it was a repeat of the rows above it.

R = [[1, 0, -2 | 3], [0, 1, 4 | 5], [0, 0, 0 | 0]]

Two pivots. The rank is 2, even though the matrix has three rows.

The number of rows is not the rank. That single sentence is the most common slip in this whole craft, and it is worth guarding deliberately: count the leading 1s, not the lines on the page. The number of columns is not the rank either — a column with no pivot in it is exactly what a free unknown looks like.

Two ceilings sit over the rank, and they follow straight from what a pivot is. A pivot claims a row of its own and a column of its own, so an m by n matrix can never have more than m pivots and never more than n. The rank is at most the smaller of the two.

One more fact, surprising the first time and useful forever: the number of independent rows and the number of independent columns are always the same number. So the rank of a matrix and the rank of its transpose are equal, and it never matters which way round you count.

Set every constant to zero and look at Ax = 0. Every column of A carries one unknown, so there are n unknowns in play, where n is the number of columns.

Reduce. Each pivot pins one unknown to a value. Whatever is left over is free — it may take any value at all, and each value gives another solution. The count of free unknowns has its own name, the nullity, and the two counts share the columns out between them:

rank + nullity = n

That is the whole rule, and it is one of the few places in mathematics where a sentence about structure is also a sentence about arithmetic. Know any two of the three numbers and the third follows.

The number of rows is nowhere in that rule. It is a ceiling on the rank and nothing more. A system of ten equations in three unknowns still has only three columns to share out, and its nullity is 3 minus its rank, never 10 minus its rank. Slipping the row count into this rule is the second signature mistake of the craft.

A nullity of 0 is a perfectly ordinary answer, not a sign of an error: it says the rank has reached the number of columns, every unknown sits in a pivot column, and Ax = 0 has nothing but the zero solution. What a nullity can never be is negative, because the rank can never pass the number of columns it has to fit into.

For a system Ax = b there are two ranks worth knowing: the rank of the coefficient matrix A, and the rank of the whole augmented matrix [A | b]. Comparing them answers every question about the solutions, in two steps and in this order.

Step one: are the two ranks equal? The augmented matrix has one extra column, so its rank is either the same as rank(A) or one larger. If it is larger, that extra pivot can only be sitting in the column past the bar — which is exactly a row reading 0 = k for some k that is not zero. The system is inconsistent and has no solution.

Notice what this means for counting. A row like [0, 0, 0 | 5] contributes a pivot to the augmented matrix and no pivot at all to the coefficient matrix. Counting it in both places is the third signature mistake here, and it makes an impossible system look like a solvable one.

Step two: if the ranks agree, compare that rank with n. Here n is the number of unknowns, which is the number of columns before the bar. The column past the bar is never an unknown and is never counted here.

• ◆rank(A) less than rank([A | b]): no solution
• ◆rank(A) = rank([A | b]) = n: exactly one solution
• ◆rank(A) = rank([A | b]) less than n: infinitely many solutions, one for every value of each of the n minus rank free unknowns

A homogeneous system, Ax = 0, can never take the first branch: x = 0 always solves it, so the two ranks always agree. The only question there is whether anything else solves it too, and the answer is yes exactly when the rank is below n.

The three elementary row operations — swapping two rows, multiplying a row by a number that is not zero, adding a multiple of one row to another — never change the rank. There is one test behind all three: each can be undone by another operation of the same kind. Something reversible cannot lose information and cannot invent any, so the count of independent rows is exactly what it was.

That is why reducing a matrix is safe. The reduced form and the original have the same rank, so the rank you count at the end is the rank you started with.

Some steps are not reversible, and they behave differently. Replacing a row by a row of zeros throws that row away for good; if the rows were independent, the rank drops by exactly 1. Adding a row of zeros at the bottom, on the other hand, changes nothing: a zero row carries no pivot.

Products need their own care, and two claims that sound reasonable are simply not true.

• ◆rank(AB) is never larger than rank(A), and never larger than rank(B). A product can lose rank freely — anything multiplied by a zero matrix has rank 0 — but it can never gain any.
• ◆rank(A + B) is not rank(A) plus rank(B). Take any A of rank 2 and let B be its negative: both have rank 2, and A + B is all zeros, of rank 0. The sum of the ranks is a ceiling, not a value.

Multiplying by an invertible matrix is the exception that proves the rule: that is reversible, so it leaves the rank alone.