Why Positive Definite Matrices Have Cholesky Factors

The Factorization We Want to Explain

A real symmetric positive definite matrix describes a quadratic form that is strictly positive in every nonzero direction. Such a matrix can also be written as a product \(R^{\top}R\), where \(R\) is upper triangular and has positive diagonal entries. This factorization is useful because it expresses the quadratic form as a sum of squares after a change of variables. The central questions here are why such a factor always exists and why the positivity condition on the diagonal makes it unique.

Throughout, matrices and vectors are real, and vectors are columns. A matrix \(\mathbf{A}\in\mathbb{R}^{n\times n}\) is symmetric if \(\mathbf{A}^{\top}=\mathbf{A}\). It is positive definite if \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}>0\) for every nonzero \(\mathbf{x}\in\mathbb{R}^n\). An upper-triangular matrix has all entries below its main diagonal equal to zero. We seek an upper-triangular \(\mathbf{R}\) for which \(\mathbf{A}=\mathbf{R}^{\top}\mathbf{R}\), with every diagonal entry of \(\mathbf{R}\) strictly positive.

The theorem has two distinct parts. Existence says at least one such factor can be constructed. Uniqueness says that once we require an upper-triangular factor with positive diagonal, no other factor can work. We prove both by induction on the matrix size. The key step is that a certain smaller matrix—the Schur complement of the top-left entry—remains positive definite.

Why the Smaller Matrix Stays Positive Definite

Write a symmetric matrix in block form, separating its first row and column:

Here \(a\) is a real number, \(\mathbf{b}\in\mathbb{R}^{n-1}\) is a column, and \(\mathbf{C}\in\mathbb{R}^{(n-1)\times(n-1)}\) is symmetric. If \(\mathbf{A}\) is positive definite, then \(a>0\): evaluate its quadratic form at the first standard basis vector \(\mathbf{e}_1\) to get \(\mathbf{e}_1^{\top}\mathbf{A}\mathbf{e}_1=a>0\). We can therefore form the matrix

This is the Schur complement of the scalar block \(a\). Its significance is not merely that it is smaller: it is itself symmetric positive definite.

Proof. The matrix \(\mathbf{S}\) is symmetric because \(\mathbf{C}\) and \(\mathbf{b}\mathbf{b}^{\top}\) are symmetric. Let \(\mathbf{y}\in\mathbb{R}^{n-1}\) be nonzero and define \(\mathbf{x}\in\mathbb{R}^{n}\) by \(\mathbf{x}=(-\mathbf{b}^{\top}\mathbf{y}/a,\mathbf{y})^{\top}\), meaning that its first coordinate is \(-\mathbf{b}^{\top}\mathbf{y}/a\) and its remaining coordinates are \(\mathbf{y}\). Since \(\mathbf{y}\ne\mathbf{0}\), we have \(\mathbf{x}\ne\mathbf{0}\). Direct expansion gives

Positive definiteness of \(\mathbf{A}\) gives \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}>0\), so \(\mathbf{y}^{\top}\mathbf{S}\mathbf{y}>0\) for every nonzero \(\mathbf{y}\). This is precisely positive definiteness of \(\mathbf{S}\). \(\square\)

The choice of the first coordinate of \(\mathbf{x}\) cancels the terms involving \(\mathbf{b}\) in the quadratic form. What remains is exactly the quadratic form of \(\mathbf{S}\). This cancellation is what makes induction possible: a positive definite problem of size \(n\) produces a positive definite problem of size \(n-1\).

Proof of Existence and Uniqueness

We now prove the theorem by induction on \(n\). For \(n=1\), a positive definite matrix consists of a single entry \(a>0\). Its factor is the one-entry matrix \([\sqrt{a}]\), where \(\sqrt{a}\) is the positive square root. It is the only positive one-entry factor whose square is \(a\).

Suppose the theorem holds for matrices of size \(n-1\), and let \(\mathbf{A}\) be a real symmetric positive definite matrix of size \(n\). Partition it as above. We have \(a>0\), and the lemma shows that \(\mathbf{S}\) is symmetric positive definite. By the induction hypothesis there is a unique upper-triangular \(\mathbf{Q}\) with positive diagonal such that \(\mathbf{S}=\mathbf{Q}^{\top}\mathbf{Q}\). Define

The matrix \(\mathbf{R}\) is upper triangular, and its diagonal entries are positive because \(\sqrt{a}>0\) and the diagonal entries of \(\mathbf{Q}\) are positive. Multiplying the blocks gives

This proves existence. For uniqueness, suppose \(\mathbf{U}\) is another upper-triangular factor with positive diagonal and \(\mathbf{U}^{\top}\mathbf{U}=\mathbf{A}\). Partition it as \(\mathbf{U}=\begin{bmatrix}u&\mathbf{w}^{\top}\\\mathbf{0}&\mathbf{V}\end{bmatrix}\), where \(u>0\), \(\mathbf{V}\) is upper triangular with positive diagonal, and \(\mathbf{w}\in\mathbb{R}^{n-1}\). Comparing the top-left entries of \(\mathbf{U}^{\top}\mathbf{U}=\mathbf{A}\) gives \(u^2=a\), and positivity forces \(u=\sqrt{a}\). Comparing the top-right blocks gives \(u\mathbf{w}^{\top}=\mathbf{b}^{\top}\), so \(\mathbf{w}=\mathbf{b}/\sqrt{a}\). Finally, comparing the bottom-right blocks gives

By the uniqueness part of the induction hypothesis, \(\mathbf{V}=\mathbf{Q}\). Thus every block of \(\mathbf{U}\) equals the corresponding block of \(\mathbf{R}\), so \(\mathbf{U}=\mathbf{R}\). This proves uniqueness at size \(n\). The base case and induction step establish both existence and uniqueness for every positive integer \(n\). \(\square\)

What the Factor Says About the Quadratic Form

The factorization also explains the connection between a matrix and its quadratic form. For every \(\mathbf{x}\in\mathbb{R}^n\), associativity of matrix multiplication gives

Here \(\|\mathbf{z}\|^2=\mathbf{z}^{\top}\mathbf{z}\) is the squared Euclidean norm. If \(\mathbf{x}\ne\mathbf{0}\), then \(\mathbf{R}\mathbf{x}\ne\mathbf{0}\): starting with the last row of \(\mathbf{R}\mathbf{x}=\mathbf{0}\), its positive diagonal entry forces \(x_n=0\); the preceding row then forces \(x_{n-1}=0\), and continuing upward forces every coordinate to be zero. Therefore \(\|\mathbf{R}\mathbf{x}\|^2>0\) whenever \(\mathbf{x}\ne\mathbf{0}\).

Proof. The matrix \(\mathbf{R}^{\top}\mathbf{R}\) is symmetric since \((\mathbf{R}^{\top}\mathbf{R})^{\top}=\mathbf{R}^{\top}\mathbf{R}\). For nonzero \(\mathbf{x}\), the row-by-row argument above shows \(\mathbf{R}\mathbf{x}\ne\mathbf{0}\). Hence \(\mathbf{x}^{\top}\mathbf{R}^{\top}\mathbf{R}\mathbf{x}=(\mathbf{R}\mathbf{x})^{\top}(\mathbf{R}\mathbf{x})>0\). This is the definition of positive definiteness. \(\square\)

Together, the theorem and its converse give an exact characterization: a real symmetric matrix is positive definite if and only if it can be written as \(\mathbf{R}^{\top}\mathbf{R}\) with \(\mathbf{R}\) upper triangular and positive on the diagonal. The uniqueness assertion applies to this specified form and diagonal condition; without those conditions, other matrix factorizations need not be unique.

Worked Factors and Checks

Why the Hypotheses and the Factor Order Matter

Positive definiteness is essential, not a technical detail. For example, let \(\mathbf{B}=\begin{bmatrix}1&2\\2&1\end{bmatrix}\). It is symmetric, but for \(\mathbf{x}=\begin{bmatrix}1\\-1\end{bmatrix}\),

So \(\mathbf{B}\) is not positive definite and cannot equal \(\mathbf{R}^{\top}\mathbf{R}\) for an upper-triangular \(\mathbf{R}\) with positive diagonal: the converse would make it positive definite.

A related common mistake is to reverse the factor order and assume that \(\mathbf{R}\mathbf{R}^{\top}\) is the target matrix. For the factor in the three-dimensional example, the wrong multiplication gives

which is not \(\mathbf{A}\). The factorization proved here is specifically \(\mathbf{A}=\mathbf{R}^{\top}\mathbf{R}\) with \(\mathbf{R}\) upper triangular. Writing the order correctly matters because matrix multiplication is not generally commutative: reversing the factors changes the product.