Linear Algebra and Its Applications, Exercise 1.5.12

Exercise 1.5.12. Could A be factored into the product UL where U is upper triangular and L is lower triangular, instead of being factored into the product LU? If so, how could this other factorization be carried out? Would U and L be the same in both cases?

Answer: The matrix A can be factored into UL by doing elimination in reverse, starting at row n of A and continuing through rows n-1, n-2, and so on, up to row 1, and trying to produce zeros starting from column n on down. For example, in the first steps of such elimination a multiple of row n would be subtracted from row n-1 in order to produce a zero in position n-1,n; a multiple of row n would then be subtracted from row n-2 in order to produce a zero in position n-2,n; and so on. This produces a lower triangular matrix.

The multipliers from the reverse elimination steps are used to create an upper triangular matrix, in analogous manner to regular elimination: When subtracting a multiple of row n from row n-1 we put the multiplier in position n-1,n of the lower triangular matrix; when subtracting a multiple of row n from row n-2 we put the multiplier in position n-2,n of the lower triangular matrix; and so on. The upper triangular matrix has ones on the diagonal.

As an example, consider the matrix defined at the beginning of section 15:

A = \begin{bmatrix} 2&1&1 \\ 4&-6&0 \\ -2&7&2 \end{bmatrix}

The reverse elimination steps would go as follows. At each step we construct the upper triangular matrix using the multipliers used in the corresponding elimination step.

The first step is null because the entry in the 2,3 position of A is already zero. The intermediate matrices are as follows, with the upper triangular matrix having a zero in the 2,3 position and the other entries being yet undetermined:

\begin{bmatrix} 2&1&1 \\ 4&-6&0 \\ -2&7&2 \end{bmatrix} \quad \begin{bmatrix} 1&?&? \\ 0&1&0 \\ 0&0&1 \end{bmatrix}

For the second step we subtract \frac{1}{2} times row 3 from row 1, and put the multiplier \frac{1}{2} in the 1,3 position of the upper triangular matrix:

\begin{bmatrix} 3&-\frac{5}{2}&0 \\ 4&-6&0 \\ -2&7&2 \end{bmatrix} \quad \begin{bmatrix} 1&?&\frac{1}{2} \\ 0&1&0 \\ 0&0&1 \end{bmatrix}

For the third step we subtract \frac{5}{12} times row 2 from row 1, and put the multiplier \frac{5}{12} in the 1,2 position of the upper triangular matrix. This completes elimination and produces the final lower triangular and upper triangular matrices L and U respectively:

L = \begin{bmatrix} \frac{4}{3}&0&0 \\ 4&-6&0 \\ -2&7&2 \end{bmatrix} \quad U = \begin{bmatrix} 1&\frac{5}{12}&\frac{1}{2} \\ 0&1&0 \\ 0&0&1 \end{bmatrix}

We now compute the product UL:

UL = \begin{bmatrix} 1&\frac{5}{12}&\frac{1}{2} \\ 0&1&0 \\ 0&0&1 \end{bmatrix} \begin{bmatrix} \frac{4}{3}&0&0 \\ 4&-6&0 \\ -2&7&2 \end{bmatrix} = \begin{bmatrix} 2&1&1 \\ 4&-6&0 \\ -2&7&2 \end{bmatrix} = A

So we have found U and L such that A = UL. Note that if we reverse the order of the factors we have

LU = \begin{bmatrix} \frac{4}{3}&0&0 \\ 4&-6&0 \\ -2&7&2 \end{bmatrix} \begin{bmatrix} 1&\frac{5}{12}&\frac{1}{2} \\ 0&1&0 \\ 0&0&1 \end{bmatrix} = \begin{bmatrix} \frac{4}{3}&\frac{5}{9}&\frac{2}{3} \\ 4&-\frac{13}{3}&2 \\ -2&\frac{37}{6}&1 \end{bmatrix} \ne A

So if A = UL it does not necessarily follow that A = LU, or vice versa—and indeed we would not expect this in general, since matrix multiplication is not commutative.

Extra credit: The matrices L and U found via reverse elimination are not exactly in the form we have otherwise been using, since L does not have diagonal entries equal to 1. We can transform L to the proper form by factoring it into a diagonal matrix D times a new lower triangular matrix. We can then multiply the matrix U by D to obtain a new upper triangular matrix.

In our example we have

L = \begin{bmatrix} \frac{4}{3}&0&0 \\ 4&-6&0 \\ -2&7&2 \end{bmatrix} = \begin{bmatrix} \frac{4}{3}&& \\ &-6& \\ &&2 \end{bmatrix} \begin{bmatrix} 1&0&0 \\ -\frac{2}{3}&1&0 \\ -1&\frac{7}{2}&1 \end{bmatrix} = DL'

so that

UL = U(DL') = (UD)L' = \begin{bmatrix} 1&\frac{5}{12}&\frac{1}{2} \\ 0&1&0 \\ 0&0&1 \end{bmatrix} \begin{bmatrix} \frac{4}{3}&& \\ &-6& \\ &&2 \end{bmatrix} L'
\quad = \begin{bmatrix} \frac{4}{3}&-\frac{5}{2}&1 \\ 0&-6&0 \\ 0&0&2 \end{bmatrix} L' = U'L'

and

U'L' = \begin{bmatrix} \frac{4}{3}&-\frac{5}{2}&1 \\ 0&-6&0 \\ 0&0&2 \end{bmatrix} \begin{bmatrix} 1&0&0 \\ -\frac{2}{3}&1&0 \\ -1&\frac{7}{2}&1 \end{bmatrix} = \begin{bmatrix} 2&1&1 \\ 4&-6&0 \\ -2&7&2 \end{bmatrix} = A

Thus U'L' is another factoring of A, this time into an upper triangular matrix and a lower triangular matrix with ones on the diagonal. Again if we reverse the order of multiplication then the product L'U' is no longer a factoring:

L'U' = \begin{bmatrix} 1&0&0 \\ -\frac{2}{3}&1&0 \\ -1&\frac{7}{2}&1 \end{bmatrix} \begin{bmatrix} \frac{4}{3}&-\frac{5}{2}&1 \\ 0&-6&0 \\ 0&0&2 \end{bmatrix} = \begin{bmatrix} \frac{4}{3}&-\frac{5}{2}&1 \\ -\frac{8}{3}&-\frac{13}{3}&-\frac{2}{3} \\ -\frac{4}{3}&-\frac{37}{2}&1 \end{bmatrix} \ne A

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.

This entry was posted in linear algebra and tagged , , . Bookmark the permalink.

4 Responses to Linear Algebra and Its Applications, Exercise 1.5.12

  1. Swagatika says:

    Thank You! It was really helpful 🙂

  2. hecker says:

    I’m glad you found this blog post useful. Thank you for linking to it from your own blog post.

  3. Optimus says:

    Thank you for solving this problem. It was really helpful.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s