Matrix Inverse Algorithm

Algorithm

The matrix inverse algorithm is an algorithm which either:

$(1): \quad$ converts a matrix into its inverse, if it exists

or:

$(2): \quad$ determines that such an inverse does not exist.

Let $\mathbf A$ be the $n \times n$ square matrix in question.

Let $\mathbf I$ be the unit matrix of order $n$.

Step $0$: Create the augmented matrix $\begin {bmatrix} \mathbf A & \mathbf I \end {bmatrix}$.

Step $1$: Perform elementary row operations until $\begin {bmatrix} \mathbf A & \mathbf I \end {bmatrix}$ is in reduced echelon form.

By Matrix is Row Equivalent to Reduced Echelon Matrix, this is possible.

By Reduced Echelon Matrix is Unique, this process is well-defined.

Call this new augmented matrix $\begin {bmatrix} \mathbf H & \mathbf C \end {bmatrix}$.

Step $2$:

If $\mathbf H = \mathbf I$, then take $\mathbf C = \mathbf A^{-1}$.

If $\mathbf H \ne \mathbf I$, $\mathbf A$ is not invertible.

Proof

Suppose $\begin {bmatrix} \mathbf A & \mathbf I \end {bmatrix}$ can be transformed into an upper triangular matrix with no zeroes on its main diagonal.

Then from Identity Matrix from Upper Triangular Matrix, it can further be transformed into $\begin {bmatrix} \mathbf H & \mathbf C \end {bmatrix}$ where $\mathbf H = \mathbf I$.

From Row Operation is Equivalent to Pre-Multiplication by Product of Elementary Matrices, the row operation to convert $\begin {bmatrix} \mathbf A & \mathbf I \end {bmatrix}$ to $\begin {bmatrix} \mathbf H & \mathbf C \end {bmatrix}$ is equivalent to the matrix product of the elementary row matrices corresponding to the sequence of elementary row operations that compose that row operation.

Let $\mathbf R$ be that matrix corresponding to that row operation.

Because $\mathbf H = \mathbf I$, it follows that:

$\mathbf R \mathbf A = \mathbf I$

and so $\mathbf R$ is the inverse of $\mathbf A$.

That is:

$\mathbf R = \mathbf A^{-1}$

We also have, from the action of $\mathbf R$ on the right hand side of the augmented matrix $\begin {bmatrix} \mathbf A & \mathbf I \end {bmatrix}$ that:

$\mathbf R \mathbf I = \mathbf C$

and so:

$\mathbf C = \mathbf R = \mathbf A^{-1}$

$\Box$

Now suppose that $\mathbf H \ne \mathbf I$.

This needs considerable tedious hard slog to complete it. In particular: It remains to be shown that in such a case $\mathbf A$ is not invertible. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Finish}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Examples

Arbitrary Matrix $1$

Let $\mathbf A$ be the (square) matrix defined as:

$\mathbf A = \begin {pmatrix}

1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ \end {pmatrix}$

Then its inverse $\mathbf A^{-1}$ is:

$\mathbf A^{-1} = \begin {pmatrix}

1 & -1 & 1 & -1 \\ 0 & 1 & -1 & 1 \\ 0 & 0 & 1 & -1 \\ 0 & 0 & 0 & 1 \\ \end {pmatrix}$

Arbitrary Matrix $2$

Let $\mathbf A$ be the (square) matrix defined as:

$\mathbf A = \begin {pmatrix}

1 &  0 & -1 \\

-1 & 1 & 0 \\

0 & -1 &  0 \\

\end {pmatrix}$

Then its inverse $\mathbf A^{-1}$ is:

$\mathbf A^{-1} = \begin {pmatrix}

0 & -1 & -1 \\
0 &  0 & -1 \\

-1 & -1 & -1 \\ \end {pmatrix}$

Arbitrary Matrix $3$

Let $\mathbf A$ be the (square) matrix defined as:

$\mathbf A = \begin {pmatrix}

1 &  2 & 0 \\
0 & -1 & 2 \\

-1 & 2 & 0 \\ \end {pmatrix}$

Then its inverse $\mathbf A^{-1}$ is:

$\mathbf A^{-1} = \begin {pmatrix}

\dfrac 1 2 & 0 & -\dfrac 1 2 \\ \dfrac 1 4 & 0 & \dfrac 1 4 \\ \dfrac 1 8 & \dfrac 1 2 & \dfrac 1 8 \\ \end {pmatrix}$

Sources

• 1998: Richard Kaye and Robert Wilson: Linear Algebra ... (previous) ... (next): Part $\text I$: Matrices and vector spaces: $1$ Matrices: $1.5$ Row and column operations