Why does elementary row operation on combination of Identity matrix and invertible matrix yields inverse matrix?

Question

Why does elementary row operation on combination of Identity matrix and invertible matrix yields inverse matrix?
$$A = \begin{pmatrix} 1 & 3\\ 4 & 2 \end{pmatrix}$$

if we combine $A$ with $I_{2\times 2}$ in which $I$ is an identity matrix, and do elementary row operation on it to get identity matrix on the other side, the opposite side(block) yields out the inverse of the matrix.
The question is, why is it true?

Answer 1

Consider a matrix in block form $(A|B)$. Let's do an elementary transformation. This amounts to multiplying the whole thing by an elementary matrix $E$ from the left. The result of that single operation is $$ (A'|B')=E(A|B)=(EA|EB). $$ If we assume that $B$ is invertible, then so is $B'$, because the elementary matrices are all invertible. We also observe that $B'^{-1}A'=B^{-1}A$, because $$ B'^{-1}A'=(EB)^{-1}(EA)=(B^{-1}E^{-1})(EA)=B^{-1}A.\qquad(*) $$ This easily generalizes to a sequence of elementary row operations $E_1,E_2,\ldots,E_n$. Namely, if $A_0=A, B_0=I$ and $A_{n}=E_nE_{n-1}\cdots E_2E_1A_0$ and $B_{n}=E_nE_{n-1}\cdots E_2E_1B_0$, then we have $$ B_{n}^{-1}A_{n}=B_0^{-1}A_0.\qquad(**) $$ Proof goes by induction on $n$, and $(*)$ is both the base case and the inductive step (don't you love it when that happens).

Anyway, if for some sequence of elementary matrices we have $A_{n}=I$, then ... well, you check what equation $(**)$ says about $B_n$ in that case.

Answer 2

Great question.

The reason why this is true is because, if a given matrix $A$ is invertible, then there exists a sequence of matrices $E_1, E_2, \dots, E_m$ such that

$$E_m E_{m-1} \cdots E_2 E_1 A = A^{-1}$$

We call these matrices elementary matrices. These matrices are in charge of the row operations that we can do on matrices, such as swapping rows, multiplying one row by a constant, or even multiplying one row by a constant and adding it to another row (exactly what we do in Guassian elimination). For example, consider the matrix

$$E_1 = \left( \begin{array}{rc} 1 & 0 \\ -4 & 1 \end{array} \right)$$

If we left-hand multiply your matrix $A$ by $E_1$, we get

$$\left( \begin{array}{rc} 1 & 0 \\ -4 & 1 \end{array} \right) \left( \begin{array}{cc} 1 & 3 \\ 4 & 2 \end{array} \right) = \left( \begin{array}{cr} 1 & 3 \\ 0 & -10 \end{array} \right)$$

which is the matrix we get after the first step Guassian elimination on your matrix $A$! But look closely: if you're trying to find the inverse of $A$ by attaching the identity to the right and row-reducing $A$ down to the identity, then $E_1$ pops up on the right (in place of the identity you attached) after your first step.

Now, consider

$$E_2 = \left( \begin{array}{rr} 1 & 0 \\ 0 & -1/10 \end{array} \right)$$

and observe that

$$E_2 E_1 A = \left( \begin{array}{rr} 1 & 0 \\ 0 & -1/10 \end{array} \right) \left( \begin{array}{cr} 1 & 3 \\ 0 & -10 \end{array} \right) = \left( \begin{array}{cc} 1 & 3 \\ 0 & 1 \end{array} \right)$$

which is the matrix you'd get after multiplying the second row through by $-1/10$, something that might be useful in our Guassian elimination because we want $A$ to eventually be the identity. If you do that in your steps of trying to invert $A$, notice that, after multiplying the second row through, the matrix attached to the right hand side becomes

$$E_2 E_1 = \left( \begin{array}{cc} 1 & 0 \\ 2/5 & -1/10 \end{array} \right)$$

Finally, consider

$$ E_3 = \left( \begin{array}{cr} 1 & -3 \\ 0 & 1 \end{array} \right)$$

and observe that

$$E_3 E_2 E_1 A = \left( \begin{array}{cr} 1 & -3 \\ 0 & 1 \end{array} \right) \left( \begin{array}{cc} 1 & 3 \\ 0 & 1 \end{array} \right) = \left( \begin{array}{cr} 1 & 0 \\ 0 & 1 \end{array} \right)$$

which is the matrix you get after your final step of Guassian elimination of $A$ (multiplying the second row by $-3$ and adding it to the first row of $A$). But look!

$$E_3 E_2 E_1 = \left( \begin{array}{cr} 1 & -3 \\ 0 & 1 \end{array} \right)\left( \begin{array}{cc} 1 & 0 \\ 2/5 & -1/10 \end{array} \right) = \left( \begin{array}{cr} -1/5 & 3/10 \\ 2/5 & -1/10 \end{array} \right)$$

which is the inverse of $A$, and it also happened to pop on the right-hand side in place of the identity that you initially attached.

Basically, when you do row operations with an identity matrix attached to the right, you're recording all of these steps as elementary matrices. When you apply multiple row operations, these steps accumulate on the right hand side. This accumulation process is the same as multiplying the elementary matrices that govern these Guassian elimination steps. In the end, once $A$ has been reduced down to the identity and all of the steps have been recorded, you get the identity, and this is the same thing as multiplying all of the elementary matrices that you needed together.