Linear Algebra and Its Applications, Exercise 1.5.8

Exercise 1.5.8. This exercise continues the discussion in p. 33-34 regarding factorization of a 3×3 matrix A and the proof that A = LU. An alternative proof begins with the fact that row 3 of U is produced by taking row 3 of A and subtracting l_{31} times row 1 of U and l_{32} times row 2 of U. (Note that for simplicity we assume that no row exchanges are necessary.)

(a) Why do we subtract rows of U rather than rows of A?

(b) The above equation can be rearranged and restated as follows: row 3 of A is equal to the sum of l_{31} times row 1 of U, l_{32} times row 2 of U, and 1 times row 3 of U. Which rule of multiplication (from 1D on p. 25) makes this also equal to row 3 of LU?

Note that applying the results of (a) and (b) for the other rows of U completes the proof.

Answer: (a) By the time we apply elimination to row 3 of A we have already completed the elimination steps for rows 1 and 2 of A. The first step produced row 1 of U, and the second step produced row 2 of U. When we come to the elimination step for row 3 we are therefore subtracting multiples of rows of U, not rows of A.

By similar logic when performing an elimination step on any pivot row we have completed elimination on all the rows above it, and therefore any row subtracted from the pivot row (using the appropriate multiplier) is a row of U.

(b) From 1D part (iii) we have each row of the product matrix AB equal to the product of a row and a matrix; more specifically, row i of AB is equal to row i of A times the matrix B.

So for the product matrix LU we have row 3 of LU equal to row 3 of L times the matrix U.

Now we have

L = \begin{bmatrix} 1&0&0 \\ l_{21}&1&0 \\ l_{31}&l_{32}&1 \end{bmatrix}

so that row 3 of L consists of the entries l_{31}, l_{32}, and 1, and since U is upper triangular we have

U = \begin{bmatrix} u_{11}&u_{12}&u_{13} \\ 0&u_{22}&u_{23} \\ 0&0&u_{33} \end{bmatrix}

The product of row 3 of L and the matrix U (which is also row 3 of the product LU) is therefore

LU = \begin{bmatrix} l_{31}&l_{32}&1 \end{bmatrix} = \begin{bmatrix} u_{11}&u_{12}&u_{13} \\ 0&u_{22}&u_{23} \\ 0&0&u_{33} \end{bmatrix} = \begin{bmatrix} l_{31}u_{11}&l_{31}u_{12}+l_{32}u_{22}&l_{31}u_{13}+l_{32}u_{23}+u_{33} \end{bmatrix}

which can be expressed as

l_{31} \begin{bmatrix} u_{11}&u_{12}&u_{13} \end{bmatrix} +  l_{32} \begin{bmatrix} 0&u_{22}&u_{23} \end{bmatrix} + 1 \cdot \begin{bmatrix} 0&0&u_{33} \end{bmatrix}

But this is l_{31} times row 1 of U plus l_{32} times the row 2 of U plus 1 times row 3 of U, and from above we have this equal to row 3 of A. Therefore row 3 of LU is equal to row 3 of A.

By similar arguments we show that row 1 of LU is equal to row 1 of A, and row 2 of LU is equal to row 2 of A. Since each row of LU is equal to the corresponding row of A, we have A = LU.

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. Bookmark the permalink.

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