Linear Algebra and Its Applications, Review Exercise 1.27

Review exercise 1.27. State whether the following are true or false. If true explain why, and if false provide a counterexample.

(1) If a matrix A can be factored as A = L_1U_1 = L_2U_2 where L_1 and L_2 are lower triangular with unit diagonals and U_1 and U_2 are upper triangular, then L_1 = L_2 and U_1 = U_2. (In other words, the factorization A = LU is unique.)

(2) If for a matrix A we have A^2 + A = I then A is invertible and A^{-1} = A + I.

(3) If all the diagonal entries of a matrix A are zero then A is singular.

Answer: (1) True. Since L_1 and L_2 are lower triangular with unit diagonal both matrices are invertible, and their inverses are also lower triangular with unit diagonal. (See the proof of this below at the end of the post.) Similarly since U_1 and U_2 are upper triangular with nonzero diagonal those matrices are invertible as well, and their inverses are also upper triangular with nonzero diagonal.

We then start with the equation L_1U_1 = L_2U_2 and multiply both sides by L_2^{-1} on the left and by U_1^{-1} on the right:

L_2^{-1}(L_1U_1)U_1^{-1} = L_2^{-1}(L_2U_2)U_1^{-1}

This equation reduces to L_2^{-1}L_1 = U_2U_1^{-1} = B where B is the product matrix. Now since B is the product of two lower triangular matrices with unit diagonal (i.e., L_2^{-1} and L_1), it itself is a lower triangular matrix with unit diagonal. Since B is the product of two upper triangular matrices (i.e., U_2 and U_1^{-1}), it is also an upper triangular matrix. Since B is both lower triangular and upper triangular it must be a diagonal matrix, and since its diagonal entries are all 1 we must have B = I.

Since L_2^{-1}L_1 = I we can multiply both sides on the left by L_2 to obtain  L_2L_2^{-1}L_1 = L_2I or L_1 = L_2. Similarly since U_2U_1^{-1} = I we can multiply both sides on the right by U_1 to obtain  U_2U_1^{-1}U_1 = IU_1 or U_2 = U_1. So the factorization A = LU is unique.

(2) True. Assume A^2 + A = I. We have I = A^2 + A = A(A + I) so that A + I is a right inverse for A. We also have I = A^2 + A = (A + I)A so that A + I is a left inverse for A. Since A+I is both a left and right inverse of A we know that A is invertible and that A^{-1} = A + I.

(3) False. The matrix

A = \begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix}

has zeros on the diagonal but is nonsingular. In fact we have

A^{-1} = \begin{bmatrix} 0&1 \\ 1&0 \end{bmatrix} = A

Proof of the result used in (1) above: Assume L is a lower triangular matrix with unit diagonal. That L is invertible can be seen from Gauss-Jordan elimination (here shown in a 4 by 4 example, although the argument generalizes to all n \ge 2):

\begin{bmatrix} 1&0&0&0&\vline&1&0&0&0 \\ x&1&0&0&\vline&0&1&0&0 \\ x&x&1&0&\vline&0&0&1&0 \\ x&x&x&1&\vline&0&0&0&1 \end{bmatrix}

Note that in forward elimination each of the diagonal entries of L will remain as is, since each of these entries has only zeros above it; each of the zero entries above the diagonal will remain unchanged as well, for the same reason. When forward elimination completes the left hand matrix will be the identity matrix since it will have zeros below the diagonal (from forward elimination), ones on the diagonal (as noted above), and zeroes above the diagonal (also as noted above). Gauss-Jordan elimination is thus guaranteed to complete successfully, so L is invertible.

The right-hand matrix at the end of Gauss-Jordan elimination will be the inverse of L. That matrix was produced from the identity matrix by forward elimination only, since backward elimination was not necessary. For the same reason noted above for the left-hand matrix, forward elimination will preserve the unit diagonal in the right-hand matrix and the zeros above it, with the only possible non-zero entries occurring below the unit diagonal. We thus see that if L is a lower-triangular matrix with unit diagonal then it is invertible and its inverse L^{-1} is also a lower-triangular matrix with unit diagonal.

Assume U is an upper triangular matrix with nonzero diagonal. That U is invertible can be seen from Gauss-Jordan elimination (again shown in a 4 by 4 example):

\begin{bmatrix} x&x&x&x&\vline&1&0&0&0 \\ 0&x&x&x&\vline&0&1&0&0 \\ 0&0&x&x&\vline&0&0&1&0 \\ 0&0&0&x&\vline&0&0&0&1 \end{bmatrix}

Note that forward elimination is not necessary: There are nonzero entries on the diagonal and zeros below them, so we have pivots in every column; therefore the left-hand matrix U is nonsingular and is guaranteed to have an inverse.

We can find that inverse by doing backward elimination to eliminate the entries above the diagonal in the left-hand matrix, and then dividing by the pivots. Note that since backward elimination starts with all zero entries below the diagonal in the right-hand matrix, it will not produce any nonzero entries below the diagonal in that matrix. Also, the diagonal entries in the right-hand matrix are not affected by backward elimination, for the same reason. After backward elimination completes the diagonal entries in the right-hand matrix will still be ones, and any nonzero entries produced will be above the diagonal. Dividing by the pivots in the left-hand matrix will then produce nonzero entries in the diagonal of the right-hand matrix.

The final right-hand matrix after completion of Gauss-Jordan elimination will therefore be an upper triangular matrix with nonzero diagonal entries. We thus see that if U is an upper-triangular matrix with nonzero diagonal then it is invertible and its inverse U^{-1} is also an upper-triangular matrix with nonzero diagonal.

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