How to find the inverse of a matrix (idea)

The proof of the method outlined by koala is quite simple. The method claims that if a sequence L of row operations turns a square matrix A into the identity then applying that same sequence L to the identity yields A^-1.

To prove this, we are first going to consider the matrices L_ij(λ), which are such that:
l_ij = λ
if p=q then l_pq=1
else l_pq=0

so for example, if we are dealing with 3 x 3 matrices, then

       /1 0 4\
L13(4)=|0 1 0 |
       \0 0 1/

Let us now consider the product B=L_ij(λ)A.
We know our summation convention:
b_pq=l_pka_kq

• if we have i=j then :
  • if p = i then b_iq=l_{i k}a_kq
    l_{i k} = 0 if i ≠ k, therefore b_iq = l_iia_iq=λa_iq
  • if p ≠ i then the above remains true, except that l_pp = 1, therefore b_pq = a_pq
  From this it is clear that multiplying A by L_ii(λ) multiplies the ith row of A by λ and leaving the other rows untouched.
• if i ≠ j then we can see that if p = i then b_iq=l_ika_kq =l_iia_iq + l_ija_jq=a_iq + λa_jq
  multiplying A by L_ij(λ) is adding λ times the jth row of A to the ith row, leaving the rest untouched.

Thus we can perform any of the row operations ""multiply a row by λ" and "add λ times a row to another row" by multiplying A by some matrix L_ij(λ). Note also that for all the row operations used in this method the L_ij(λ) are triangular with non zero terms on the diagonal : they are invertible.

We need one more type of matrix : one that will allow us to swap the ith and jth row. Fortunately, this is not too difficult. we simply have S_ij(with i ≠ j) which is such that :
s_ij = 1
s_ji = 1
s_ii = 0
s_jj = 0
and all the other terms on the diagonal are 1. You may wish to check for yourself that this matrix does what I claim, and that it is invertible.

We can now perform all the row operations needed by multiplying by an invertible matrix. So what our method is actually doing is finding a series of m invertible matrices such that L_m...L₂L₁A= I
L_m...L₂L₁ represents our sequence of row operations. Multiplying on the right side by A^-1 yields L_m...L₂L₁I= A^-1, which is what we wanted : performing our sequence of row operations on the identity gives us A^-1.

You may also be interested in knowing what happens if this method is applied to a singular matrix. What will happen is that eventually you will have a row with nothing but zeros, it will not be possible to transform the matrix into the identity.