Row Reduction Is a Proof, Not an Algorithm

August 2026

Source: Herbert Gross, MIT OpenCourseWare RES.18-008, “Calculus Revisited: Complex Variables, Differential Equations, and Linear Algebra”, Part III: Linear Algebra, Lecture 3 — “Constructing Bases,” 39 minutes. Everything below is written out from a full transcript of that lecture, in our own words. Found via a post on X that credited the lecturer and the course correctly.

Why this one is worth featuring

Almost everyone who takes linear algebra learns row reduction as a procedure: get a 1 there, clear the column below it, repeat. It is taught as arithmetic you perform, and it is graded as arithmetic you perform. Gross does something different. He never introduces row reduction as a technique at all — he introduces it as a chain of moves each of which provably cannot change the answer, and then points out that the familiar algorithm is what that chain looks like when you write it down.

That reframe turns a bookkeeping exercise into a proof, and it makes several results that are normally memorized separately fall out as by-products of one idea.

The setup: a matrix as a coding system

Start with a vector space $V$ of dimension 4 and a basis $u_1, u_2, u_3, u_4$. Pick four vectors in it:

$$\alpha_1 = (1,1,2,3), \quad \alpha_2 = (2,3,4,5), \quad \alpha_3 = (3,7,6,5), \quad \alpha_4 = (4,5,9,9)$$

The question is the ordinary one: what space do these four vectors span?

Write them as the rows of a matrix. Gross is careful about what that matrix is: it is not the vectors themselves, it is a code for them relative to the basis $u_1,\dots,u_4$. The first row, $(1,1,2,3)$, is shorthand for $1u_1 + 1u_2 + 2u_3 + 3u_4$. Everything that follows depends on remembering that the numbers are coordinates in a chosen basis, not the objects.

The one move, and why it is safe

Now do the thing you always do — replace row 2 by (row 2 minus twice row 1) to clear an entry.

Read that in the coding system instead of in the arithmetic. It says: replace the spanning vector $\alpha_2$ by $\alpha_2 - 2\alpha_1$.

That is the whole argument. You have replaced one spanning vector by itself plus a scalar multiple of another spanning vector. Any linear combination you could build from the old set you can still build from the new one, and vice versa — so the space spanned has not changed. Not “approximately,” not “up to something”: the span is literally the same set.

Every elementary row operation is an instance of that same move. So row reduction is a sequence of steps each of which is span-preserving by construction. Whatever matrix you end up with, its rows span exactly what the rows you started with spanned.

This is why the algorithm works, and it is a fact about spans, not about arithmetic.

What the destination tells you

Once you know the span is invariant, the endpoints of the reduction become informative rather than merely final.

If you reach the identity matrix, the rows are $u_1, u_2, u_3, u_4$ — which span all of $V$ by definition of a basis. Since row reduction preserved the span, the original $\alpha$’s must have spanned all of $V$ too. Reaching the identity is therefore a proof of spanning, not just a tidy stopping point.

If you get a zero row, you have learned more, not less. In this example the third row reduces to zero, so the identity is now unreachable. Gross’s phrase for it is that even failure is success here. The zero vector spans nothing — every scalar multiple of it is still the zero vector, so it contributes nothing to any linear combination — which means it is redundant and can be discarded. Three nonzero rows survive; call them $\beta_1,\beta_2,\beta_3$. They span the same space the four $\alpha$’s did, so that space is at most 3-dimensional.

The count of nonzero rows is the dimension. That is normally stated as a definition of rank; here it arrives as a consequence.

Recovering the actual dependency

A zero row proves the original set was linearly dependent, but it does not by itself say which vector was redundant. Gross recovers that by carrying along a record of which combination of $\alpha$’s produced each current row — reducing an augmented array rather than the bare matrix.

When the third row goes to zero, the record shows what combination produced it:

$$5\alpha_1 - 4\alpha_2 + \alpha_3 = \mathbf{0} \quad \Longrightarrow \quad \alpha_3 = 4\alpha_2 - 5\alpha_1$$

He then checks it by hand rather than asserting it, which is worth reproducing because it takes one line:

$$4\alpha_2 = (8,12,16,20), \qquad -5\alpha_1 = (-5,-5,-10,-15)$$ $$4\alpha_2 - 5\alpha_1 = (3,7,6,5) = \alpha_3 \ \checkmark$$

So $\alpha_3$ is the redundant one, and $\alpha_1, \alpha_2, \alpha_4$ are a basis for the space in question. Note what this did not require: no guessing, no trying subsets. The reduction found the redundancy and named it.

The sting in the tail: coordinates are relative

The lecture closes on the point most likely to cause trouble later, and it is the same point the matrix-as-a-code framing set up at the start.

The vector $(2,5,3,5)$ turns out to live in the space $W$ spanned by the $\beta$’s. Written relative to the $\beta$ basis its coordinates are $(2,5,3)$. Written relative to $\alpha_1,\alpha_2,\alpha_4$ the same vector has coordinates $(-2,4,-1)$.

Two different triples. One vector. Neither is wrong.

Gross’s warning is that a great deal of difficulty in advanced work comes from readers who stay rigid about this — who keep picturing the same $n$-tuples throughout and then cannot see how two different tuples could possibly name the same object. Once a basis is chosen the coordinate system is relative to that basis, and if the basis changes for convenience, the code changes with it.

Catalog status: Proven Systems

Nothing here is under test. This is standard linear algebra, rigorously established, and the lecture is a 1970s MIT recording published openly by MIT OpenCourseWare. What is featured is the teaching, not a claim.

A note on where this came from

The post that surfaced this lecture described it in all capitals as the clearest explanation of linear algebra ever recorded, and framed it as explaining “what Gilbert Strang built his entire career on.” It then named the source plainly: Herb Gross, MIT, Calculus Revisited Part III, lecture 3.

The Strang line is a framing device rather than an attribution — Gilbert Strang is a real and celebrated MIT linear algebra teacher, of 18.06, a different course, and his name appears nowhere in these 39 minutes. But the post does not claim otherwise; it credits Gross directly. Worth saying because linear algebra on the internet defaults to Strang, and Gross’s course deserves to be found under its own name.

The substance holds up better than an all-caps caption usually does. The claim that row reduction is “not just an algorithm but a proof” is exactly, specifically what the lecture argues — and the fact that it argues it well is why the material was worth writing out.