# Why does the Gaussian-Jordan elimination works 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.

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.

• Very clear, thanks! Apr 19, 2015 at 9:53

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.

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: