Positive definiteness gives a safe algebraic pivot
Definition 2.4.1
(Positive definite matrix)
A real symmetric matrix is positive definite if for every nonzero vector .
Such a matrix has more structure than an arbitrary invertible matrix. Its Cholesky factorization writes
where is lower triangular with strictly positive diagonal. This lets us solve by two triangular solves, and . It does not require forming .
Definition 2.4.2
(Schur complement)
Let
be a symmetric block matrix whose upper-left block is a scalar . The Schur complement of in is the matrix .
Concept lensAnalytic
Schur complement as a minimum over one variable
For a fixed vector , the function is a quadratic in one variable with positive leading coefficient. Its minimum is attained at , and its value is . So is the quadratic form that remains after the first variable has been eliminated by minimization. This second description explains why inherits positive definiteness from , and it identifies the test vector used in the proof below.
Theorem 2.4.3
(Cholesky factorization)
Every real symmetric positive definite matrix has a unique factorization with lower triangular and positive diagonal. Conversely, any such product is symmetric positive definite.
Proof
(Induction on the Schur complement)
Use induction on the dimension. For the first pivot, because . Write
Multiplying shows that exactly when
The matrix is the Schur complement of ; it is symmetric because and are symmetric. For any nonzero , choose . Then and
Thus is positive definite and the induction hypothesis supplies . The case is .
For uniqueness, the first diagonal entry must be , and the remaining entries in the first column are forced by . The Schur complement is then fixed, and induction fixes the remaining block. Conversely, if has positive diagonal it is invertible, and for , .
Proof X-ray
Why positivity survives every elimination step
Positive definiteness must survive each elimination step; that is the whole induction. The first pivot is available only because is positive definite, and it is needed to divide by . The nonobvious move is the test vector : it picks the first coordinate that minimizes for the given , so is the minimum of the form over that coordinate. Since whenever , positivity of transfers to , and the same argument applies to the smaller matrix. A positive first pivot alone says nothing about , as the counterexample below shows. Uniqueness is a separate matter: every entry is forced because each step offers only one positive square root.
The entry recurrence
Equating entries of gives, for ,
The theorem proves that the exact radicand is positive at every step. It does not say that an arbitrary symmetric matrix has positive radicands, nor that finite-precision arithmetic cannot disturb a very small one.
Worked example 2.4.4
(A two-by-two system)
For
we have . To solve , forward substitution gives and ; back substitution gives , . Checking verifies this particular calculation.
Worked example 2.4.5
(A three-by-three factorization by the recurrence)
Let . The recurrence gives , , ; then , ; finally . So , and multiplying out returns . For , forward substitution gives and back substitution gives , , . Check: .
Worked example 2.4.6
(A radicand that reaches zero)
Let . The recurrence gives , and . The matrix does satisfy , but its diagonal is not positive and is singular. Indeed is only semidefinite: vanishes at . The two triangular solves are then impossible, and in a larger matrix the next column would divide by .
Counterexample mode
Symmetry and a positive first pivot do not imply positive definiteness
The symmetric matrix is invertible but not positive definite. It cannot equal for a real , since for every . A positive first pivot alone does not make the Schur complement positive: here it equals .
Common mistake
(Positive diagonal entries are not enough)
For a symmetric matrix, positive diagonal entries are only necessary, since . The matrix has diagonal , yet gives . Its Schur complement after the first pivot is , so the recurrence would take the square root of a negative number.
A matrix that is positive semidefinite may have a singular factorization with zero diagonal entries, but the recurrence above can divide by zero; the positive-definite theorem does not cover that case. In finite precision, Cholesky is commonly used for well-scaled positive-definite systems, but a complete rounding-error or conditioning analysis requires additional assumptions. A successful factorization does not by itself guarantee a small relative error in when is ill-conditioned.
Practice and solutions
Quick check
(Find the Cholesky factor of .)
Take square roots of the pivots.
Solution · Answer
.
Quick check
(Is positive definite? Explain without computing its eigenvalues.)
Try a vector with entries of opposite sign.
Solution · Answer
No: for , .
Quick check
(Why are both triangular systems uniquely solvable when has positive diagonal?)
What is the determinant of a triangular matrix?
Solution · Answer
A triangular matrix with nonzero diagonal is invertible; forward and backward substitution determine the entries successively.
Quick check
(If with invertible, why can have only the zero solution?)
Compute .
Solution · Answer
gives , hence .