An algorithm for row echelon form

Now, we turn to explicitly describing the steps from a general matrix $A$ to one in (reduced) row echelon form using our three classes of
row operations.

Thanks to the Theorem on Row Operations and Solution Sets we know that the set of solutions to the system remains unchanged when moving $A$ to the matrix in (reduced) row echelon form. From this we can conclude if we want to know the solution to a general system, it suffices to convert it to (reduced) row echelon form and the solve that system.
Solving (reduced) row echelon systems is easier than general systems.

Let’s describe one by one the steps.

Step 0

Write the system as an augmented matrix $(A \mid b)$.

Step 1 (Permutations)

Exchange the rows of $(A \mid b)$ until all $0$ rows are at the bottom.

Then permute the rows so that the column index of the pivots is a non-increasing function of the row index of the pivot. In equations, we want \(\operatorname{Pivot}(\mathbf{R}_i) \leq \operatorname{Pivot}(\mathbf{R}_j)\) if $i \leq j$.

Step 2 (Linear combinations)

Reading left to right, find the first column $\mathbb{C}_j$ such that

• there is a pivot $a_{ij}$ from row $\mathbf{R}_i$ in $\mathbb{C}_j$ and
• there is some some $a_{sj} \neq 0 $ with $s > i$, ie below $a_{ij}$.

If there are none, you are done.

Otherwise, let $\mathbf{R}_p$ be the row with the smallest $p$ of all the rows that have their pivots in $\mathbf{C}_j$.

For all $t \geq s$ replace the row $\mathbf{R}_t$ of $(A \mid b)$ with \(\mathbf{R}_t - \frac{a_{tj}}{a_{pj}} \mathbf{R}_p\) Note that this does nothing if $a_{tj} = 0$. If $a_{tj} \neq 0$, then it will be zeroed out.

Return to Step 1.

Let’s see this in effect in an example \(5 x_1 - 3 x_2 + x_3 + x_4 = 3 \\ x_1 + x_2 - x_3 + x_4 = 0 \\ -2x_1 - x_2 + 2x_3 + x_4 = 1\) to illustrate the algorithm.

Next, we want a proof that this algorithm actually outputs an matrix is row echelon form.

Theorem. The algorithm from row echelon form outputs a matrix in row echelon form.

Proof. Since we pass through Step 1 before we exit, we know two things:

• all zero rows are at the bottom and
• the column indices of the pivots never decrease as we increase the row index.

To get to row echelon form, we need know that the column index strictly increases as we increase the row index.

When we exit the algorithm, we know that if a column has a pivot, then all entries below the pivot must be $0$. Thus, we cannot have another pivot in that column. Since we know that column index of the pivot cannot decrease and cannot remain the same, it must increase as we increase the row index.

An algorithm for reduced row echelon form

We can tweak our algorithm from row echelon form slightly to get an algorithm that produces a matrix in reduced row echelon form.

Step 0

Same as before.

Step 1

Also the same.

Step 1.5

Scale all the rows so that all pivots have value $1$

Step 2

Reading left to right, find the first column $\mathbb{C}_j$ such that

• there is a pivot $a_{pj}$ from row $\mathbf{R}_p$ in $\mathbb{C}_j$ and
• there is some some $a_{sj} \neq 0 $ with $s \neq p$, ie anywhere in the column not just below.

If there are none, you are done.

Otherwise, let $\mathbf{R}_p$ be the row with the smallest $p$ of all the rows that have their pivots in $\mathbf{C}_j$.

For all $t \neq s$ replace the row $\mathbf{R}_t$ of $(A \mid b)$ with \(\mathbf{R}_t - \frac{a_{tj}}{a_{pj}} \mathbf{R}_p\)