Matrix Inverse Algorithm

From ProofWiki
Jump to navigation Jump to search

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



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