0
$\begingroup$

Question in title. I know that matrix factorizations aren't unique in general, and this is when text books usually mention what types of factorizations exist, like Doolittle's or Crout's .... but are these then unique?

If no, how does one determine all Doolittle factorizations of a given matrix?

$\endgroup$
  • 2
    $\begingroup$ At first I had no clue what Doolittle's factorization is, then I checked and found that it's the LU factorization. In that case, yes, it's unique because L is a lower triangular matrix with $1$ being the element of all diagonal positions. $\endgroup$ – implicati0n Sep 16 '15 at 16:30
  • $\begingroup$ A more general statement is that the LDU decomposition is unique if the $D$ is diagonal and $L$ is lower triangular and $U$ is upper triangular and all diagonal entries of $U$ and $L$ are 1. Then the matrix $D$ can be multiplied with either $L$ or $U$ to give a unique decomposition where either $L$ or $U$ has all 1 on the diagonal. See Wikipedia's page on LU decomposition to see the statement of uniqueness. $\endgroup$ – user2566092 Sep 16 '15 at 16:37
0
$\begingroup$

Yes, the Doolittle factorization $A=LU$ where L is a unit lower triangular matrix is unique for non-singular matrices A.

The proof is given by the algorithm itself, since it is basically the generic algorithm for an LU decomposition but with a fixed initial value $ l_{11} = 1 $. In a LU decomposition that is not a Doolitle, Crout or Cholesky decomposition, the nonzero initial value may be freely chosen.

The algorithm is as follows (using forward propagation):

for $k=1,2,...,n$ do:

$\qquad$ $l_{kk} \leftarrow 1$

$\qquad$ for $j=k,k+1,...,n$ do:

$\qquad \qquad u_{kj} \leftarrow a_{kj} - \sum\limits_{s=1}^{k-1} l_{ks}u_{sj}$

$\qquad$ end

$\qquad$ for $i=k+1, k+2,...,n$ do:

$\qquad \qquad$ $\left. l_{ik} \leftarrow \left( a_{ik} - \sum\limits_{s=1}^{k-1} l_{is}u_{sk}\right) \middle/ u_{kk} \right.$

$\qquad$ end

end

This becomes Crout's decomposition if we use backward propagation instead of forward propagation.

$\endgroup$

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.