9
$\begingroup$

Why does the Cholesky factorization requires the matrix A to be positive definite? What happens when we factorize non-positive definite matrix?

Let's assume that we have a matrix A' that is not positive definite (so at least one leading principal minor is negative). Can one prove that there is no L such as A' = LL*? If not, wouldn't the positive definite criteria remove some of the matrices that could be potentially decomposed?

We could also put this question in the form of a demonstration for the next statement: For any square matrix L, the product LL* is a positive definite matrix.

$\endgroup$
  • 1
    $\begingroup$ If you allow matrices over the field of complex numbers, you can have the cholesky-decomposition with negative definite matrices. The given answers so far ("doesn't exist", et. al.) should be extended by the restriction "over the reals" (which was not given by the question, btw) $\endgroup$ – Gottfried Helms Aug 8 '13 at 12:52
  • 1
    $\begingroup$ As for What happens when we factorize non-positive definite matrix?, the algorithm requires you to compute the square root of some numbers (located on the diagonal of a temporary matrix you work on). If the matrix is not positive definite, you can prove that one of these numbers will be negative, and thus, your algorithm will fail. $\endgroup$ – Fezvez Aug 8 '13 at 13:18
16
$\begingroup$

Suppose a matrix $A$ factors as $A = L^* L$. Then \begin{align} x^* Ax &= x^* L^* L x \\ &= (Lx)^* (Lx) \\ &= \| Lx \|^2 \\ &\geq 0. \end{align} This shows that $A$ is positive semidefinite.

If we further assume that $L$ is square and triangular with positive real diagonal entries, then $L$ is invertible, so $Lx = 0 \iff x = 0$. In this case, we see that $A$ is positive definite.

$\endgroup$
  • $\begingroup$ Thanks! I would accept all answers as they are all useful to me but unfortunately I can do it only for one! The explanations you provided helped me to understand a bit more correctly the Cholesky factorization. $\endgroup$ – Memleak Aug 9 '13 at 6:57
5
$\begingroup$

We could also put this question in the form of a demonstration for the next statement: For any square matrix L, the product LL* is a positive definite matrix.

Semidefinite.

Let's go with the definition:

$$x^* L L^* x = (L^*x)^* (L^*x) = y^* y, \quad y := L^*x.$$

By the definition of the Euclidean scalar product, $y^* y = \langle y, y \rangle \ge 0$, with the equality if and only if $0 = y = L^* x$.

So, $x^* L L^* x \ge 0$ for all $x$, hence $L L^*$ is positive semidefinite. Furthermore, it is positive definite if

$$L^*x = 0 \quad \Leftrightarrow \quad x = 0,$$

i.e., if $L$ is of a full row rank.

$\endgroup$
4
$\begingroup$

Just consider the case of numbers $\Bbb M_1(\Bbb R)$. If we have a negative number $a<0$, then its Cholesky decomposition doesn't exist:

$$ll^\ast = |l|^2 = a<0.$$

$\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.