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.
Recall the three elementary row operations:
\(R_i \leftarrow \alpha R_i\) (replacing row \(i\) with \(\alpha\) times row \(i\) where \(\alpha \neq 0\))
\(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\))
\(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.
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
For each the following matrices, transform it into a matrix in RREF using elementary row operations.
\(\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{bmatrix}\)
\(\begin{bmatrix} 0 & 2 & 2 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 1 & 2 & 1 \end{bmatrix}\)