2.6. Gauss-Jordan elimination

Fig. 2.3 Carl Wilhelm Jordan (1842 - 1899)

Gauss-Jordan elimination (GJE), named after Gauss and German geodesist Wilhelm Jordan, is similar to Gaussian elimination with the difference that the augmented matrix is reduced using elementary row operations so that the values of the pivot elements are 1 and are the only non-zero element in the column. This allows the solution to be read from the final augmented matrix without the need to perform back substitution. A matrix in this form is said to be in reduced row echelon form.

Definition 2.5 (Reduced Row Echelon Form (RREF))

A matrix is said to be in Reduced Row Echelon Form (RREF) if it satisfies the following conditions

• it is in row echelon form;

• the leading entry in each non-zero row has a value of 1;

• the leading entry in each non-zero row is the only non-zero element in its column.

For example the following matrices are in reduced row echelon form:

\[\begin{split} \begin{align*} &\begin{pmatrix} \textcolor{red}{1} & 0 \\ 0 & \textcolor{red}{1} \end{pmatrix}, & &\begin{pmatrix} \textcolor{red}{1} & 2 & 0 \\ 0 & 0 & \textcolor{red}{1} \end{pmatrix}, & &\begin{pmatrix} \textcolor{red}{1} & 0 & 2 & 0 \\ 0 & \textcolor{red}{1} & 3 & 0 \\ 0 & 0 & 0 & \textcolor{red}{1} \end{pmatrix} \end{align*} \end{split}\]

The method of Gauss-Jordan elimination is summarised by the steps below.

Algorithm 2.3 (Gauss-Jordan elimination)

Inputs: An \(m \times n\) matrix \(A\)

Outputs: The matrix \(A\) expressed in reduced row echelon form

• Start with the pivot element as the element in the first row and column of \(A\).

• For each column of \(A\)

  • If partial pivoting is not used

    • Ensure the pivot element is non-zero by performing a row swap on a row beneath the pivot row

  • Else if partial pivoting is used

    • Perform a row swap with the row beneath the pivot row that has the largest absolute value element in the pivot column which is greater than the absolute value fo the pivot element.

  • If the pivot element is zero move to the next column

  • For each row of \(A\) except the pivot row

    • Subtract the pivot row multiplied by the value in the pivot column of the row divided by the pivot element from the current row.

  • Divide the pivot row by the pivot element.

• Return \(A\)

Example 2.5

Use Gauss-Jordan elimination to solve the following system of linear equations

\[\begin{split} \begin{align*} 3x_1 + x_2 - 2 x_3 &= 1, \\ x_1 - x_2 + 2x_3 &= 3, \\ 2x_1 - 3x_2 + 7x_3 &= 4. \end{align*} \end{split}\]

Solution (click to show)

\[\begin{split} \begin{align*} & \left( \begin{array}{ccc|c} 3 & 1 & -2 & 1 \\ 1 & -1 & 2 & 3 \\ 2 & -3 & 7 & 4 \end{array} \right) \begin{array}{l} R_1 \leftrightarrow R_2 \\ \phantom{x} \\ \phantom{x} \end{array} & \longrightarrow & \left( \begin{array}{ccc|c} 1 & -1 & 2 & 3 \\ 3 & 1 & -2 & 1 \\ 2 & -3 & 7 & 4 \end{array} \right) \begin{array}{l} \\ R_2 - 3R_1 \\ R_3 - 2R_1 \end{array} \\ \\ \longrightarrow & \left( \begin{array}{ccc|c} 1 & -1 & 2 & 3 \\ 0 & 4 & -8 & -8 \\ 0 & -1 & 3 & -2 \end{array} \right) \begin{array}{l} \\ \frac{1}{4} R_2 \\ \phantom{x} \end{array} & \longrightarrow & \left( \begin{array}{ccc|c} 1 & -1 & 2 & 3 \\ 0 & 1 & -2 & -2 \\ 0 & -1 & 3 & -2 \end{array} \right) \begin{array}{l} R_1 + R_2 \\ \\ R_3 + R_2 \end{array} \\ \\ \longrightarrow & \left( \begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & -2 & -2 \\ 0 & 0 & 1 & -4 \end{array} \right) \begin{array}{l} \\ R_2 + 2R_3 \\ \phantom{x} \end{array} & \longrightarrow & \left( \begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & -10 \\ 0 & 0 & 1 & -4 \end{array} \right) \end{align*} \end{split}\]

Therefore the solution is \(x_1 = 1\), \(x_2 = -10\) and \(x_3 = -4\).

2.6.1. Calculating the inverse of a matrix using Gauss-Jordan elimination

Gauss-Jordan elimination allows us to calculate the inverse of matrices which is much more computationally efficient than the adjoint-determinant formula. To show how we can use ERO to calculate an inverse of a matrix we first need to consider elementary matrices.

Definition 2.6 (Elementary matrices)

An elementary matrix is an \(n \times n\) square matrix obtained by performing a single elementary row operation to the identity matrix \(I_n\)

Since we have three types of elementary row operations there are three types of elementary matrices. Consider the examples of the three type for \(I_3\):

• swap row 1 and row 2:   \(E_1 = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}\);

• multiply row 2 by \(k\):   \(E_2 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & k & 0 \\ 0 & 0 & 1 \end{pmatrix}\);

• add \(k\) multiplies of row 1 from row 3:   \(E_3 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ k & 0 & 1 \end{pmatrix}\).

Elementary matrices have an inverse which is obtained by inverting the elementary row operation and applying it to the identity matrix. Consider the inverse operations to those shown above:

• swap row 1 and row 2:   \(E_1 = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}\);

• divide row 2 by \(k\):   \(E_2 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1/k & 0 \\ 0 & 0 & 1 \end{pmatrix}\);

• subtract \(k\) multiplies of row 1 from row 3:   \(E_3 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -k & 0 & 1 \end{pmatrix}\).

Since the inverse of an elementary matrix is obtained by applying an elementary row operation to the identity matrix, by definition it must also be an elementary matrix.

Theorem 2.3 (Multiplying by an elementary matrix)

IF \(A\) is an \(n \times n\) matrix and \(E\) is an elementary matrix the product \(EA\) is equivalent to performing the elementary row operation used to obtain \(E\) on \(A\).

For example, let \(A = \begin{pmatrix} 1 & 0 & 4 \\ 2 & -1 & 3 \\ 0 & 5 & 1 \end{pmatrix}\) and consider the following row operations:

• \(R_1 \leftrightarrow R_2\):   \(E_1 = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}\) so \(E_1A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 4 \\ 2 & -1 & 3 \\ 0 & 5 & 1 \end{pmatrix} = \begin{pmatrix} 2 & -1 & 3 \\ 1 & 0 & 4 \\ 0 & 5 & 1 \end{pmatrix}\);

• \(-2R_2\):   \(E_2 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & -2 & 0 \\ 0 & 0 & 1 \end{pmatrix}\) so \(E_2A = \begin{pmatrix} 1 & 0 & 0 \\ 0 & -2 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 4 \\ 2 & -1 & 3 \\ 0 & 5 & 1 \end{pmatrix}=\begin{pmatrix} 1 & 0 & 4 \\ -4 & 2 & -6 \\ 0 & 5 & 1 \end{pmatrix}\);

• \(R_3 + 3R_2\):   \(E_3 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 3 & 1 \end{pmatrix}\) so \(E_3A = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 3 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 4 \\ 2 & -1 & 3 \\ 0 & 5 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 4 \\ 2 & -1 & 3 \\ 6 & 2 & 10 \end{pmatrix}\).

Consider a matrix \(A\) that has been reduced to reduced row echelon form, i.e., \(I\), by applying \(k\) elementary row operations with corresponding elementary matrices \(E_1, E_2, \ldots, E_k\) then

\[ I = E_k E_{k-1} \cdots E_2 E_1 A. \]

Right-mutiplying both sides by \(A^{-1}\)gives

\[\begin{split} \begin{align*} I A^{-1} &= E_k E_{k-1} \cdots E_2 E_1 A A^{-1} \\ A^{-1} &= E_k E_{k-1} \cdots E_2 E_1 I. \end{align*} \end{split}\]

In other words, we can calculate the inverse of \(A\) by applying the same row operations to the identity matrix as we do when we reduce \(A\) to reduced row echelon form. For brevity we do this by forming an augmented matrix \((A \mid I)\) and perform Gauss-Jordan elimination on the augmented matrix. Once this has been reduced to reduced row echelon form the matrix to the right of the partition is the inverse of \(A\).

The calculation of a matrix inverse using Gauss-Jordan elimination is more efficient that using the adjoint- determinant formula when dealing with larger matrices (i.e., when \(n > 3\)) since the steps can be easily programmed into a computer and it does not require the calculation of determinants which can be computationally expensive.

Example 2.6

Use Gauss-Jordan elimination to calculate the inverse of

\[\begin{split} A = \begin{pmatrix} 1 & 0 & 2 \\ 2 & -1 & 3 \\ 1 & 4 & 4 \end{pmatrix}.\end{split}\]

Solution (click to show)

\[\begin{split} \begin{align*} &\left( \begin{array}{ccc|ccc} 1 & 0 & 2 & 1 & 0 & 0 \\ 2 & -1 & 3 & 0 & 1 & 0 \\ 1 & 4 & 4 & 0 & 0 & 1 \end{array} \right) \begin{array}{l} \\ R_2 - 2R_1 \\ R_3 - R_1 \end{array} \\ \\ \longrightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 2 & 1 & 0 & 0 \\ 0 & -1 & -1 & -2 & 1 & 0 \\ 0 & 4 & 2 & -1 & 0 & 1 \end{array} \right) \begin{array}{l} \\ -R_2 \\ \phantom{x} \end{array} \\ \\ \longrightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 2 & 1 & 0 & 0 \\ 0 & 1 & 1 & 2 & -1 & 0 \\ 0 & 4 & 2 & -1 & 0 & 1 \end{array} \right) \begin{array}{l} \\ \\ R_3 - 4R_2 \end{array} \\ \\ \longrightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 2 & 1 & 0 & 0 \\ 0 & 1 & 1 & 2 & -1 & 0 \\ 0 & 0 & -2 & -9 & 4 & 1 \end{array} \right) \begin{array}{l} \\ \\ -\frac{1}{2}R_3 \end{array} \\ \\ \longrightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 2 & 1 & 0 & 0 \\ 0 & 1 & 1 & 2 & -1 & 0 \\ 0 & 0 & 1 & 9/2 & -2 & -1/2 \end{array} \right) \begin{array}{l} R_1 - 2R_3 \\ R_2 - R_3 \\ \phantom{x} \end{array} \\ \\ \longrightarrow &\left( \begin{array}{ccc|ccc} 1 & 0 & 0 & -8 & 4 & 1 \\ 0 & 1 & 1 & -5/2 & 1 & 1/2 \\ 0 & 0 & 1 & 9/2 & -2 & -1/2 \end{array} \right) \begin{array}{l} R_1 - 2R_3 \\ R_2 - R_3 \\ \phantom{x} \end{array} \\ \\ \end{align*} \end{split}\]

The augmented matrix is now in reduced row echelon form and the inverse of \(A\) is

\[\begin{split} A^{-1} = \begin{pmatrix} -8 & 4 & 1 \\ -5/2 & 1 & 1/2 \\ 9/2 & -2 & -1/2 \end{pmatrix}. \end{split}\]

Checking whether this is correct

\[\begin{split} \begin{align*} A^{-1} A &= \begin{pmatrix} -8 & 4 & 1 \\ -5/2 & 1 & 1/2 \\ 9/2 & -2 & -1/2 \end{pmatrix} \end{align*} \begin{pmatrix} 1 & 0 & 2 \\ 2 & -1 & 3 \\ 1 & 4 & 4 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \checkmark\end{split}\]