Question

22. (Reduced LU Factorization) With A as in the Practice Problem, i.e., \[A = \left[ {\begin{array}{*{20}{c}}{\bf{2}}&{ - {\bf{4}}}&{ - {\bf{2}}}&{\bf{3}}\\{\bf{6}}&{ - {\bf{9}}}&{ - {\bf{5}}}&{\bf{8}}\\{\bf{2}}&{ - {\bf{7}}}&{ - {\bf{3}}}&{\bf{9}}\\{\bf{4}}&{ - {\bf{2}}}&{ - {\bf{2}}}&{ - {\bf{1}}}\\{ - {\bf{6}}}&{\bf{3}}&{\bf{3}}&{\bf{4}}\end{array}} \right]\], find a \[{\bf{5}} \times {\bf{3}}\] matrix B and a \[{\bf{3}} \times {\bf{4}}\] matrix C such that \[A = BC\]. Generalize this idea to the case where A is \[m \times n\], \[A = LU\], and U has only three nonzero rows.

Short answer

Matrix \[B = \left[ {\begin{array}{*{20}{c}}1&0&0\\3&1&0\\1&{ - 1}&1\\2&2&{ - 1}\\{ - 3}&{ - 3}&2\end{array}} \right]\] and matrix \[C = \left[ {\begin{array}{*{20}{c}}2&{ - 4}&{ - 2}&3\\0&3&1&{ - 1}\\0&0&0&5\end{array}} \right]\] such that \[A = BC\]. For the case A is \[m \times n\], and U has only three nonzero rows, let B be the first three columns of Land Cbe the first three rows of U.

Step-by-step solution

Determine L

Since A has five rows, Lshould be \[5 \times 5\]. The first column of L is the first column of A, divided by the top pivot entry 2.

\[L = \left[ {\begin{array}{*{20}{c}}1&0&0&0&0\\3&1&0&0&0\\1&*&1&0&0\\2&*&*&1&0\\{ - 3}&*&*&*&1\end{array}} \right]\]

Reduce A into row echelon form

\[A = \left[ {\begin{array}{*{20}{c}}2&{ - 4}&{ - 2}&3\\6&{ - 9}&{ - 5}&8\\2&{ - 7}&{ - 3}&9\\4&{ - 2}&{ - 2}&{ - 1}\\{ - 6}&3&3&4\end{array}} \right]\]

At row 2, multiply row 1 by 3 and subtract it from row 2, i.e., \[{R_2} \to {R_2} - 3{R_1}\]; at row 3, subtract row 1 from row 3 i.e., \[{R_3} \to {R_3} - {R_1}\]; at row 4, multiply row 1 by 2 and subtract it from row 4, i.e., \[{R_4} \to {R_4} - 2{R_1}\]; and at row 5, multiply row 1 by 3 and add it to row 5, i.e., \[{R_5} \to {R_5} + 3{R_1}\]. Therefore,

\[ \sim \left[ {\begin{array}{*{20}{c}}2&{ - 4}&{ - 2}&3\\0&3&1&{ - 1}\\0&{ - 3}&{ - 1}&6\\0&6&2&{ - 7}\\0&{ - 9}&{ - 3}&{13}\end{array}} \right]\]

At row 3, add row 2 to row 3, i.e., \[{R_3} \to {R_2} + {R_3}\]; at row 4, multiply row 2 by 2 and subtract it from row 4, i.e., \[{R_4} \to {R_4} - 2{R_2}\]; and at row 5, multiply row 2 by 3 and add it to row 5, i.e., \[{R_5} \to {R_5} + 3{R_2}\]. Therefore,

\[ \sim \left[ {\begin{array}{*{20}{c}}2&{ - 4}&{ - 2}&3\\0&3&1&{ - 1}\\0&0&0&5\\0&0&0&{ - 5}\\0&0&0&{10}\end{array}} \right]\]

Here, row 3 has a pivot element 5. So, at row 4, add row 3 to row 4, i.e., \[{R_4} \to {R_3} + {R_4}\], and at row 5, multiply row 3 by 2 and subtract it from row 5, i.e., \[{R_5} \to {R_5} - 2{R_3}\]. Then,

\[ \sim \left[ {\begin{array}{*{20}{c}}2&{ - 4}&{ - 2}&3\\0&3&1&{ - 1}\\0&0&0&5\\0&0&0&0\\0&0&0&0\end{array}} \right] = U\]

At each pivot column \[\left[ {\begin{array}{*{20}{c}}2\\6\\2\\4\\{ - 6}\end{array}} \right]\], \[\left[ {\begin{array}{*{20}{c}}3\\{ - 3}\\6\\{ - 9}\end{array}} \right]\], and \[\left[ {\begin{array}{*{20}{c}}5\\{ - 5}\\{10}\end{array}} \right]\], divide them by pivots 2, 3, and 5, respectively. Thus, L can be written as:

\[L = \left[ {\begin{array}{*{20}{c}}1&0&0&0&0\\3&1&0&0&0\\1&{ - 1}&1&0&0\\2&2&{ - 1}&1&0\\{ - 3}&{ - 3}&2&0&1\end{array}} \right]\]

Determine B and C

Note that the last two rows of U contain only zeros. So, for LU, the last two columns of L will not be used. Thus, let B be the first three columns of L and C be the first three rows of U. That is

\[B = \left[ {\begin{array}{*{20}{c}}1&0&0\\3&1&0\\1&{ - 1}&1\\2&2&{ - 1}\\{ - 3}&{ - 3}&2\end{array}} \right]\]and \[C = \left[ {\begin{array}{*{20}{c}}2&{ - 4}&{ - 2}&3\\0&3&1&{ - 1}\\0&0&0&5\end{array}} \right]\]

Hence, \[A = LU = BC\].

Generalize the idea

For the case A is \[m \times n\], U has only three nonzero rows. So, the first three columns of L are only required. Hence, let B be the first three columns of Land Cbe the first three rows of U.