In this post we'll look at how to use Gauss-Jordan elimination to find the inverse of a matrix.
In Part 4 of this series we looked at how to perform elimination to solve for a single solution vector \(\xx\) in \(\A\xx=\bb\). Now we'll look at an extension of Gaussian elimination, called Gauss-Jordan elimination, which we can use to find the entire matrix \(\A^{-1}\) if it exists.
Suppose we have
\[ \A = \mat{1 & 2 & 3 \\ 1 & 3 & 5 \\ 2 & 7 & 9} \]
and we need to find its inverse. In other words, we want to find the matrix \(\A^{-1}\) such that \(\A\A^{-1}=\I\). Written another way, we want to find the column vectors \(\A^{-1}_i\) in
\[ \A[\A^{-1}_1 \A^{-1}_2 \A^{-1}_3] = \I. \]
This is equivalent to saying we need to solve three different systems:
\[ \begin{align*} \A\A^{-1}_1 &= \I_1 \\ \A\A^{-1}_2 &= \I_2 \\ \A\A^{-1}_3 &= \I_3 \end{align*} \]
To solve the first one, we'd write the right-hand side \(\I_1\) next to \(\A\) and proceed with elimination, e.g.,
\[ \mat{1 & 2 & 3 & 1 \\ 1 & 3 & 5 & 0 \\ 2 & 7 & 9 & 0}. \]
Once elimination and back-substitution have completed, the above would be transformed from \(\A\I_1\) to \(\I\A^{-1}_1\). Gauss-Jordan elimination works by solving all of these simultaneously, transforming \(\A\I\) to \(\I\A^{-1}\). We just need to write \(\A\I\) and then perform the elimination process on the augmented matrix:
\[ \mat{1 & 2 & 3 & 1 & 0 & 0 \\ 1 & 3 & 5 & 0 & 1 & 0 \\ 2 & 7 & 9 & 0 & 0 & 1} \]
The steps follow:
\[ \implies \mat{1 & 2 & 3 & 1 & 0 & 0 \\ 1 & 3 & 5 & 0 & 1 & 0 \\ 2 & 7 & 9 & 0 & 0 & 1} \implies \mat{1 & 2 & 3 & 1 & 0 & 0 \\ 0 & 1 & 2 & -1 & 1 & 0 \\ 2 & 7 & 9 & 0 & 0 & 1} \] \[ \implies \mat{1 & 2 & 3 & 1 & 0 & 0 \\ 0 & 1 & 2 & -1 & 1 & 0 \\ 0 & 3 & 3 & -2 & 0 & 1} \implies \mat{1 & 2 & 3 & 1 & 0 & 0 \\ 0 & 1 & 2 & -1 & 1 & 0 \\ 0 & 0 & -3 & 1 & -3 & 1} \] \[ \implies \mat{1 & 2 & 3 & 1 & 0 & 0 \\ 0 & 1 & 0 & -\tfrac{1}{3} & -1 & \tfrac{2}{3} \\ 0 & 0 & -3 & 1 & -3 & 1} \implies \mat{1 & 2 & 0 & 2 & -3 & 1 \\ 0 & 1 & 0 & -\tfrac{1}{3} & -1 & \tfrac{2}{3} \\ 0 & 0 & -3 & 1 & -3 & 1} \] \[ \implies \mat{1 & 0 & 0 & 2 \tfrac{2}{3} & -1 & -\tfrac{1}{3} \\ 0 & 1 & 0 & -\tfrac{1}{3} & -1 & \tfrac{2}{3} \\ 0 & 0 & -3 & 1 & -3 & 1} \]
Lastly, we divide each row by the diagonal on the left side to yield \(\I\A^{-1}\):
\[ \implies \mat{1 & 0 & 0 & 2 \tfrac{2}{3} & -1 & -\tfrac{1}{3} \\ 0 & 1 & 0 & -\tfrac{1}{3} & -1 & \tfrac{2}{3} \\ 0 & 0 & 1 & -\tfrac{1}{3} & 1 & -\tfrac{1}{3}} \]
In this post we've seen a technique for using Gaussian elimination as a building block to solve a more complex problem: rather than solving for a single vector, we solved for a whole matrix. In the next post in this series I'll cover \(\A=\L\D\U\) matrix factorization.