Is the $L$ in $LU$ factorization unique?

Question

I was doing an $LU$ factorization problem \begin{bmatrix} 2 & 3 & 2 \\ 4 & 13 & 9 \\ -6 & 5 &4 \end{bmatrix} and I was going to multiply the second row by .$5$ and subtract the result from row $1$, then do something similar to row reduce row $3$. My book tells me that you first row-reduce to get $U$, then you extract certain columns from various steps in the reduction process to get $L$. That's when I realized that if I instead multiplied row $1$ by $2$ subtracted from one times row $2$, this would be equivalent to getting $U$, but it would change the resultant $L$ matrix! What is wrong with this approach?

Answer 1

The usual theorem is the following :

Let $A \in \mathbb{C}_n^n $ be a square matrix such that its principal minors are not equal to $0$. Then there is a unique couple $(L,U)$ such that $L$ is lower triangular and $diag(L) = (1,\cdots,1)$, $U$ is upper triangular and $A = LU.$

The uniqueness is obtained thanks to the condition $$diag(L) = (1,\cdots,1).$$

Answer 2

There is nothing wrong with your reasoning: you will still get an LU factorization, just a different one as compared to otherwise. LU factorizations are, as you have just discovered, not unique. Uniqueness would need some extra constraints on the form of L and U.

Wikipedia states that one such condition is to force the diagonal entries of one of the matrices to all be one (so if L has a diagonal of ones, or U has, then uniqueness holds). See the link for further information: https://en.wikipedia.org/wiki/LU_decomposition#Existence_and_uniqueness

Answer 3

There are 3 actions which does not change the rank of a matrix: (I) Multiple one row (column) with a nonzero scalar. (II) Exchange two rows (columns). (III) Multiple one row (column) and add to another row (column). You can use LU factorization only if you only use type (III) to reduce a matrix to the U. If rows exchange is necessary, there is an upgrade for LU.

Answer 4

Just to add one observation to the other (good) responses. The reason why there is no unique pair of lower/upper triangular matrices L and U such that A=LU, is simply because the problem is underdetermined. If you count the number entries to determine in L and U you obtain $n^2+n$, while the equality A=LU only gives you $n^2$ equations that the coefficients of L and U must fulfill.

Therefore, in order to hope for uniqueness, you must add some constraints. Typically, we require the diagonal entries of L to be 1's (notice that this is completely arbitrary, we may as well require the diagonal entries of U to be $1,2,3,\ldots,n$ for what it matters). As others pointed out, this constraint is not in general sufficient to even be sure that a factorization exists. However, under certain conditions (such as those in the theorem pointed out by Dubussy), such a factorization exists and is unique.

Answer 5

For a singular matrix, the LU decomposition may not be unique; for example, $$\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}=\begin{bmatrix}1&0&0\\1&1&0\\1&x&1\end{bmatrix}\begin{bmatrix}1&1&1\\0&0&0\\0&0&0\end{bmatrix}$$ for any $x$. It is interesting to note that for a $2\times 2$ matrix, the LU decomposition is unique, even if the matrix is singular. (One can show this by direct calculation.)