2.7. 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 with and without partial pivoting in Algorithm 2.3 and Algorithm 2.4 respectively.

Algorithm 2.3 (Gauss-Jordan elimination (without partial pivoting))

Inputs: An \(m \times n\) coefficient matrix \(A\) and an \(m\)-element constant vector \(\vec{b}\).

Outputs: An augmented matrix in row echelon form.

1. Form the augmented matrix \(( A \mid \vec{b} )\)

2. Set pivot row \(k\) to 1

3. For each column \(j\) from 1 to \(n\):

   1. Check pivot element:

      • If the pivot element \(a_{kj} = 0\)

        • Identify a row \(i\) where \(i > j\) and \(a_{ij} \neq 0\), if no such row exists skip to the next column

        • Swap row \(i\) with row \(k\)

   2. Eliminate elements in pivot column:

      • For each row \(i\) from \(1\) to \(m\) where \(i \neq k\):

        • Subtract \(\dfrac{a_{ij}}{a_{jj}}\) times row \(j\) from row \(i\)

   3. Normalise pivot row

      • Divide row \(k\) by pivot \(a_{kj}\)

Algorithm 2.4 (Gauss-Jordan elimination (with partial pivoting))

Inputs: An \(m \times n\) coefficient matrix \(A\) and an \(m\)-element constant vector \(\vec{b}\).

Outputs: An augmented matrix in row echelon form.

1. Form the augmented matrix \(( A \mid \vec{b} )\)

2. Set pivot row to \(k = 1\)

3. For each column \(j\) from 1 to \(n\):

   1. Find the pivot row:

      • Identify the row \(i\) where \(i \geq k\) with the largest absolute value in column \(j\)

      • If the largest absolute value is zero skip to next column

   2. Swap rows:

      • Swap row \(i\) with row \(k\).

   3. Eliminate elements in pivot column:

      • For each row \(i\) from \(1\) to \(m\) where \(i \neq k\):

        • Subtract \(\dfrac{a_{ij}}{a_{jj}}\) times row \(j\) from row \(i\)

   4. Normalise pivot row

      • Divide row \(k\) by pivot \(a_{kj}\)

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

\[\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.7.1. Elementary matrices

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:

\[\begin{split} \begin{align*} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{matrix} R_1 \leftrightarrow R_2 \\ \phantom{x} \\ \phantom{x} \end{matrix} \qquad \longrightarrow \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \end{align*} \end{split}\]

• Multiply row 2 by \(k\):

\[\begin{split} \begin{align*} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{matrix} \\ kR_2 \\ \phantom{x} \end{matrix} \qquad \longrightarrow \begin{pmatrix} 1 & 0 & 0 \\ 0 & k & 0 \\ 0 & 0 & 1 \end{pmatrix} \end{align*} \end{split}\]

• Add \(k\) multiples of row 1 to row 3:

\[\begin{split} \begin{align*} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{matrix} \\ \\ R_3 + kR_1 \end{matrix} \qquad \longrightarrow \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ k & 0 & 1 \end{pmatrix} \end{align*} \end{split}\]

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

• Swap row 1 and row 2:

\[\begin{split} \begin{align*} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{matrix} R_1 \leftrightarrow R_2 \\ \phantom{x} \\ \phantom{x} \end{matrix} \qquad \longrightarrow \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} \end{align*} \end{split}\]

• Divide row 2 by \(k\):

\[\begin{split} \begin{align*} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{matrix} \\ \frac{1}{k} R_2 \\ \phantom{x} \end{matrix} \qquad \longrightarrow \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1/k & 0 \\ 0 & 0 & 1 \end{pmatrix} \end{align*} \end{split}\]

• Subtract \(k\) multiples of row 1 from row 3:

\[\begin{split} \begin{align*} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{matrix} \\ \\ R_3 + kR_1 \end{matrix} \qquad \longrightarrow \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -k & 0 & 1 \end{pmatrix} \end{align*} \end{split}\]

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

Proof. 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.

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

\[\begin{split}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}\end{split}\]

• \(-2R_2\):   \(E_2 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & -2 & 0 \\ 0 & 0 & 1 \end{pmatrix}\) so

\[\begin{split}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}\end{split}\]

• \(R_3 + 3R_2\):   \(E_3 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 3 & 1 \end{pmatrix}\) so

\[\begin{split}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}\end{split}\]

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

Theorem 2.4

If \(A\) is a non-singular square matrix then the inverse of \(A\) can be calculated using

\[A^{-1} = E_kE_{k-1}\cdots E_2E_1.\]

Proof. Applying \(k\) elementary row operations with corresponding elementary matrices \(E_1, E_2, \ldots, E_k\) to row reduce \(A\) to reduced row echelon form then

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

Multiplying \(A^{-1}\) to the right of both sides 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. \end{align*} \end{split}\]

So 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

\[\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}\]