Up Main page

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\):

Quick Quiz

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}\)