Page 156 - Matrix Analysis & Applied Linear Algebra

150 Chapter 3 Matrix Algebra

submatrices implies that each A k possesses an LU factorization, and hence
A n = A must have an LU factorization.
Up to this point we have avoided dealing with row interchanges because if
a row interchange is needed to remove a zero pivot, then no LU factorization is
possible. However, we know from the discussion in §1.5 that practical computa-
tion necessitates row interchanges in the form of partial pivoting. So even if no
zero pivots emerge, it is usually the case that we must still somehow account for
row interchanges.
To understand the effects of row interchanges in the framework of an LU
decomposition, let T k = I − c k e T be an elementary lower-triangular matrix as
k
described in (3.10.2), and let E = I − uu T with u = e k+i − e k+j be the Type I
elementary interchange matrix associated with an interchange of rows k +i and
T
k + j. Notice that e E = e T because e T has 0’s in positions k + i and k + j.
k k k
2
This together with the fact that E = I guarantees
T
T
2
ET k E = E − Ec k e E = I − ˜ c k e , where ˜ c k = Ec k .
k
k
In other words, the matrix
˜
T k = ET k E = I − ˜ c k e T (3.10.14)
k
˜
is also an elementary lower-triangular matrix, and T k agrees with T k in all
positions except that the multipliers µ k+i and µ k+j have traded places. As be-
fore, assume we are row reducing an n × n nonsingular matrix A, but suppose
that an interchange of rows k + i and k + j is necessary immediately after the
k th stage so that the sequence of left-hand multiplications ET k T k−1 ··· T 1 is
2
2
applied to A. Since E = I, we may insert E to the right of each T to obtain
2
2
2
ET k T k−1 ··· T 1 = ET k E T k−1 E ··· E T 1 E 2
=(ET k E)(ET k−1 E) ··· (ET 1 E) E
˜ ˜
˜
= T k T k−1 ··· T 1 E.
In such a manner, the necessary interchange matrices E can be “factored” to
˜
the far-right-hand side, and the matrices T retain the desirable feature of be-
ing elementary lower-triangular matrices. Furthermore, (3.10.14) implies that
˜ ˜
˜
T k T k−1 ··· T 1 differs from T k T k−1 ··· T 1 only in the sense that the multipli-
ers in rows k + i and k + j have traded places. Therefore, row interchanges in
˜
˜ ˜
Gaussian elimination can be accounted for by writing T n−1 ··· T 2 T 1 PA = U,
where P is the product of all elementary interchange matrices used during the
˜
reduction and where the T k ’s are elementary lower-triangular matrices in which
the multipliers have been permuted according to the row interchanges that were
˜
implemented. Since all of the T k ’s are elementary lower-triangular matrices, we
may proceed along the same lines discussed in (3.10.4)—(3.10.6) to obtain
˜ −1
˜ −1 ˜ −1
PA = LU, where L = T T ··· T . (3.10.15)
1 2 n−1