Why does the Gaussian-Jordan elimination work when finding the inverse matrix?

Question

In order to find the inverse matrix $A^{-1}$, one can apply Gaussian-Jordan elimination to the augmented matrix $$(A \mid I)$$ to obtain $$(I \mid C),$$ where $C$ is indeed $A^{-1}$. However, I fail to see why this actually works, and reading this answer didn't really clear things up for me.

Answer 1

You have three types of what are called elementary matrices, representing row changes, scaling, and adding a multiple of one row to another. If you left multiply a matrix by an elementary matrix, you perform that operation; for example, with a 3x3 matrix, the elementary matrix $$\pmatrix{1&0&0\\5&1&0\\0&0&1}$$ adds 5 times the first row to the second (can you figure out how the other two look?). If a matrix $A$ is invertible, there are a set of steps to reduce it to the identity matrix, which also means that we have some set of elementary matrices such that $$E_nE_{n-1}\dots E_2E_1A=I$$ However, by right-multiplying by $A^{-1}$ (since $A$ is invertible), we get $$E_nE_{n-1}\dots E_2E_1I=A^{-1}$$ So by performing the steps to reduce $A$ to the identity matrix, those same steps performed on the identity matrix create the inverse of $A$. If we start with $(A|I)$ and reduce the left side to the identity matrix, then we would end up with $(I|A^{-1})$ based on the above information, which explains the algorithm.

Answer 2

You want to find a matrix $B$ such that $BA = I$. $B$ can be written as a product of elementary matrices iff it is invertible. Hence we attempt to obtain $B$ by left-multiplying $A$ by elementary matrices until it becomes $I$. All we have to do is to keep track of the product of those elementary matrices. But that is exactly what we are doing when we left-multiply $I$ by those same elementary matrices in the same order. This is what is happening with the augmented matrix.

Answer 3

Let me make it concrete in the following example(@pauly-b's answer is much better).

Suppose that 4 apples(any two are the same price) and 3 bananas(any two are the same price) in city A would cost 10 euros, and 3 apples and 2 bananas 7 euros. Let's calculate how much it would cost for 1 apple and 1 banana in A? We don't need to calculate the price for each fruit, the answer is just 10 minus 7.

$\pmatrix{4&3\\ 3&2} \cdot \pmatrix{a_A\\ b_A} = \pmatrix{10\\ 7}$

We apply Gaussian elimination by $R_1 = R_1 − R_2$

$\pmatrix{1&1\\ 3&2} \cdot \pmatrix{a_A\\ b_A} = \pmatrix{3\\ 7}$

Obviously, the above two equations are equivalent. By the same token we can perform more such operations to make the matrix on the LHS an identity one.

$\pmatrix{1&0\\ 0&1} \cdot \pmatrix{a_A\\ b_A} = \pmatrix{1\\ 2}$

And we get $a_A$ and $b_A$: 1 and 2. We denote the above by

$\left(\begin{array}{cc|c} 4 & 3 & 10 \\ 3 & 2 & 7 \\ \end{array}\right) \rightarrow \left(\begin{array}{cc|c} 1 & 0 & 1 \\ 0 & 1 & 2 \\ \end{array}\right) $

---

Let's assume that we are in a different city B and the prices change, and we get

$\pmatrix{4&3\\ 3&2} \cdot \pmatrix{a_B\\ b_B} = \pmatrix{11\\ 8}$

Following the same process, we can get $a_B$ and $b_B$: 2 and 1.

---

We can combine the two and get

$\pmatrix{4&3\\ 3&2} \cdot \pmatrix{a_A&a_B\\ b_A&b_B} = \pmatrix{10&11\\ 7&8}$

Performing Gaussian elimination we get

$\pmatrix{a_A&a_B\\ b_A&b_B} = \pmatrix{1&2\\ 2&1}$

---

What if we change $\pmatrix{10&11\\ 7&8}$ in $\pmatrix{4&3\\ 3&2} \cdot \pmatrix{a_A&a_B\\ b_A&b_B} = \pmatrix{10&11\\ 7&8}$ to $\pmatrix{1&0\\ 0&1}$?

We get the following:

$\pmatrix{4&3\\ 3&2} \cdot \pmatrix{a_A&a_B\\ b_A&b_B} = \pmatrix{1&0\\ 0&1}$

After Gaussian elimination we get the inverse of $\pmatrix{4&3\\ 3&2}$: $\pmatrix{-2&3\\ 3&-4}$

And we can denote the above by

$\left(\begin{array}{cc|cc} 4 & 3 & 1&0 \\ 3 & 2 & 0&1 \\ \end{array}\right) \rightarrow \left(\begin{array}{cc|cc} 1 & 0 & -2 & 3 \\ 0 & 1 & 3 & -4 \\ \end{array}\right) $

References:

1. Gaussian Elimination
2. Going from Gaussian elimination to finding the inverse matrix