# Matrix Inverse Algorithm

## Algorithm

The **matrix inverse algorithm** is an algorithm which either:

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

## 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