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.

The clearing step is legal because $\beta\ne0$: if the entry in row $i$ below it is $\alpha_i$, use $R_i\leftarrow R_i-(\alpha_i/\beta)R_1$. Every column before $j$ remains zero. Operations on $V$ lift by increasing each row index by one; they leave the first row fixed and act on zero prefixes in the lower rows. If $j$ is the final column, there is no trailing block to reduce: all lower rows are already zero. This boundary case ends the step without invoking induction on a nonexistent column.

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.

Proof

Why the last pivot survives the induction

Goal and strengthened hypothesis. We prove a little more than existence: a REF with $r$ nonzero rows can be reduced using only those rows, while keeping its pivot columns. This stronger induction statement records the information needed by the next step. Here $r$ means the visible count of nonzero rows in a REF; we are not assuming the later theorem that rank is independent of the reduction path. For $r=0$, no operation is needed.

Key move. Suppose the strengthened statement is known for $r=k$, and let $A$ have $k+1$ pivots in columns $d_1,\ldots,d_{k+1}$. Retain the columns strictly before $d_{k+1}$ as a left block $U$. Its first $k$ rows form a REF with $k$ pivots; every lower row of $U$ is zero. Apply the induction hypothesis to those first $k$ rows. When $k=0$, the entire left block is zero, possibly with no columns, so this stage does nothing.

Why the move is legal. Lift each chosen operation to the same two row indices, or the same scaled row, in the whole matrix $A$. An operation acts on the entire row, not just the entries displayed in $U$. Thus the right block changes along with $U$, but row $k+1$ and all rows below it are untouched. The pivot columns $d_1,\ldots,d_k$ become the standard coordinate columns $e_1,\ldots,e_k$, and the last pivot value $\alpha=A_{k+1,d_{k+1}}$ remains nonzero. The induction hypothesis supplies a sequence confined to the top $k$ rows; an arbitrary sequence that happens to reduce $U$ would not give this guarantee.

Cleanup and its boundary condition. Divide row $k+1$ by $\alpha$. If the entry above that pivot in row $i$ is $c_i$, replace $R_i$ by $R_i-c_iR_{k+1}$, for each $1\leq i\leq k$. These are allowed elementary operations because $\alpha\ne0$ and the source and target rows are distinct. Row $k+1$ is zero in every column before $d_{k+1}$. Therefore adding its multiples cannot alter the already reduced left block. It also cannot introduce an earlier leading entry. Rows below $k+1$ remain zero.

Closing the proof. Each old pivot column still has its single entry $1$, and the last pivot column now does too. All leading positions are unchanged, so the result is RREF with the original $k+1$ pivot columns. Only its nonzero rows were used, establishing the strengthened statement for the next induction step. Combining this construction with REF existence proves RREF existence; it does not yet prove uniqueness.

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 sequence below follows the inductive proof step by step: 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.

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.

1. Target guarantee

   Every matrix can reach a row-equivalent REF, and then a row-equivalent RREF. Row equivalence is the invariant throughout the proof.

2. First pivot

   If the matrix is not zero, find the leftmost nonzero column and move its topmost nonzero entry into the first row.

3. Smaller block

   Use the first row to clear below the pivot. The remaining block V has fewer rows, so the induction hypothesis applies there.

4. Lift the induction

   The row operations that reduce V to V# act only on lower rows when lifted back to the full matrix, so the first pivot remains fixed.

5. REF to RREF

   For a REF of rank r, rank induction reduces earlier pivot columns, then normalizes the last pivot and clears above it.

6. Pivots stay

   The cleanup changes entries, not pivot-column positions. This is the useful preservation result; uniqueness of RREF is a separate stronger theorem.

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:

1. elimination can always be organized into REF;
2. REF can always be cleaned into RREF;
3. pivot columns read in REF are the same pivot columns in the corresponding RREF cleanup;
4. 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

Checkpoint

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

After the first pivot column is placed and cleared, the unreduced part is a smaller matrix with one fewer row block to handle. That is exactly the kind of recursive situation where induction on the number of rows applies.

Checkpoint

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

No. The cleanup from REF to RREF preserves the pivot columns. It scales pivot rows and clears entries above pivots, but the pivot positions remain in the same columns.

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

The zero row is at the bottom. The first nonzero row has leading entry in column $2$, and the second nonzero row has leading entry in column $3$, which is strictly to the right. Hence the matrix is in REF. Its pivot columns are columns $2$ and $3$.

Exercise 2

Continue the matrix from Exercise 1 to RREF. Give the row operations in order, and then check whether the pivot columns have changed.

Solution · Guided solution for exercise 2

First use $R_2\leftarrow \frac15R_2$. Next use $R_1\leftarrow R_1-R_2$ to clear the entry above the second pivot, and finally use $R_1\leftarrow \frac12R_1$. The result is

$$\begin{bmatrix} 0 & 1 & 0 & \frac75\\ 0 & 0 & 1 & \frac65\\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

The pivot columns remain $2$ and $3$. The calculation shows why normalization and backward clearing change the entries without moving the pivots.

Related notes

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