6
$\begingroup$

The first question: what is the proof that LU factorization of matrix is unique? Or am I mistaken?

The second question is, how can theentries of L below the main diagonal be obtained from the matrix $A$ and $A_1$ that results from the row echelon reduction to $U$? ($A=LU$)

$\endgroup$
1
  • 4
    $\begingroup$ Note that an $LU$ decomposition does not always exist: for instance among permutation matrices, only the identity matrices have an $LU$ decomposition. If an $LU$ decomposition exists it can be made unique by requiring diagonal entries $1$ for (say) $L$; however if a permutation matrix is thrown into the mix, (e.g. $LUP$) then uniqueness is no longer possible. The general notion is Bruhat decomposition, which at the element level is not unique. $\endgroup$ Aug 21 '12 at 12:34
3
$\begingroup$

The factorisation is not unique. There are $n^2+n$ coefficients to estimate and only $n^2$ "equations". As such, that is why there are the two "common" methods, Doolittle and Crout see wiki page. For each of these two approaches, you can show that the resulting linear system has a unique solution.

$\endgroup$
2
  • 2
    $\begingroup$ It seems you're assuming a certain dimension? In any event: one often uses the degrees of freedom available to impose constraints on either the upper or lower triangular factor, e.g. having one of them be unit triangular... $\endgroup$ Aug 21 '12 at 10:31
  • $\begingroup$ Edited! For some reason I had $3\times3$ matrices in my brain... $\endgroup$
    – Daryl
    Aug 21 '12 at 12:13
3
$\begingroup$

It is unique if you require $diag(L) = (1, \dots 1)$.

Because, assume that the LU-decomposition is not unique. Any other LU-decomp would be of the form: $$A=LU=LI_nU=LDD^{-1}U=(LD)(D^{-1}U)$$ with $D\in\mathbb{R}^{n\times n}$, $D\neq I_n$. For this $(LD)(D^{-1}U)$ to be a LU-decomposition, we need $LD$ lower triangular, $(D^{-1}U)$ upper triangular. In order for $LD$ to stay a lower triangular matrix, $D$ needs to be lower triangular. But $D$ lower triangular $\Rightarrow D^{-1}$ lower triangular matrix $\Rightarrow$ $(D^{-1}U)$ not upper triangular.

Therefore, $D$ can only be a diagonal matrix. Now, because $D\neq I_n \Rightarrow \exists d_{ii} \neq 1$ but in that case $$ (LD)_{ii} = \sum_{j=1} L_{ij}D_{ij} = L_{ii}D_{ii} + \sum_{j=1, j=i} L_{ij}*0 = 1\times D_{ii} +0 \neq 1$$

Resulting in $diag(LD) \neq (1, \dots 1)$ which is a contradiction. So such a $D$ does not exist, meaning the decomposition is unique.

$\endgroup$
3
  • 1
    $\begingroup$ Why "Any other LU-decomp would be of the form..."? What if we have $A = LU$ and $A = MV$ with $M \neq L$ and $V \neq U$? Why we should be able to obtain $M$ from $L$? $\endgroup$
    – Figurinha
    Sep 9 '20 at 14:53
  • $\begingroup$ First, It's essential that $M$ is lower unit triangular matrix. This is reasonable since always $L$ is of that type in the $LU$ decomposition. Not allowing $M$ this way would mean, for example, that $M$ does not come from a Gaussian elimination algorithm from which the $LU$ derives from. After that, if we have $A=LU=MV$, we would get $M^{-1} L=VU^{-1}$. This means that $M^{−1}L$ is a upper triangular matrix and a lower triangular matrix, since is a product of two lower triangulars matrices and two upper triangular matrices. Hence, $M^{−1} L=VU^{−1}=D$ is a diagonal matrix. $\endgroup$ Jul 15 '21 at 18:23
  • $\begingroup$ $U$ is invertible, since $\text{rk}(A)\leq \text{min}\{ \text{rk}(L), \text{rk}(U) \}$, whenever $A=LU,$ which would mean that $A$ would not be invertible, and this is not compatible with the LU decomposition assumptions. $\endgroup$ Jul 15 '21 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.