Matrix Inverse by the Elimination Method

Given two square matrices of the same size, \(\ \boldsymbol{A}=[\,a_{ij}\,]_{n\times n}\ \,\text{and}\ \, \boldsymbol{B}=[\,b_{ij}\,]_{n\times n}\ \,\text{in}\ \,M_n(K)\,,\ \) \(\\\) we shall use the term 2-block for the matrix formed by appending \(\,\boldsymbol{B}\,\) onto the right side of \(\ \boldsymbol{A}:\)

\[\begin{split}\left[\,\boldsymbol{A}\,|\,\boldsymbol{B}\,\right]\ \,:\,=\ \, \left[\begin{array}{cccccc} a_{11} & \ldots & a_{1n} & b_{11} & \ldots & b_{1n} \\ a_{21} & \ldots & a_{2n} & b_{21} & \ldots & b_{2n} \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ a_{n1} & \ldots & a_{nn} & b_{n1} & \ldots & b_{nn} \end{array}\right]\,\in\,M_{n\times 2n}(K)\,.\end{split}\]

Lemma. \(\,\)

We assume, as above, that \(\ \boldsymbol{A},\boldsymbol{B}\in M_n(K)\,.\)

1. \(\,\) If \(\ O\ \) is a row elementary operation, \(\,\) then \(\ \,O\,\left[\,\boldsymbol{A}\,|\,\boldsymbol{B}\,\right]\ =\ \left[\,O\boldsymbol{A}\,|\,O\boldsymbol{B}\,\right]\,.\)

2. \(\,\) Let \(\ \boldsymbol{C}\in M_n(K)\,.\ \,\) Then \(\ \,\boldsymbol{C}\, \left[\,\boldsymbol{A}\,|\,\boldsymbol{B}\,\right]\,=\, \left[\;\boldsymbol{C}\boldsymbol{A}\,|\, \boldsymbol{C}\boldsymbol{B}\;\right]\,.\)

Whereas the first statement of the Lemma is obvious, the second one may be easily validated on the grounds of the Column Rule of Matrix Multiplication.

Now suppose that \(\,\boldsymbol{A}\in M_n(K)\,\) is an invertible matrix, and that the consecutive elementary operations \(\,O_1\,,O_2,\,\dots,\,O_k\,,\ \) represented by elementary matrices \(\,\boldsymbol{E}_1,\boldsymbol{E}_2,\dots,\boldsymbol{E}_k\in M_n(K),\,\) transform \(\,\boldsymbol{A}\,\) into the reduced row echelon form (the latter is the identity matrix):

(1)\[O_k\dots O_2\,O_1\ \boldsymbol{A}\ =\ \boldsymbol{E}_k\dots\boldsymbol{E}_2\,\boldsymbol{E}_1\,\boldsymbol{A}\ =\ \boldsymbol{I}_n\,.\]

We note immediately that

(2)\[\boldsymbol{E}_k\dots\boldsymbol{E}_2\,\boldsymbol{E}_1\ =\ \boldsymbol{A}^{-1}\,.\]

Let’s apply the operations \(\,O_1\,,O_2,\,\dots,\,O_k\ \) to the 2-block \(\,\left[\,\boldsymbol{A}\,|\,\boldsymbol{I}_n\,\right].\,\) \(\\\) Using the Lemma, Theorem 2. as well as Eqs (1) and (2), we get

\[ \begin{align}\begin{aligned}O_k\dots O_2\,O_1\ \left[\, \boldsymbol{A}\,|\,\boldsymbol{I}_n\,\right]\ \,=\ \, \left[\ O_k\dots O_2\,O_1\ \boldsymbol{A}\ |\ O_k\dots O_2\,O_1\ \boldsymbol{I}_n\ \right]\ \,=\\=\ \, \left[\ \boldsymbol{E}_k\dots \boldsymbol{E}_2\, \boldsymbol{E}_1\ \boldsymbol{A}\ |\ \boldsymbol{E}_k\dots \boldsymbol{E}_2\, \boldsymbol{E}_1\ \boldsymbol{I}_n\ \right]\ \,=\ \, \left[\ \boldsymbol{A}^{-1}\boldsymbol{A}\ |\ \boldsymbol{A}^{-1}\boldsymbol{I}_n\ \right]\ =\ \left[\,\boldsymbol{I}_n\;|\;\boldsymbol{A}^{-1}\,\right]\,.\end{aligned}\end{align} \]

That way we have come up with a practical recipe to obtain the inverse of a matrix.

Proposition 3. \(\,\) Matrix Inversion Algorithm \(\,\)

Let \(\,\boldsymbol{A}\in M_n(K)\,\) be an invertible matrix. \(\\\) To find its inverse, create the 2-block \(\,\left[\,\boldsymbol{A}\,|\,\boldsymbol{I}_n\,\right]\,\) and perform elementary row operations which transform the first segment of the 2-block into the identity matrix. Then the second segment turns out to be \(\,\boldsymbol{A}^{-1}\,.\)

Example. \(\,\) Find the inverse of \(\ \boldsymbol{A}\ =\ \left[\begin{array}{rrrr} 2 & 0 & -1 & 1 \\ 1 & 1 & -1 & 0 \\ -1 & 0 & 6 & 1 \\ 1 & 0 & 1 & 1 \end{array}\right]\,.\) \(\\\)

The Sage code calculates \(\,\boldsymbol{A}^{-1}\,\) and checks the result:

sage: A = matrix(QQ,[[ 2, 0,-1, 1],
                     [ 1, 1,-1, 0],
                     [-1, 0, 6, 1],
                     [ 1, 0, 1, 1]])

# Create the 2-block [A|I]:
sage: AI = A.augment(identity_matrix(QQ,4))

# Transform [A|I] into [I|A^(-1)]:
sage: IA_1 = AI.rref()

# Select the second segment of the 2-block
# (columns starting from 4. to the last):
sage: A_1 = IA_1[:,4:]

# Display the product of the original matrix
# and its inverse:
sage: table([[A, '*', A_1, '=', A * A_1]])

The output reads:

\[\begin{split}\left[\begin{array}{rrrr} 2 & 0 & -1 & 1 \\ 1 & 1 & -1 & 0 \\ -1 & 0 & 6 & 1 \\ 1 & 0 & 1 & 1 \end{array}\right]\ \ *\ \ \left[\begin{array}{rrrr} 5 & 0 & 2 & -7 \\ -3 & 1 & -1 & 4 \\ 2 & 0 & 1 & -3 \\ -7 & 0 & -3 & 11 \end{array}\right] \quad = \quad\left[\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right]\end{split}\]

The matrix \(\,\boldsymbol{A}^{-1}\,\) in question is given as the second factor on the left-hand side.