From a Positive Definite Matrix to Its Factor
Cholesky factorization replaces a symmetric positive definite matrix with a product of a lower triangular matrix and its transpose. The triangular shape makes the factor relatively quick to compute, and it turns a quadratic form into a sum of squares. It also gives a way to solve a linear system using two triangular systems rather than treating the original matrix all at once.
Throughout, matrices and vectors are real. A matrix \(\mathbf{A}\in\mathbb{R}^{n\times n}\) is symmetric positive definite if \(\mathbf{A}^{\top}=\mathbf{A}\) and \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}>0\) for every nonzero \(\mathbf{x}\in\mathbb{R}^n\). A lower triangular matrix has zero entries above its main diagonal. The standard Cholesky factorization of \(\mathbf{A}\) is a factorization \(\mathbf{A}=\mathbf{L}\mathbf{L}^{\top}\), where \(\mathbf{L}\) is lower triangular and each diagonal entry of \(\mathbf{L}\) is positive. The positive diagonal convention is part of the definition; it makes the factor unique.
The existence of such a factor for every real symmetric positive definite matrix is the Cholesky existence result established earlier in the material on positive definiteness. Here the task is to compute the entries. Write \(l_{ij}\) for the entry of \(\mathbf{L}\) in row \(i\), column \(j\). Because \(\mathbf{L}\) is lower triangular, \(l_{ij}=0\) when \(j>i\). The \((i,j)\) entry of \(\mathbf{L}\mathbf{L}^{\top}\) is therefore a sum of products from the first \(\min(i,j)\) columns:
For \(i\geq j\), this equation gives the entries of column \(j\) in a useful order: first the diagonal entry \(l_{jj}\), then the entries below it. The diagonal equation is \(a_{jj}=\sum_{k=1}^{j}l_{jk}^{2}\). The off-diagonal equation for row \(i>j\) includes \(l_{ij}\) in its last term. Solving each equation gives the algorithm.
At the moment a column is computed, the entries in its sums are already known: they belong to earlier columns. In the off-diagonal formula, division by \(l_{jj}\) is valid because the algorithm chooses the positive square root for the diagonal. These equations are not formulas to apply to an arbitrary matrix without checking the hypotheses. The standard result used here is that positive definiteness guarantees a factor with positive diagonal; the equations show how to determine that factor.
Why the Entry Equations Give the Factor
Proof. We first justify that the formulas determine the entries of any Cholesky factor. Suppose \(\mathbf{A}=\mathbf{L}\mathbf{L}^{\top}\) for a lower triangular \(\mathbf{L}\) with positive diagonal. For each \(j\), the diagonal entry equation is \(a_{jj}=\sum_{k=1}^{j}l_{jk}^{2}\). Once the entries \(l_{j1},\dots,l_{j,j-1}\) are known, this forces \(l_{jj}^{2}=a_{jj}-\sum_{k=1}^{j-1}l_{jk}^{2}\). Since \(l_{jj}>0\), it forces exactly the positive square root in the formula. For \(i>j\), the \((i,j)\) equation is \(a_{ij}=\sum_{k=1}^{j-1}l_{ik}l_{jk}+l_{ij}l_{jj}\). Since \(l_{jj}>0\), solving for \(l_{ij}\) gives the stated off-diagonal formula. Thus every entry is forced in column order, so there is at most one such factor. The earlier Cholesky existence result supplies a factor for this positive definite \(\mathbf{A}\); applying the forced equations to it shows that the formulas compute that factor. \(\square\)
This argument also explains the order of computation. It does not guess entries independently: each new diagonal entry is fixed by a diagonal equation, and each entry below it is then fixed by an off-diagonal equation. To check arithmetic or catch a transcription error, multiply the resulting \(\mathbf{L}\mathbf{L}^{\top}\) and compare every entry with \(\mathbf{A}\).
A Three-by-Three Factorization
Worked Example: Compute and Verify a Cholesky Factor
Find the Cholesky factor of \(\mathbf{A}=\begin{bmatrix}4&2&2\\2&5&1\\2&1&6\end{bmatrix}\).
Start with column 1. The first diagonal entry is \(l_{11}=\sqrt{4}=2\). The entries below it follow from the \((2,1)\) and \((3,1)\) equations: \(l_{21}=2/2=1\) and \(l_{31}=2/2=1\).
For column 2, the diagonal equation gives \(l_{22}=\sqrt{5-l_{21}^{2}}=\sqrt{5-1}=2\). The remaining entry in that column is \(l_{32}=(a_{32}-l_{31}l_{21})/l_{22}=(1-1\cdot1)/2=0\).
For the last diagonal entry, \(l_{33}=\sqrt{6-l_{31}^{2}-l_{32}^{2}}=\sqrt{6-1-0}=\sqrt{5}\). Thus
Verify by multiplication:
For example, the \((3,2)\) entry is \(1\cdot1+0\cdot2+\sqrt{5}\cdot0=1\), and the \((3,3)\) entry is \(1^{2}+0^{2}+(\sqrt{5})^{2}=6\). The other entries follow from the displayed product. This multiplication checks the factorization itself, not just that the entries satisfy some of the triangular equations.
Using the Factor to Evaluate a Quadratic Form
If \(\mathbf{A}=\mathbf{L}\mathbf{L}^{\top}\), then for any \(\mathbf{x}\in\mathbb{R}^n\), associativity of matrix multiplication gives \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}=(\mathbf{L}^{\top}\mathbf{x})^{\top}(\mathbf{L}^{\top}\mathbf{x})\). For a real vector \(\mathbf{y}\), \(\mathbf{y}^{\top}\mathbf{y}\) is the sum of the squares of its entries. So the factor lets us compute the quadratic form by first finding \(\mathbf{L}^{\top}\mathbf{x}\), then summing its squared entries.
Proof. By the definition of the Euclidean norm, \(\|\mathbf{y}\|^{2}=\mathbf{y}^{\top}\mathbf{y}\). Substituting \(\mathbf{y}=\mathbf{L}^{\top}\mathbf{x}\) and using \(\mathbf{A}=\mathbf{L}\mathbf{L}^{\top}\) gives \(\|\mathbf{L}^{\top}\mathbf{x}\|^{2}=\mathbf{x}^{\top}\mathbf{L}\mathbf{L}^{\top}\mathbf{x}=\mathbf{x}^{\top}\mathbf{A}\mathbf{x}\). It remains to check strict positivity for nonzero \(\mathbf{x}\). If \(\mathbf{L}^{\top}\mathbf{x}=\mathbf{0}\), its last equation forces \(x_n=0\), because the last diagonal entry of \(\mathbf{L}^{\top}\) is nonzero. The preceding equation then forces \(x_{n-1}=0\). Continuing upward forces every entry of \(\mathbf{x}\) to be zero. Thus, when \(\mathbf{x}\ne\mathbf{0}\), \(\mathbf{L}^{\top}\mathbf{x}\ne\mathbf{0}\), and its squared norm is positive. Hence \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}>0\). \(\square\)
Worked Example: Evaluate a Quadratic Form by a Factor
Let \(\mathbf{L}=\begin{bmatrix}1&0&0\\2&1&0\\-1&3&2\end{bmatrix}\) and \(\mathbf{x}=\begin{bmatrix}1\\-1\\2\end{bmatrix}\). First compute \(\mathbf{A}=\mathbf{L}\mathbf{L}^{\top}\):
Instead of multiplying \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}\) directly, compute \(\mathbf{L}^{\top}\mathbf{x}=\begin{bmatrix}1&2&-1\\0&1&3\\0&0&2\end{bmatrix}\begin{bmatrix}1\\-1\\2\end{bmatrix}=\begin{bmatrix}-3\\5\\4\end{bmatrix}\). Therefore \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}=(-3)^2+5^2+4^2=9+25+16=50\).
Check by direct multiplication: \(\mathbf{A}\mathbf{x}=\begin{bmatrix}-3\\-1\\26\end{bmatrix}\), so \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}=1(-3)+(-1)(-1)+2(26)=-3+1+52=50\). The two computations agree.
Solving a System with Two Triangular Solves
When \(\mathbf{A}=\mathbf{L}\mathbf{L}^{\top}\), solving \(\mathbf{A}\mathbf{x}=\mathbf{b}\) can be done in two stages. First solve \(\mathbf{L}\mathbf{y}=\mathbf{b}\) for \(\mathbf{y}\) by forward substitution, moving from the top row downward. Then solve \(\mathbf{L}^{\top}\mathbf{x}=\mathbf{y}\) by back substitution, moving from the bottom row upward. The reason this works is that \(\mathbf{A}\mathbf{x}=\mathbf{L}\mathbf{L}^{\top}\mathbf{x}=\mathbf{b}\); taking \(\mathbf{y}=\mathbf{L}^{\top}\mathbf{x}\) gives precisely the two equations in sequence. Positive diagonal entries ensure the divisions in both solves are valid.
Worked Example: Solve a System Using Cholesky
Use Cholesky factorization to solve \(\begin{bmatrix}4&2&2\\2&5&-1\\2&-1&6\end{bmatrix}\mathbf{x}=\begin{bmatrix}8\\3\\7\end{bmatrix}\). The factor is \(\mathbf{L}=\begin{bmatrix}2&0&0\\1&2&0\\1&-1&2\end{bmatrix}\), as direct multiplication gives \(\mathbf{L}\mathbf{L}^{\top}=\begin{bmatrix}4&2&2\\2&5&-1\\2&-1&6\end{bmatrix}\).
First solve \(\mathbf{L}\mathbf{y}=\mathbf{b}\). The first row gives \(2y_1=8\), so \(y_1=4\). The second gives \(y_1+2y_2=3\), hence \(4+2y_2=3\) and \(y_2=-\tfrac12\). The third gives \(y_1-y_2+2y_3=7\), hence \(4+\tfrac12+2y_3=7\) and \(y_3=\tfrac54\).
Now solve \(\mathbf{L}^{\top}\mathbf{x}=\mathbf{y}\), where \(\mathbf{L}^{\top}=\begin{bmatrix}2&1&1\\0&2&-1\\0&0&2\end{bmatrix}\). The last row gives \(2x_3=\tfrac54\), so \(x_3=\tfrac58\). The second row gives \(2x_2-x_3=-\tfrac12\), so \(2x_2=-\tfrac12+\tfrac58=\tfrac18\) and \(x_2=\tfrac1{16}\). The first row gives \(2x_1+x_2+x_3=4\), so \(2x_1=4-\tfrac1{16}-\tfrac58=\tfrac{53}{16}\) and \(x_1=\tfrac{53}{32}\).
Thus \(\mathbf{x}=\begin{bmatrix}\tfrac{53}{32}\\\tfrac1{16}\\\tfrac58\end{bmatrix}\). Check by multiplying by the original matrix: the three entries of \(\mathbf{A}\mathbf{x}\) are \(\tfrac{53}{8}+\tfrac18+\tfrac{10}{8}=8\), \(\tfrac{53}{16}+\tfrac5{16}-\tfrac{10}{16}=3\), and \(\tfrac{53}{16}-\tfrac1{16}+\tfrac{60}{16}=7\). Therefore \(\mathbf{A}\mathbf{x}=\mathbf{b}\), as required.
Common Mistake: Omitting Earlier Products
In an off-diagonal equation, the numerator is not generally just \(a_{ij}\). It must subtract the products contributed by the columns already computed. In the first worked example, a tempting but incorrect calculation is \(l_{32}=a_{32}/l_{22}=1/2\). It ignores \(l_{31}l_{21}=1\). The correct calculation is \(l_{32}=(1-1\cdot1)/2=0\). With the incorrect value, the \((3,2)\) entry of the proposed product would be \(l_{31}l_{21}+l_{32}l_{22}=1+\tfrac12\cdot2=2\), not the required entry \(1\). Multiplying the proposed factors back exposes the error.
A second check is structural: \(\mathbf{L}\) must be lower triangular and the product must be \(\mathbf{L}\mathbf{L}^{\top}\), not \(\mathbf{L}^{\top}\mathbf{L}\). These products need not be equal. Before using a computed factor, check its triangular shape, its positive diagonal, and the full product \(\mathbf{L}\mathbf{L}^{\top}=\mathbf{A}\).
Check Your Understanding
Use the entry equations carefully, and verify computed factors or solutions by substitution.
- For \(\mathbf{A}=\begin{bmatrix}9&3\\3&5\end{bmatrix}\), compute the Cholesky factor and multiply it by its transpose to check your answer.
- Write the entry equation that determines \(l_{31}\) when computing a three-by-three Cholesky factor. What earlier entries does it use?
- If \(\mathbf{A}=\mathbf{L}\mathbf{L}^{\top}\), explain why \(\mathbf{x}^{\top}\mathbf{A}\mathbf{x}\) is a sum of squares.
- For the factor \(\mathbf{L}=\begin{bmatrix}2&0\\1&3\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}4\\7\end{bmatrix}\), solve \(\mathbf{L}\mathbf{y}=\mathbf{b}\), then solve \(\mathbf{L}^{\top}\mathbf{x}=\mathbf{y}\).
- In the formula for \(l_{ij}\), identify the omitted contribution in the incorrect expression \(l_{ij}=a_{ij}/l_{jj}\).
