This page is intended to be a part of the Numerical Analysis section of Math Online. Similar topics can also be found in the Linear Algebra section of the site.

Computing The Inverse of a Matrix with Gaussian Elimination

Recall that if we have a linear system of $n$ equations in $n$ variables, then if $A$ represents the corresponding $n \times n$ coefficient matrix of the system, $x$ represents the $n \times 1$ column matrix of the variables in the system, and $b$ represents the $n \times 1$ column matrix of the constants for the system, then the linear system itself can be written in the form $Ax = b$. Furthermore, if $A$ is an invertible matrix, then $A^{-1}$ exists, and so we can obtain the solution to our system of equations by multiplying both sides of $Ax = b$ from the left by $A^{-1}$ to get $x = A^{-1}b$, i.e, the unique solution to our system. Therefore, being able to determine the inverse of a square matrix (provided that it exists) is remarkable useful in solving linear systems of equations.

What's nice is that we can determine the inverse of a matrix using Gaussian Elimination. Let $A$ be an $n \times n$ matrix. Assume that the inverse of $A$ exists and let $B = A^{-1}$. Denote the columns of $B$ as $\bar{b_1}$, $\bar{b_2}$, …, $\bar{b_n}$. Therefore we can rewrite the inverse of $A$ as:

(1)

\begin{align} \quad B = (\bar{b_1} \: \bar{b_2} \: ... \: \bar{b_n} ) \end{align}

Furthermore, let $I_n$ be the $n \times n$ identity matrix and let $e_1$, $e_2$, …, $e_n$ be the columns of $I_n$. Now since $B$ is the inverse matrix of $A$, we have that $AB = I$ or in the notation we've just defined:

(2)

\begin{align} \quad A(\bar{b_1} \: \bar{b_2} \: ... \: \bar{b_n}) = (e_1, e_2, ..., e_n) \end{align}

(3)

\begin{align} \quad \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix} \begin{bmatrix} b_{11} & b_{12} & \cdots & b_{1n}\\ b_{21} & b_{22} & \cdots & b_{2n}\\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \cdots & b_{nn} \end{bmatrix} = \begin{bmatrix} 1 & 0 & \cdots & 0\\ 0 & 1 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix} \end{align}

Now the product of the matrix $A$ with the $k^{th}$ column matrix $\bar{b_k}$ produces an $n \times 1$ column matrix $A\bar{b_k}$:

(4)

\begin{align} \quad A \bar{b_k} = \begin{bmatrix} a_{11}b_{1k} + a_{12}b_{2k} + ... + a_{1n}b_{nk}\\ a_{21}b_{1k} + a_{22}b_{2k} + ... + a_{2n}b_{nk}\\ \vdots \\ a_{n1}b_{1k} + a_{n2}b_{2k} + ... + a_{nn}b_{nk} \end{bmatrix} \end{align}

Therefore the equation $A(\bar{b_1} \: \bar{b_2} \: ... \: \bar{b_n}) = (e_1, e_2, ..., e_n )$ can be rewritten as:

(5)

\begin{align} \quad (A\bar{b_1} \: A\bar{b_2} \: ... \: A\bar{b_n}) = (e_1, e_2, ..., e_n) \end{align}

From the equation above, we see that $A\bar{b_1} = e_1$, $A\bar{b_2} = e_2$, …, $A\bar{b_n} = e_n$, and so the columns of the inverse matrix $B$ of $A$ are each solutions to linear systems:

(6)

\begin{align} \quad A \bar{b_k} = e_k \quad , \quad k = 1, 2, ..., n \end{align}

Now note that if we take the coefficient matrix $A$ and adjoin the identity matrix $I_n$, then the resulting augmented matrix is $[ \: A \: | \: I \: ]$, that is:

(7)

\begin{align} \quad [ \: A \: | \: I \: ] = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & 1 & 0 & \cdots & 0\\ a_{21} & a_{22} & \cdots & a_{2n} & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots\\ a_{n1} & a_{n2} & \cdots & a_{nn} & 0 & 0 & \cdots & 1 \end{bmatrix} \end{align}

Applying Gaussian Elimination will simultaneously account for the systems $A\bar{b_1} = e_1$, $A\bar{b_2} = e_2$, …, $A\bar{b_n} = e_n$. After Gaussian Elimination is successfully performed, we will obtain an augmented matrix in the form $[ \: I \: | \: B \: ]$ and so we will have obtained our inverse matrix $B$ of $A$.