2
$\begingroup$

What would be an example of a matrix that would not have a $LDL^T$ decomposition? This is a trivial case but I was thinking of a zero matrix which would result in L being an identity matrix and D would be a zero matrix. When you compute $LDL^T$ it still gives you the original zero matrix so I don't believe this is correct.

What about a singular matrix?

  • 1
    An $\mathbf L\mathbf D\mathbf L^T$ decomposition is not a "block LU decomposition".2010-11-24
  • 3
    In any event, $$\begin{pmatrix}0&1\\1&0\end{pmatrix}$$2010-11-24
  • 0
    Sorry about that I was mixing up my questions.2010-11-24
  • 0
    In general you can get an LU decomposition if you never need to switch rows when row reducing. Switching rows adds a permutation matrix to the decomposition. J.M. has given the simplest counterexample.2010-11-24
  • 0
    So even if you need to use a permutation matrix to find the final result you don't consider that a decomposition of the original matrix?2010-11-24
  • 0
    Look at the algorithm for $\mathbf L\mathbf D\mathbf L^T$ again, and note that you quickly bump into a division by zero.2010-11-24
  • 1
    @Planeman: That matrix has no LU decomposition. You can show this with bare hands: Try writing $\begin{pmatrix}0&1\\1&0\end{pmatrix}=\begin{pmatrix}a&0\\b&c\end{pmatrix}\begin{pmatrix}d&e\\0&f\end{pmatrix}$ and see what happens.2010-11-24
  • 1
    @Planeman, the $\mathbf L\mathbf D\mathbf L^T$ decomposition usually does not involve pivoting of any sort.2010-11-24
  • 0
    @Planeman: (My last comment was addressed to a comment that was edited out.) Regarding your updated comment, whatever you call the decomposition that includes a permutation matrix, it is not an LU decomposition in the usual sense. It is sometimes called an LUP decomposition. See http://en.wikipedia.org/wiki/LU_decomposition2010-11-24
  • 0
    Usually for Gaussian elimination, one does indicate if s/he needs a permutation matrix or not; viz. $\mathbf P\mathbf A=\mathbf L\mathbf U$ versus $\mathbf A=\mathbf L\mathbf U$ .2010-11-24
  • 0
    The proper designation is "LU decomposition with partial pivoting", actually, if you do pivot (and in practice, one often does!)2010-11-24
  • 0
    Thank you both, it makes sense now. I was just not clear before on the use of the permutation matrix.2010-11-24

1 Answers 1

5

So that this does not remain unanswered:

$$\begin{pmatrix}0&1\\1&0\end{pmatrix}$$

is the simplest matrix that does not possess an $\mathbf L\mathbf D\mathbf L^T$ decomposition.

In general, any symmetric matrix whose leading submatrix (the submatrix formed by the first few rows and columns) is singular will not possess such a decomposition.

  • 0
    By extension, Cholesky too will fail if given a matrix with a singular leading submatrix.2010-11-24