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 Lij(λ), which are such that:
lij = λ
if p=q then lpq=1
else lpq=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 biq=li kakq
li k = 0 if i ≠ k, therefore biq = liiaiq=λaiq -
if p ≠ i then the above remains true, except that lpp = 1, therefore bpq = apq
From this it is clear that multiplying A by Lii(λ) 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
biq=likakq
=liiaiq + lijajq=aiq + λajq
multiplying A by Lij(λ) 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 Sij(with i ≠ j) which is such that :
sij = 1
sji = 1
sii = 0
sjj = 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 Lm...L2L1A= I
Lm...L2L1 represents our sequence of row operations. Multiplying on the right side by A-1 yields Lm...L2L1I= 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.