# Why does the Cholesky decomposition requires a positive definite matrix?

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.

• 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) – Gottfried Helms Aug 8 '13 at 12:52
• 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. – Fezvez Aug 8 '13 at 13:18

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.

• 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. – Memleak Aug 9 '13 at 6:57
• @lttleO, Is there an optimized function for Cholesky Decomposition of $B = {A}^{T} A$ without having $B$ explicitly but only $A$ (So, we reduce the multiplication overhead)? – Royi Jan 18 at 18:41
• @Royi Hmm, what if we computed a QR factorization of $A$, so $A = QR$ where $Q$ is orthogonal and $R$ is upper triangular. Then $B = R^T Q^T Q R = R^T R$. So we have expressed $B$ as a product of a lower triangular matrix $R^T$ and an upper triangular matrix $R$. Does that work? – littleO Jan 18 at 19:29
• The issue is $A$ isn't guaranteed to be PSD while $B = {A}^{T} A$ is. – Royi Jan 19 at 5:36
• @Royi Is that a problem? $A$ still has a QR factorization, whether or not $A$ is positive semidefinite. – littleO Jan 19 at 6:06

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.

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