Why use symmetry twice?
Gaussian elimination applies to many matrices, but it stores two triangular factors even when the coefficient matrix is symmetric. For a real symmetric positive definite matrix, one triangular factor determines the other. The resulting Cholesky factorization also avoids pivoting in exact arithmetic. This is valuable when a factor is reused for many right-hand sides, but neither positivity nor a successful factorization says that the original system is well conditioned.
Throughout this note is symmetric, , and calculations are exact unless stated otherwise.
Definition 3.2.1
(Positive definite matrix and Cholesky factor)
A real symmetric matrix is positive definite if for every nonzero . A Cholesky factor of is a lower triangular matrix with strictly positive diagonal entries such that .
Constructing the columns
The equation gives a practical order of calculation. Once columns are known, set
The empty sum is zero. The square root is the positive one. The theorem below is what makes these operations legal for positive definite input; simply taking a square root of a computed expression is not a proof that it is positive.
Theorem 3.2.2
(Existence and uniqueness)
A real symmetric matrix is positive definite if and only if there is a lower triangular matrix with strictly positive diagonal satisfying . This is unique, and the column formulas above compute it.
Proof
(Induction through the Schur complement)
For the forward direction, use induction on . The case follows from . For , partition
Here . For any nonzero , put . Then and , so is positive definite. By induction for lower triangular with positive diagonal. Consequently
satisfies . Repeating the same block step gives the stated column formulas and positive radicands. Conversely, if with triangular and positive diagonal, then is invertible and for nonzero .
For uniqueness, equating entries in forces , then the rest of the first column. Assuming earlier columns fixed, the diagonal equation forces the positive and the off-diagonal equations force each . Induction fixes every entry. The positive diagonal is essential for uniqueness: without that convention, column signs can be changed.
The induction hides one non-obvious choice of test vector, and the uniqueness half depends on a sign convention. The dissection below separates them.
Proof X-ray
The Schur complement explains the next pivot
The key move is the test vector . Expanding with cancels the cross term and leaves exactly . This single identity transfers positive definiteness from to the smaller matrix , so the induction can continue. It also explains the column formulas: the radicand at step is the leading entry of the th Schur complement, and a positive definite matrix has positive diagonal entries (), so every square root is of a positive number.
Symmetry is used in the partition itself: the same vector appears below and to the right of , which is why one factor and its transpose suffice. The converse direction uses only that a triangular matrix with positive diagonal is invertible, so for . Uniqueness uses the sign convention at each diagonal equation : without the requirement , each column could be multiplied by .
Solving and reusing the factor
After computing , solve by forward substitution and then by back substitution. Neither inverse need be formed. The dense factorization uses about arithmetic operations under the usual convention counting a multiplication and an addition separately; each pair of triangular solves costs . These are leading dense-operation counts, not guarantees for a sparse implementation: elimination can introduce fill, and ordering affects storage.
Worked example 3.2.3
(Factor once, solve twice)
Take
The first column is . The second diagonal is , and . Finally . Thus
Its positive diagonal and the identity also certify that is positive definite. Forward substitution gives ; back substitution gives . Check directly that . With a second right-hand side , the same may be reused and the solution is . The factorization cost is paid once, although each new solve has its own arithmetic error in a computer.
What can fail?
Counterexample mode
Symmetry and positive diagonal are insufficient
The symmetric matrix has positive diagonal entries but . Its first Cholesky pivot is , while the second radicand is . It is nonsingular, yet has no real factor . Positive diagonal entries alone are not positive definiteness.
The boundary between definite and semidefinite matrices is visible in the formulas.
Worked example 3.2.4
(A semidefinite matrix reaches a zero pivot)
Take . It is symmetric, and , with equality for , so is positive semidefinite but not positive definite. The column formulas give , , and then
The product does equal , but the diagonal is not strictly positive, so this is not a Cholesky factor in the sense of the theorem. In a larger matrix a zero pivot would also make the next column formula divide by zero. The theorem's strict inequality is exactly what excludes this case.
Worked example 3.2.5
(Positive definite but ill conditioned)
Even for positive definite , a small eigenvalue can make the solution sensitive. For with , the factor is , while the two-norm condition number is . If changes to , the solution changes from to : a relative change in the data produces a relative change in the solution. Stable factorization cannot remove the problem's inherent sensitivity.
Common mistake
(Taking a successful factorization as a well-conditioned problem)
A completed Cholesky factorization certifies positive definiteness in exact arithmetic. It says nothing about the size of the condition number, as the diagonal example shows. Overflow, input uncertainty and conditioning require separate attention.
Common mistake
(Diagnosing a computed nonpositive pivot)
In floating-point arithmetic a computed nonpositive pivot may reflect indefiniteness or rounding near singularity; it is not by itself a proof of either cause. Further evidence, such as an explicit vector with , is needed to conclude that is indefinite.
Practice with solutions
Quick check
(Factor and solve .)
Solution · Answer
The first column is and the second diagonal is , so . Forward substitution gives ; back substitution gives . Multiplication confirms the answer.
Quick check
(For , determine exactly when the real positive-diagonal Cholesky factor exists.)
Solution · Answer
The first pivot is and the second radicand is . The factor exists exactly when . At the matrix is singular; for the quadratic form takes a negative value. The theorem gives the same conclusion through positive definiteness.
Quick check
(Does with invertible lower triangular necessarily imply is positive definite if the diagonal signs are unrestricted? Is then unique?)
Solution · Answer
Yes: for , so . Uniqueness fails: for example . Requiring positive diagonal selects one factor.
The proof concerns exact arithmetic and the specified matrix class. It does not by itself establish finite-precision error bounds, conditioning, sparse fill estimates, or applicability to indefinite matrices.