5.5. JUSTIFICATION FOR THE MULTIPLIER METHOD 133
Let Ux = y and consider PLy = b. In other words, solve, 1 0 0
0 0 1
0 1 0
1 0 0
4 1 0
1 0 1
y1
y2
y3
=
1
2
3
.
Then multiplying both sides by P gives 1 0 0
4 1 0
1 0 1
y1
y2
y3
=
1
3
2
and so
y =
y1
y2
y3
=
1
−1
1
.
Now Ux = y and so it only remains to solve
1 2 3 2
0 −5 −11 −7
0 0 0 −2
x1
x2
x3
x4
=
1
−1
1
which yields
x1
x2
x3
x4
=
15 + 7
5 t910 − 11
5 t
t
− 12
: t ∈ R.
5.5 Justification for the Multiplier Method
Why does the multiplier method work for finding an LU factorization? Suppose A is amatrix which has the property that the row reduced echelon form for A may be achievedusing only the row operations which involve replacing a row with itself added to a multipleof another row. It is not ever necessary to switch rows. Thus every row which is replacedusing this row operation in obtaining the echelon form may be modified by using a rowwhich is above it. Furthermore, in the multiplier method for finding the LU factorization,we zero out the elements below the pivot entry in first column and then the next and so onwhen scanning from the left. In terms of elementary matrices, this means the row operationsused to reduce A to upper triangular form correspond to multiplication on the left by lowertriangular matrices having all ones down the main diagonal and the sequence of elementarymatrices which row reduces A has the property that in scanning the list of elementarymatrices from the right to the left, this list consists of several matrices which involve onlychanges from the identity in the first column, then several which involve only changes fromthe identity in the second column and so forth. More precisely, Ep · · ·E1A = U where U isupper triangular, Ek having all zeros below the main diagonal except for a single column.
Therefore, A =
Will be L︷ ︸︸ ︷E−1
1 · · ·E−1p−1E
−1p U. You multiply the inverses in the reverse order. Now each
of the E−1i is also lower triangular with 1 down the main diagonal. Therefore their product