Why does the Gaussian-Jordan elimination work when finding the inverse matrix? 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.
 A: 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.
A: 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.
A: 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:

*

*Gaussian Elimination

*Going from Gaussian elimination to finding the inverse matrix
