How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The real Cholesky recurrence computes the positive-diagonal factor
Statement
Let and let be symmetric positive definite, meaning for every nonzero . Initialize as the zero matrix. For in order, set and then, for in order, set Every pivot is positive, so the recurrence is well-defined and returns a lower-triangular matrix with positive diagonal satisfying .
Statement references
Hermitian positive-definite matrices and Cholesky factorisation A = LL* with positive diagonal: over the real numbers, positive definiteness means for every nonzero vector, and the Cholesky factor has the form with lower triangular and positive diagonal.
Rank-nullity: : a linear map with finite-dimensional domain satisfies dimension equals nullity plus rank; in particular, a square map with zero kernel is invertible.
David Bindel, CS 4220: Numerical Analysis, “Cholesky factorization”: complete block-recursion discussion; it leaves positivity of the Schur complement as an exercise, which the proof below supplies.
Tobin A. Driscoll and Richard J. Braun, Fundamentals of Numerical Computation, §2.9.3: symmetric positive-definite matrices, the positive-diagonal Cholesky factor, and the LDLᵀ square-root construction.
Facts & Assumptions
Given: A real symmetric positive-definite matrix with . Prove the displayed recurrence is defined at every stage and returns its positive-diagonal Cholesky factor.
is real symmetric and for every nonzero .
Hermitian positive-definite matrices and Cholesky factorisation A = LL* with positive diagonal: over , positive definiteness means symmetry and for every nonzero vector; a Cholesky factor is lower triangular with positive diagonal and satisfies .
Rank-nullity: : for a linear map on a finite-dimensional space, dimension equals kernel dimension plus image dimension; hence zero kernel implies full-dimensional image and invertibility.
Proof
Induct on . At , testing in [A1] gives . For , suppose columns have been computed with positive diagonal and let and ; the induction hypothesis gives . The block is positive definite because extending any nonzero by zeros gives a nonzero vector to which [A1] applies. Its kernel is therefore zero; [F2] makes invertible. The lower-triangular matrix is invertible as well, since solving row by row with its positive diagonal forces every coordinate of to be zero. Put and . The already computed recurrence at each column gives , so . Since , this implies . The leading block of is positive definite by the same zero-extension argument. For the nonzero vector , its quadratic form under is . Thus is positive and every division defining is by a positive number. The recurrence is well-defined through column , and the same formulas give the factorization identity on the leading block.
For every , the pivot equation gives . For every , rearranging the recurrence gives . These identities fill the diagonal and lower triangle; symmetry of and fills the upper triangle. The initialized matrix remains lower triangular, and each diagonal entry is positive by step 1.1, so it is the required Cholesky factor.
Depends on
Used by
Dependency tree · two levels
9 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- David Bindel, CS 4220: Numerical Analysis, Blocked LU and Cholesky (standard reference, not scraped)
- Tobin A. Driscoll and Richard J. Braun, Fundamentals of Numerical Computation, §2.9.3 (standard reference, not scraped)