Why does the Cholesky decomposition requires a positive definite matrix?

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.