## Introduction

We saw that if we have a system $$Ax = b$$ where $$A$$ is in reduced row-echelon form (RREF), then we can readily obtain solutions. Hence, if we can transform a given system of linear equations into an equivalent system in such a form, we will have solved the system.

Gauss-Jordan elimination is a mechanical procedure for transforming a given system of linear equations to $$Rx = d$$ with $$R$$ in RREF using only elementary row operations. In casual terms, the process of transforming a matrix into RREF is called row reduction. We illustrate how this is done with an example.

## Gauss-Jordan elimination example

Recall the three elementary row operations:

1. $$R_i \leftarrow \alpha R_i$$ (replacing row $$i$$ with $$\alpha$$ times row $$i$$ where $$\alpha \neq 0$$)

2. $$R_i \leftarrow R_i + \alpha R_j$$ (replacing row $$i$$ with row $$i$$ plus $$\alpha$$ times row $$j$$ where $$\alpha \neq 0$$ and $$i \neq j$$)

3. $$R_i \leftrightarrow R_j$$ (swapping rows $$i$$ and $$j$$ where $$i \neq j$$)

Let $$A = \begin{bmatrix} 1 & -1 & 2 & 1\\ 2 & -2 & 0 & 2 \\ -1 & 3 & 0 & 1 \end{bmatrix}$$, $$x = \begin{bmatrix} x_1\\x_2\\x_3\\x_4\end{bmatrix}$$, and $$b = \begin{bmatrix} 3\\ 1\\ 1\end{bmatrix}$$.

The augmented matrix for the system $$Ax = b$$ is $$\left[\begin{array}{cccc|c} 1 & -1 & 2 & 1 & 3 \\ 2 & -2 & 0 & 2 & 1\\ -1 & 3 & 0 & 1 & 1 \end{array}\right].$$ We now row reduce this matrix; i.e. to transform it into a matrix in RREF using elementary row operations.

In the first row, we already have a leading $$1$$. So we need to make sure all entries below it are zero using elementary row operations. This can be accomplished via $$R_2 \leftarrow R_2 + (-2)\times R_1$$ and $$R_3 \leftarrow R_3 + R_1$$. The resulting matrix is $\left[\begin{array}{cccc|c} 1 & -1 & 2 & 1 & 3 \\ 0 & 0 & -4 & 0 & -5\\ 0 & 2 & 2 & 2 & 4 \end{array}\right].$ Now, notice that the left-most nonzero entry in the second and third rows are not $$1$$. We can fix this via $$R_2 \leftarrow -\frac{1}{4} R_2$$ and $$R_3 \leftarrow \frac{1}{2} R_3$$. The resulting matrix is $\left[\begin{array}{cccc|c} 1 & -1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 0 & \frac{5}{4}\\ 0 & 1 & 1 & 1 & 2 \end{array}\right].$

The leading $$1$$ in row $$3$$ is to the left of that in row $$2$$. So we swap the two rows via $$R_2 \leftrightarrow R_3$$ to get $\left[\begin{array}{cccc|c} 1 & -1 & 2 & 1 & 3 \\ 0 & 1 & 1 & 1 & 2 \\ 0 & 0 & 1 & 0 & \frac{5}{4} \end{array}\right].$

To clear the entry above the leading $$1$$ in row 2, we perform $$R_1 \leftarrow R_1 + R_2$$ to obtain $\left[\begin{array}{cccc|c} 1 & 0 & 3 & 2 & 5 \\ 0 & 1 & 1 & 1 & 2 \\ 0 & 0 & 1 & 0 & \frac{5}{4} \end{array}\right].$

Finally, we clear the entries above the leading $$1$$ in row 3 by performing $$R_1 \leftarrow R_1 + (-3)\times R_3$$ and $$R_2 \leftarrow R_2 + (-1)\times R_3$$ to obtain $\left[\begin{array}{cccc|c} 1 & 0 & 0 & 2 & \frac{5}{4} \\ 0 & 1 & 0 & 1 & \frac{3}{4} \\ 0 & 0 & 1 & 0 & \frac{5}{4} \end{array}\right].$ This matrix is in RREF. The variables corresponding to the first three columns correspond to the leading ones. So, one solution to $$Ax = b$$ is given by $$x = \begin{bmatrix} 5/4 \\ 3/4 \\ 5/4 \\ 0\end{bmatrix}$$. To obtain all solutions, we would need to set $$x_4$$, the only free variable in this case, to some parameter $$s$$ and then solve for the pivot variables $$x_1,x_2,x_3$$ in terms of $$s$$. The answer is $$x = \begin{bmatrix} \frac{5}{4} - 2s\\ \frac{3}{4} - s \\ \frac{5}{4} \\ s\end{bmatrix}$$.

Remark: The RREF of a matrix is unique. In other words, no matter how you transform a matrix to one in RREF, as long as you are using only elementary row operations, you will always end up with the same matrix.

## Pseudo-code

It is possible to codify the procedure. Here is the pseudo-code for one implementation for row-reducing an $$m \times n$$ matrix $$A$$:

• Set $$p$$ to 1

• for $$k = 1,\ldots, n$$, do the following:

• if there exists $$i \in \{p,\ldots,m\}$$ such that (a_{ik} \neq 0,\) then do the following:

• if (i \neq p\), swap row $$p$$ and row $$i$$

• perform $${R}_p \leftarrow \alpha^{-1} {R}_p$$ where $$\alpha$$ is the entry in column $$k$$ of row $$p$$

• perform $${R}_q \leftarrow {R}_q - \alpha_{q}{R}_R$$ for all $$q \neq p$$ where $$\alpha_q$$ is the entry in column $$k$$ of row $$q$$

• increment $$p$$ by 1

• if $$p > m$$ stop

## Exercises

1. For each the following matrices, transform it into a matrix in RREF using elementary row operations.

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

2. $$\begin{bmatrix} 0 & 2 & 2 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 1 & 2 & 1 \end{bmatrix}$$