Cholesky factors, solves and energy certificates

Try

Take the symmetric matrix A(t) with rows (2,1,0), (1,2,1), (0,1,t). The parameter t changes only one entry. Nevertheless, it can change whether every right-hand side has a unique solution and whether a quadratic energy has a minimum. We will use exact real arithmetic before discussing numerical limitations.

Elimination without row exchanges gives A(t)=LDLᵀ, where L has rows (1,0,0), (1/2,1,0), (0,2/3,1), and D has diagonal entries 2, 3/2, t−2/3. Multiply these factors to check the last diagonal entry: it is (2/3)²·(3/2)+(t−2/3)=t.

Predict what changes at t=2/3. Above this threshold all three entries of D are positive. At the threshold the last is zero. Below it one is negative. Because xᵀA(t)x=(Lᵀx)ᵀD(Lᵀx) and Lᵀ is invertible, these signs determine the quadratic form’s positivity, zero directions or negative directions.

Predict

When the diagonal entries d₁,d₂,d₃ of D are positive, take their positive square roots. Set C=L√D, where √D is diagonal. Then CCᵀ=L D Lᵀ=A. This is the Cholesky factor, chosen lower triangular with positive diagonal. Multiplication on the right scales columns of L, not rows.

For t=2 the factor is as follows. Reconstruct its off-diagonal entries by multiplication rather than matching only the diagonal.

Predict whether the same positive-diagonal recipe can be applied below t=2/3. It cannot take a real square root of the last negative pivot. This is not merely a limitation of this algorithm: every real CCᵀ is positive semidefinite, since xᵀCCᵀx=‖Cᵀx‖₂².

Experiment

Use the explorer to compare the positive, zero and negative last-pivot cases. Before inspecting a result, predict whether the real positive-diagonal Cholesky factor exists and whether the energy can have a unique minimizer. Keep a factor identity, a solve and an energy conclusion separate: each has different hypotheses. Select t=2 and the first right-hand side, then change Line parameter s from 0 to 1/3: the displayed line reaches (1,−1,1) with energy −1. The graph explores only its stated one-dimensional affine line, not all vectors. Its s is a playground coordinate distinct from the free parameter used in the later paper solution. The exact fixed calculations below remain at t=2 regardless of later control changes.

From a positive pivot to a minimum

A has rows (2, 1, 0), (1, 2, 1), (0, 1, t). Change its last entry and predict whether a real Cholesky factor and a unique energy minimum survive.

Matrix parameter t02/312 Right-hand sideb = (1, 0, 1)b = (1, 0, −1/3) Line parameter s-2-5/3-4/3-1-2/3-1/301/32/314/35/32 Reset explorer

A is positive definite. Leading principal minors: (2, 3, 4). Exact LDLᵀ pivots: (2, 3/2, 4/3). L has rows (1, 0, 0), (1/2, 1, 0), (0, 2/3, 1).

For w = (1, −2, 3), the exact quadratic value wᵀAw is 12. A negative value disproves positive semidefiniteness. A zero value for nonzero w disproves positive definiteness; it does not by itself prove semidefiniteness.

Inspect the real factor C with A = CCᵀ

C = L diag(√2, √(3/2), √(t − 2/3)). Its rows below are rounded to six decimals; the LDLᵀ values above are exact.

(1.414214, 0.000000, 0.000000)

(0.707107, 1.224745, 0.000000)

(0.000000, 0.816497, 1.154701)

Inspect the energy along a revealing line

Use E(x) = xᵀAx/2 − bᵀx and x(s) = (2/3, −1/3, 0) + s(1, −2, 3). Here s is a real line parameter, not an iteration count. The displayed controls sample it in thirds.

Along this line E = −1/3 + (9t − 6)s²/2 − 4s. The two axes stay fixed as t and b change. The curve is a plot of this formula; it is not an optimization run.

Current x = (2/3, -1/3, 0). E(x) = -1/3. Residual Ax − b = (0, 0, -4/3).

Unique global minimum: x = (1, -1, 1), at s = 1/3 on this line. Positive definiteness and the completed-square identity prove global minimality, not just this plotted segment.

Start at t = 2 and select s = 1/3 to reach the minimum for b = (1, 0, 1). Then set t = 2/3 and compare both right-hand sides. Explain why the same zero pivot can accompany either no minimum or many minima. These temporary controls do not record completion.

For a fixed paper example, set t=2 and b=(1,0,1). Solve Cy=b forward, then Cᵀx=y backward. Forward substitution gives y=(1/√2,−1/√6,2/√3). Back substitution gives x=(1,−1,1). Check the original equations: their outputs are (1,0,1).

The same answer minimizes E(x)=xᵀAx/2−bᵀx. At this solution bᵀx=2, so the minimum value is −1. To test that this is a certificate rather than an isolated evaluation, perturb the solution by an arbitrary vector h. The energy increases by hᵀAh/2, which is strictly positive unless h=0.

Understand

The preceding positive LDLᵀ theorem supplies a constructive dependency: for a real symmetric positive definite matrix, a unit lower L and positive diagonal D exist. Taking the scalar positive square roots constructs C, with no general matrix-square-root theorem needed. This factor is unique under the positive-diagonal convention. If A=CCᵀ=HHᵀ, set Q=C⁻¹H. It is lower triangular with positive diagonal and QQᵀ=I. Its inverse equals Qᵀ and is both lower and upper triangular, so Q is diagonal. Each diagonal entry has square 1 and is positive. Hence Q=I and C=H. The inverses here exist because the diagonals are strictly positive.

To solve Ax=b, the triangular systems Cy=b and Cᵀx=y uniquely determine all coordinates. Their product gives the original equation. There is no need to form A⁻¹. These are exact existence and uniqueness statements; they do not themselves bound the errors of a floating-point implementation.

For energy, let x⋆ be this solution and write x=x⋆+h. Expanding and using symmetry and Ax⋆=b cancels the terms linear in h, giving

E(x)−E(x⋆)=hᵀAh/2.

Positive definiteness makes x⋆ the unique global minimizer. A residual r=Ax−b measures equation mismatch. If a known number μ>0 satisfies vᵀAv≥μ‖v‖₂² for all v, then μ‖h‖²≤hᵀAh=hᵀr≤‖h‖‖r‖. Therefore ‖h‖≤‖r‖/μ, with h=0 handled directly. Without a lower bound such as μ, a small residual alone need not mean a small solution error. For diag(ε,1), b=0 and x=(1,0), the residual norm is ε but the error norm is 1 for every ε>0.

Cholesky also enters least squares. For a real m×n matrix B, the Gram matrix BᵀB satisfies xᵀBᵀBx=‖Bx‖². It is positive definite exactly when B has independent columns. Then the normal equations BᵀBx=Bᵀy have a unique solution. Its residual is orthogonal to every column of B, so adding any h to x increases the squared data residual by ‖Bh‖². This proves the least-squares conclusion directly. Numerically, however, forming BᵀB can square the spectral condition number: its eigenvalues are the squared singular values of B. That observation uses the singular-value theorem and motivates QR methods; it is not contradicted by exact positive definiteness.

The complex Hermitian extension replaces every transpose by conjugate transpose, denoted ∗. A positive Hermitian LDL∗ factorization gives C=L√D with positive real diagonal and A=CC∗. The uniqueness argument uses QQ∗=I and the same triangular reasoning. Ordinary transpose is wrong for complex data because squared magnitudes require conjugation. This is a stated extension of the real proof, using the Hermitian LDL∗ theorem as its prerequisite.

Apply

At t=2/3, a kernel vector is z=(1,−2,3), since Lᵀz=(0,0,3) and the last entry of D vanishes. For b=(1,0,1), bᵀz=4. Along x=sz the quadratic part vanishes and E(sz)=−4s, so the energy is unbounded below as s grows. The equation is incompatible: zᵀAx=0 cannot equal zᵀb=4. This matrix is positive semidefinite, yet not every linear forcing term gives a minimum.

Change instead to b=(1,0,−1/3). Now bᵀz=0. Solving gives x=(1/2−s/2,s,−1/2−3s/2) for arbitrary real s. Check all three equations. These vectors differ by kernel directions and all minimize the same energy: around any solution, the difference remains hᵀAh/2≥0. The minimum is not unique.

Zero pivots need explicit branches. A positive semidefinite matrix with a zero diagonal entry has an entirely zero corresponding row and column: test eᵢ+s eⱼ and choose a small signed s to contradict positivity if the cross entry were nonzero. A semidefinite factor can be constructed recursively: if its first diagonal is zero, the row lemma permits a zero first factor column and recursion on the remaining principal block. If it is positive, completing the square shows that its Schur complement is positive semidefinite; recurse on that block after the ordinary elimination step. This gives existence with special zero-column choices, but the strictly positive algorithm cannot divide by a zero pivot. Even lower triangular factors with nonnegative diagonals need not be unique: diag(0,1)=CCᵀ for every C with rows (0,0),(c,√(1−c²)), where −1≤c≤1. A canonical zero-column convention would select one of these; it is an added convention, not the positive-diagonal uniqueness theorem.

Continue

Record symmetry, pivot signs and the exact positivity hypothesis before claiming a Cholesky solve or a unique energy minimum. A singular factor may exist without invertibility; an indefinite real matrix cannot equal CCᵀ. A small residual becomes an error certificate only after a suitable scale bound is supplied.

For the numerical alternative to forming Gram matrices, return to least squares and QR. For the orthogonal-residual argument, revisit least squares and residuals. These links distinguish the exact structure proved here from numerical algorithm selection.