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 2.5.1

(Existence of REF)

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

Theorem 2.5.2

(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.

Induction on the number of rows

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

Definition 2.5.3

(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 2.5.4

(Conclusion of the REF proof)

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

Worked example 2.5.5

(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 2.5.6

(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 2.5.7

(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 2.5.8

(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.

Worked example 2.5.9

(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$.

Existence and independence of the reduction path

The proofs establish that every matrix can reach REF and then RREF. During the specified cleanup, the pivot columns keep their positions. For a consistent augmented system, REF already identifies the leading and free variables; RREF makes their formulas directly readable. Row equivalence preserves the solution set throughout.

A different question is whether two completed reductions must give the same RREF. That requires the separate uniqueness theorem. Existence supplies a reachable form; uniqueness makes that reduced form independent of the chosen operations and supports the later definition of rank. The present induction proves existence and preservation during cleanup, without assuming path independence.

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

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.

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

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.