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.