134 CHAPTER 5. SOME FACTORIZATIONS
has this property. Recall also that if Ei equals the identity matrix except for having an ain a single column somewhere below the main diagonal, E−1
i is obtained by replacing the ain Ei with −a, thus explaining why we replace with −1 times the multiplier in computingL. In the case where A is a 3×m matrix, E−1
1 · · ·E−1p−1E
−1p is of the form 1 0 0
a 1 0
0 0 1
1 0 0
0 1 0
b 0 1
1 0 0
0 1 0
0 c 1
=
1 0 0
a 1 0
b c 1
.
Note that scanning from left to right, the first two in the product involve changes in theidentity only in the first column while in the third matrix, the change is only in the second.If the entries in the first column had been zeroed out in a different order, the followingwould have resulted. 1 0 0
0 1 0
b 0 1
1 0 0
a 1 0
0 0 1
1 0 0
0 1 0
0 c 1
=
1 0 0
a 1 0
b c 1
However, it is important to be working from the left to the right, one column at a time.
A similar observation holds in any dimension. Multiplying the elementary matrices whichinvolve a change only in the jth column you obtain A equal to an upper triangular, n×mmatrix U which is multiplied by a sequence of lower triangular matrices on its left which isof the following form, in which the aij are negatives of multipliers used in row reducing toan upper triangular matrix.
1 0 · · · 0
a11 1...
.... . . 0
a1,n−1 0 · · · 1
1 0 · · · 0
0 1...
......
. . . 0
0 a2,n−2 · · · 1
· · ·
1 0 · · · 0
0 1...
.... . . 0
0 · · · an,n−1 1
From the matrix multiplication, this product equals
1
a11 1...
. . .
a1,n−1 · · · an,n−1 1
Notice how the end result of the matrix multiplication made no change in the aij . It just
filled in the empty spaces with the aij which occurred in one of the matrices in the product.This is why, in computing L, it is sufficient to begin with the left column and work columnby column toward the right, replacing entries with the negative of the multiplier used in therow operation which produces a zero in that entry.
5.6 Existence for the PLU Factorization
Here I will consider an invertible n × n matrix and show that such a matrix always hasa PLU factorization. More general matrices could also be considered but this is all I willpresent.