23. Elementary matrices, 2

Lemma:

0.12 E_{i j} (lambda) is invertible with inverse E_{i j} (minus lambda) and E_i (lambda) is invertible with inverse E_i(one over lambda) (recall that lambda is nonzero for type II elementary matrices).

1.02 We'll prove it for 2-by-2 matrices to save ourselves from all the dots in the last few proofs. For the first: E_{1 2}(lambda) E_{1 2}(minus lambda) equals 1, lambda; 0, 1 times 1, minus lambda; 0, 1, which equals 1, lambda minus lambda; 0, 1, which equals the identity. For the second: E_1(lambda) times E_1(one over lambda) equals lambda, 0; 0, 1 times 1 over lambda, 0; 0, 1, which equals lambda over lambda, 0; 0, 1, which equals the identity.

2.50 We now proceed to the proof of the theorem:

Theorem:

If A is a matrix and you use row operations on A bar I until you get B bar C with B in reduced echelon form then:

if B is I then A is invertible with inverse C;
if B is not the identity then A is not invertible.

4.28 Put A into reduced echelon form by performing row operations. Each row operation corresponds to multiplying A on the left by an elementary matrix. Therefore B = M_k times dot dot dot times M_1 for some sequence of elementary matrices M_i.

6.04 We're simultaneously performing row operations on both sides of the bar in the augmented matrix, so C = M_k times dot dot dot times M_1 times I equals M_k times dot dot dot times M_1, so C is a product of elementary matrices. Moreover, B = M_k times dot dot dot times M_1 times A, which equals C A.

6.54 If B = I then C A = I and A is invertible with A inverse equals C.

7.27 If B is nonzero, it needs to have a row of zeros. Indeed, suppose B is an n-by-n matrix in echelon form. If all rows are nonzero then there are n leading entries, which have to move to the right as you go down, so they have to live on the diagonal, which forces your matrix to be the identity.

8.40 Therefore there is a free variable in the solution to B v = 0 (equivalently A v = 0). Therefore there is a whole line's worth of solutions, so there is at least one v is nonzero such that A v = 0. If A were invertible then v = A inverse times 0, which equals 0, which is a contradiction. Therefore A is not invertible.

Corollary:

10.13 A product of elementary matrices is invertible; conversely, any invertible matrix is a product of elementary matrices.

Recall that elementary matrices are invertible and their inverses are again elementary matrices.

If M_k times dot dot dot times M_1 is a product of elementary matrices then the inbverse of the product M_k times dot dot dot times M_1 is M_1 inverse times dot dot dot times M_k inverse, so it is invertible. Conversely, if A is invertible then its inverse has the form M_k times dot dot dot times M_1 for some sequence of elementary matrices (as we just saw in the previous proof). Therefore A equals M_1 inverse times dot dot dot times M_k inverse is a product of elementary matrices.