2.5 Existence of row-echelon forms

The previous notes teach how to carry out Gaussian elimination and how to read the result. This note asks a more theoretical question:

Why is it legitimate to expect a row-echelon form, and then a reduced row-echelon form, to exist for every matrix?

This question matters because row reduction is used throughout the course. We use it to solve systems, find free variables, test span, test independence, compute inverses, find ranks, and build bases. If echelon forms were only a collection of examples, the later theory would rest on guesswork. The theorem below says that the algorithm has a guaranteed target.

What is being proved

Theorem

Existence of REF

For every matrix $C$ , there exists a row-echelon form $C^\#$ such that $C^\#$ is row-equivalent to $C$ .

Theorem

Existence of RREF

For every matrix $C$ , there exists a reduced row-echelon form C' such that C' is row-equivalent to $C$ .

The first theorem says that Gaussian elimination can always reach a staircase form. The second theorem says that, once a staircase form has been reached, the extra cleanup steps can always reach reduced form.

The proof is optional, but it is valuable because it explains why the row reduction process is not just a recipe. It is a finite, structured argument.

Induction on the number of rows

The REF existence proof is by induction on the number of rows.

Definition

The induction proposition

Let P(m) be the statement: if $A$ is a matrix with m rows, then $A$ is row-equivalent to some row-echelon form $A^\#$ with m rows.

The base case is direct. If a matrix has only one row, it is already in row echelon form: either it is the zero row, or its first nonzero entry is the leading entry of the only nonzero row.

For the induction step, assume P(k) is true and let $A$ be a matrix with $k+1$ rows.

If $A$ is the zero matrix, there is nothing to prove. Otherwise, find the leftmost nonzero column of $A$ . In that column, choose the topmost nonzero entry and swap its row into the first row if necessary. Call the resulting first pivot value $\beta$ .

After that, use the first row to clear all entries below $\beta$ in the same column. The matrix has the block shape

\begin{bmatrix} O_{1\times(j-1)} & \beta & u \\ O_{k\times(j-1)} & 0_k & V \end{bmatrix},

where $V$ is a matrix with k rows.

Now the induction hypothesis applies to $V$ . It can be row-reduced to some row-echelon form V'. Performing the corresponding row operations on the lower k rows of the whole matrix gives

\begin{bmatrix} O_{1\times(j-1)} & \beta & u \\ O_{k\times(j-1)} & 0_k & V' \end{bmatrix}.

This matrix is in row-echelon form: the first pivot is in column j, all entries below it are zero, and the lower block has the required staircase structure by induction.

Theorem

Conclusion of the REF proof

By mathematical induction, every matrix with a positive number of rows is row-equivalent to some row-echelon form.

The point of the proof is not to memorize the block notation. The point is to see the recursive structure: one pivot is placed, everything below it is cleared, and the remaining smaller matrix is handled by the same theorem.

Worked example

Seeing the smaller block in an actual matrix

Consider

A= \begin{bmatrix} 0 & 2 & 1\\ 0 & 4 & 3\\ 0 & 0 & 5 \end{bmatrix}.

The leftmost nonzero column is column 2. The top entry in that column is already nonzero, so we may use $\beta=2$ in row 1 as the first pivot. Clearing below it gives

R_2\leftarrow R_2-2R_1,\qquad \begin{bmatrix} 0 & 2 & 1\\ 0 & 0 & 1\\ 0 & 0 & 5 \end{bmatrix}.

What remains below and to the right of the first pivot is the smaller block

V= \begin{bmatrix} 1\\ 5 \end{bmatrix}.

This is exactly the point of the induction proof. The whole matrix no longer has to be solved at once: after the first pivot is fixed, the remaining task is to put a matrix with fewer rows into row-echelon form. In this example, one more operation, $R_3\leftarrow R_3-5R_2$ , gives

\begin{bmatrix} 0 & 2 & 1\\ 0 & 0 & 1\\ 0 & 0 & 0 \end{bmatrix},

which is in REF. The example is small, but it shows the same reduction in size used in the general proof.

From REF to RREF

The second part begins with a matrix already in row-echelon form. The goal is to prove that it can be changed into reduced row-echelon form without losing row equivalence.

The induction parameter is now the rank, meaning the number of nonzero rows in the row-echelon form.

Theorem

REF-to-RREF lemma

If $A$ is a row-echelon form of rank r, then there exists a reduced row-echelon form A' of rank r such that A' is row-equivalent to $A$ .

The base case $r=0$ is immediate: a row-echelon form with rank 0 is the zero matrix, which is already in RREF.

For the induction step, suppose the result is known for rank k, and let $A$ be a row-echelon form of rank $k+1$ . Focus first on the columns strictly to the left of the last pivot column. Those columns form a smaller row-echelon block of rank k, so the induction hypothesis reduces that left block.

Then normalize the last pivot to 1 and clear the entries above it. These row operations do not disturb the already-reduced pivot columns to the left, because the echelon form has zeros in the relevant positions.

The result is a matrix whose pivot columns each contain exactly one nonzero entry, and that entry is 1. Hence the result is in RREF.

Worked example

Cleaning a REF without moving its pivot columns

Start from the row-echelon form

B= \begin{bmatrix} 2 & 1 & 4 & 5\\ 0 & 0 & -3 & 6\\ 0 & 0 & 0 & 0 \end{bmatrix}.

Its pivot columns are columns 1 and 3. To clean it toward RREF, first normalize the second pivot:

R_2\leftarrow -\frac{1}{3}R_2,\qquad \begin{bmatrix} 2 & 1 & 4 & 5\\ 0 & 0 & 1 & -2\\ 0 & 0 & 0 & 0 \end{bmatrix}.

Then clear the entry above the second pivot:

R_1\leftarrow R_1-4R_2,\qquad \begin{bmatrix} 2 & 1 & 0 & 13\\ 0 & 0 & 1 & -2\\ 0 & 0 & 0 & 0 \end{bmatrix}.

Finally normalize the first pivot:

R_1\leftarrow \frac{1}{2}R_1,\qquad \begin{bmatrix} 1 & \frac12 & 0 & \frac{13}{2}\\ 0 & 0 & 1 & -2\\ 0 & 0 & 0 & 0 \end{bmatrix}.

The numerical entries in columns 2 and 4 changed, but the pivot columns did not. They are still columns 1 and 3. This is the concrete version of the preservation statement in the REF-to-RREF proof.

Pivot columns are preserved in the REF-to-RREF cleanup

The proof actually gives a useful extra statement.

Theorem

Pivot columns are preserved from REF to RREF

Suppose $A$ is a row-echelon form of rank r, with pivot columns $d_1,\ldots,d_r$ . Then $A$ is row-equivalent to a reduced row-echelon form whose pivot columns are still $d_1,\ldots,d_r$ .

This is why, once a matrix is in REF, you can already read the pivot columns. Continuing from REF to RREF cleans the pivot columns; it does not move them.

The video below turns the optional proof into a short proof-as-algorithm map: one pivot is placed, the smaller lower block is handled by induction, and the REF cleanup preserves the pivot columns already visible in the staircase.

Visual explanation

Existence of REF and RREF

Turn the optional appendix proof into a proof-as-algorithm map: leftmost pivot, clear below, recurse on a smaller block, then clean REF to RREF while preserving pivot columns.

The existence proof is constructive: place one pivot, reduce the smaller block by induction, then clean a REF to RREF without moving the pivot columns. It proves a reachable target, not RREF uniqueness.

Worked example

REF already tells you the pivot columns

Consider

\begin{bmatrix} 2 & 4 & 1 & 7\\ 0 & 0 & 3 & 5\\ 0 & 0 & 0 & 0 \end{bmatrix}.

This is in REF. The pivot columns are columns 1 and 3. To reach RREF, one would scale the first two nonzero rows and clear entries above the second pivot. The values in the free columns may change, but the pivot columns remain columns 1 and 3.

What this note does not prove

This note proves existence. It shows that at least one REF and at least one RREF can be reached from any matrix.

There is another important theorem, used later when rank is treated as a well-defined invariant: the RREF of a matrix is unique. That uniqueness theorem is stronger than existence. Existence says a target can be reached; uniqueness says all valid reduction paths reach the same reduced target.

For ordinary computation, you mainly need the practical consequence:

elimination can always be organized into REF;
REF can always be cleaned into RREF;
pivot columns read in REF are the same pivot columns in the corresponding RREF cleanup;
row equivalence preserves the solution set of an augmented system.

How this theorem is used later

The existence theorem is quiet, but it supports many later calculations. When you solve a system, you usually do not pause to prove that the row-reduction process will reach an interpretable form. You simply reduce the augmented matrix and expect to read pivot variables, free variables, and consistency from the result. This note supplies the missing guarantee: the row operations can always be organized so that an REF exists, and the REF can always be cleaned further to an RREF.

It is also important to separate two different kinds of information. REF is already enough to identify the pivot columns and decide which variables are basic or free. RREF is more convenient when you want final formulas, because each pivot column has been normalized and cleared. The proof explains why these two uses are compatible: the cleanup from REF to RREF improves the shape of the pivot columns without changing their positions.

This is why later notes may move quickly between computation and theory. For example, when rank is defined using pivot columns, we are not merely relying on a lucky example. The existence result ensures that a pivot staircase can be reached, and the preservation result ensures that the pivot columns read from a staircase remain the relevant columns during the RREF cleanup. The separate uniqueness theorem will later make the final RREF independent of the path of row operations; this note deliberately stops one step earlier, at existence and pivot-column preservation.

One practical way to remember the distinction is this: existence justifies the method before you start, while uniqueness later justifies the independence of the final reduced answer. When you are still at the REF stage, you should trust the pivot pattern but not pretend that the entire matrix is already in its final canonical form. This separation keeps the computational procedure honest without overstating what the optional proof has actually established.

Common mistakes

Common mistake

Treating induction as a calculation trick

The proof is not saying that every matrix should be reduced by writing block matrices on paper. The induction proof explains why the algorithm must terminate with the desired form.

Common mistake

Confusing existence with uniqueness

Existence of RREF says some reduced row-echelon form can be reached. It does not, by itself, prove that different row-reduction paths must lead to the same RREF.

Common mistake

Thinking RREF changes pivot columns from REF

The REF-to-RREF argument preserves pivot columns. The cleanup clears entries above pivots and normalizes pivots, but it does not shift the leading positions to new columns.

Quick checks

Quick check

Why does the REF proof use induction on the number of rows?

Look at what remains after the first pivot column has been placed and cleared.

Solution

Answer

Quick check

Once a matrix is in REF, can the pivot columns move while cleaning to RREF?

Think about the extra statement proved in the REF-to-RREF lemma.

Solution

Answer

Exercises

Exercise 1

Explain why the following matrix is already in REF, and identify its pivot columns:

\begin{bmatrix} 0 & 2 & 1 & 4\\ 0 & 0 & 5 & 6\\ 0 & 0 & 0 & 0 \end{bmatrix}.

Solution

Guided solution for exercise 1

Exercise 2

Suppose a row-echelon form has pivot columns 1, 4, and 5. What can you say about the pivot columns after reducing it further to RREF?

Solution

Guided solution for exercise 2

This appendix should be read after 2.3 Gaussian elimination and RREF and before relying heavily on row reduction in span, independence, rank, or inverse computations.

2.5 Existence of row-echelon forms

MATH1030: Linear algebra I

What is being proved

Existence of REF

Existence of RREF

Induction on the number of rows

The induction proposition

Conclusion of the REF proof

Seeing the smaller block in an actual matrix

From REF to RREF

REF-to-RREF lemma

Cleaning a REF without moving its pivot columns

Pivot columns are preserved in the REF-to-RREF cleanup

Pivot columns are preserved from REF to RREF

REF already tells you the pivot columns

What this note does not prove

How this theorem is used later

Common mistakes

Treating induction as a calculation trick

Confusing existence with uniqueness

Thinking RREF changes pivot columns from REF

Quick checks

Why does the REF proof use induction on the number of rows?

Answer

Once a matrix is in REF, can the pivot columns move while cleaning to RREF?

Answer

Exercises

Exercise 1

Guided solution for exercise 1

Exercise 2

Guided solution for exercise 2

Section mastery checkpoint

Suppose a matrix is already in REF with pivot columns 2 and 4. During the cleanup from REF to RREF, what happens to those pivot columns?

Prerequisites

Key terms in this unit

Premium learning add-ons

More notes in this series

2.5 Existence of row-echelon forms

MATH1030: Linear algebra I

What is being proved

Existence of REF

Existence of RREF

Induction on the number of rows

The induction proposition

Conclusion of the REF proof

Seeing the smaller block in an actual matrix

From REF to RREF

REF-to-RREF lemma

Cleaning a REF without moving its pivot columns

Pivot columns are preserved in the REF-to-RREF cleanup

Pivot columns are preserved from REF to RREF

REF already tells you the pivot columns

What this note does not prove

How this theorem is used later

Common mistakes

Treating induction as a calculation trick

Confusing existence with uniqueness

Thinking RREF changes pivot columns from REF

Quick checks

Why does the REF proof use induction on the number of rows?

Answer

Once a matrix is in REF, can the pivot columns move while cleaning to RREF?

Answer

Exercises

Exercise 1

Guided solution for exercise 1

Exercise 2

Guided solution for exercise 2

Related notes

Section mastery checkpoint

Prerequisites

Key terms in this unit

Premium learning add-ons

More notes in this series