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.

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
