5

Let $L$ be a lower triangular matrix, $D$ diagonal, and $U$ upper triangular.
If $A = LDU$ and also $A = L_1D_1U_1$ with all factors invertible, then $L = L_1$ and $D = D_1$ and $U = U_1$. 'The three factors are unique!'

Hint: Derive the equation $L_1^{-1}LD = D_1 U_1 U^{-l}.$ Are the two sides triangular or diagonal? Deduce $L = L^{-1}$ and $U = U^{-1}$ (they all have diagonal $1$'s). Then $D = D_1$.

Lemma: The inverse of a (lower/upper) triangular matrix is a (lower/upper) triangular matrix.

Uniqueness Proof: Assume $LDU = L_1D_1U_1$. Objective: Prove $X = X_1$ for each $X = L, D, U$.

In keeping with the hint, $\color{green}{L_1^{-1}}LDU\color{#D555D1}{U^{-1}} = \color{green}{L_1^{-1}}L_1D_1U_1\color{#D555D1}{U^{-1}} \iff \color{green}{L_1^{-1}}LD = D_1U_1\color{#D555D1}{U^{-1}}$ $\Longrightarrow (\text{Lower triangular})D = D_1(\text{Upper triangular}).$

$\color{red}{\bigstar} $ So both sides are diagonal. $ \; L,U,L_1,U_1$ have diagonal $1$’s so $D = D_1$. Then $\color{green}{L_1^{-1}}L = I$ and $U_1\color{#D555D1}{U^{-1}} = I. \qquad \blacksquare$

$\Large{1.}$ I don't apprehend the (gruff) sentences after $\color{red}{\bigstar}$. Would someone please enlarge upon them?

$\Large{2.}$ Without the hint, how would one divine/previse to work with $L_1^{-1}LD = D_1 U_1 U^{-l}$?
This equation looks like the critical one in this proof.

2 Answers2

5

Google this problem and found this page :( but finally I worked out this problem somehow. So I will try to answer this question.

First notice that $L_1^{-1}L$ is a lower triangular matrix and has diagonal 1's, since both $L_1^{-1}$ and $L$ are lower triangular and have diagonal 1's.

Nonzero entries below the diagonal of $L_1^{-1}L$ will cause nonzero entries below the diagonal of $L_1^{-1}LD$ (since $D$ is also diagonal). And if that happens, $L_1^{-1}LD$ cannot equal to $D_1U_1U^{-1}$, thus entries below the diagonal of $L_1^{-1}L$ are all 0's.

Now we can conclude $L_1^{-1}L=I$. Similarly, $U_1U^{-1}=I$.

As for the second question, I can not help.

xdot
  • 51
  • 2
0

I wanted to add that the non-singularity of $A$ is crucial. E.g:

$\pmatrix{1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 0 & 1 }$ $\pmatrix{0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 }$ $\pmatrix{1 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 } = $ $\pmatrix{0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 } = $ $\pmatrix{1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 }$ $\pmatrix{0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 }$ $\pmatrix{1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 }$

The zeros on the diagonal allow for "junk" to appear in the non-selected rows or columns. In this example, the zero in $D_{1,1}$ annihilates the first column from $L$, and the first row from $R$. In fact, we have

$\pmatrix{* & 0 & 0 \\ * & 1 & 0 \\ * & 0 & 1 }$ $\pmatrix{0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 }$ $\pmatrix{* & * & * \\ 0 & 1 & 0 \\ 0 & 0 & 1 } = $ $\pmatrix{0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 }$

Where $*$ ranges over $\mathbb{R}$ (or anything that annihilates with 0).

As for question 2, the question is "how do I derive the hint from the problem?" Here's a rough train of thought...

  1. Because $L$ and $R$ are invertible (being composed of row/ column operations), you can move them around and see what happens.
  2. Since the inverse of row (column) operations is more row (column) operations, and composing lower (upper) triangular matrices maintains the lower (upper) triangular structure, consolidating them seems natural.
  3. If a lower and upper triangular matrix are equal, then they are both diagonal.
  4. You probably had to be a little clever to get to this point, but noticing that the ones are on the diagonals of $L_1^{-1}L$ and $U_1U^{-1}$ is probably something hard to find. Maybe you realize it will be hard to prove anything about the other matrices, so you start trying to prove $D = D_1$, and hopefully you'll see this can happen if the diagonals are all 1's, at which point you may have to do some calculations to verify.
  5. Since $D$ and $D_1$ are non-singular, you have that there can be no 0s on the diagonals, so any garbage below or above the diagonals in $L_1^{-1}L$ and $U_1U^{-1}$ will get captured by $D$ and $D_1$, but this can't happen because we made sure our left and right hand sides were both diagonal.
  6. Finally, it takes a second to realize that a lower (upper) triangular matrix with ones on the diagonal and nothing below (above) the diagonal is the identity, so you finally get $L_1^{-1}L = I$ ($U_1U^{-1} = I$)
Nathan Chappell
  • 258