Alphabeta Math
LemmaStatement: AI-adaptedProof: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)
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 n≥1 and let M∈Rn×n be symmetric positive definite, meaning xTMx>0 for every nonzero x∈Rn. Initialize R as the zero n×n matrix. For j=1,…,n in order, set pj=Mjj−∑k<jRjk2,Rjj=pj, and then, for i=j+1,…,n in order, set Rij=Mij−∑k<jRikRjkRjj. Every pivot pj is positive, so the recurrence is well-defined and returns a lower-triangular matrix R with positive diagonal satisfying M=RRT.

Statement references

Hermitian positive-definite matrices and Cholesky factorisation A = LL* with positive diagonal: over the real numbers, positive definiteness means xTMx>0 for every nonzero vector, and the Cholesky factor has the form RRT with R lower triangular and positive diagonal.

Rank-nullity: dim⁡FV=nullity⁡T+rank⁡T: 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 M∈Rn×n with n≥1. Prove the displayed recurrence is defined at every stage and returns its positive-diagonal Cholesky factor.

[A1]

M is real symmetric and xTMx>0 for every nonzero x∈Rn.

[F1]

Hermitian positive-definite matrices and Cholesky factorisation A = LL* with positive diagonal: over R, positive definiteness means symmetry and xTMx>0 for every nonzero vector; a Cholesky factor is lower triangular with positive diagonal and satisfies M=RRT.

[F2]

Rank-nullity: dim⁡FV=nullity⁡T+rank⁡T: 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

1.1givenA1F1F2inductionalgebra

Induct on j. At j=1, testing e1 in [A1] gives p1=M11>0. For j>1, suppose columns 1,…,j−1 have been computed with positive diagonal and let T=R{1,…,j−1},{1,…,j−1} and A=M{1,…,j−1},{1,…,j−1}; the induction hypothesis gives A=TTT. The block A is positive definite because extending any nonzero x∈Rj−1 by zeros gives a nonzero vector to which [A1] applies. Its kernel is therefore zero; [F2] makes A invertible. The lower-triangular matrix T is invertible as well, since solving Tx=0 row by row with its positive diagonal forces every coordinate of x to be zero. Put m=(M1j,…,Mj−1,j)T and u=(Rj1,…,Rj,j−1)T. The already computed recurrence at each column i<j gives Mij=∑k<iRikRjk+RiiRji, so Tu=m. Since A=TTT, this implies mTA−1m=uTu. The leading j×j block P of M is positive definite by the same zero-extension argument. For the nonzero vector (−A−1m,1), its quadratic form under P is Mjj−mTA−1m=Mjj−uTu=pj>0. Thus Rjj=pj is positive and every division defining Rij is by a positive number. The recurrence is well-defined through column j, and the same formulas give the factorization identity on the leading j×j block.

2.1step 1.1F1algebra∎

For every j, the pivot equation gives Mjj=∑k<jRjk2+Rjj2=(RRT)jj. For every i>j, rearranging the recurrence gives Mij=∑k<jRikRjk+RijRjj=(RRT)ij. These identities fill the diagonal and lower triangle; symmetry of M and RRT 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