TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generated

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.

Ordered sparse Cholesky has the symbolic filled pattern when no cancellation occurs

Statement

Let $A \in C^{n \times n}$ be Hermitian positive definite and use its pattern from Undirected structural graph of a Hermitian matrix. The local Hermitian Schur-support lemma Hermitian Schur-complement support stays inside the symmetric filled graph applies. In exact arithmetic, the Cholesky recurrence in Ordered sparse Cholesky with explicit pivot and range statuses returns the unique factor $L$ satisfying $P A P^{*} = L L^{*}$ and positive diagonal, and every nonzero strict-lower entry of $L$ is permitted by the filled graph $G_{π}^{+}$ .

For $i > j$ with ${i, j} \in E_{π}^{+}$ (where ordered position $i$ represents original vertex $v_{i}$ ), define the recurrence numerator $ν_{i j} = B_{i j} - \sum_{k < j} l_{i k} \overline{l_{j k}}, B = P A P^{*} .$ If $ν_{i j} \neq 0$ at every permitted strict-lower position, then the numerical nonzero pattern of $L$ is exactly the lower-triangular part of $G_{π}^{+}$ together with its diagonal. Without this no-cancellation hypothesis only the upper-pattern inclusion is asserted.

Facts & Assumptions

Given: A Hermitian positive-definite matrix $A$ , the stated batch-2 graph/ordering interface, and its Schur-support hypothesis.

[F1]

Ordered sparse Cholesky with explicit pivot and range statuses: The permutation matrix has row $j$ equal to row $v_{j}$ of $I_{n}$ , and the exact algorithm uses $d_{j} = B_{j j} - \sum_{k < j} ∣ l_{j k} ∣^{2}$ , $l_{j j} = \sqrt{d_{j}}$ , and $l_{i j} = (B_{i j} - \sum_{k < j} l_{i k} \overline{l_{j k}}) / l_{j j}$ on filled positions.

[F2]

Hermitian Schur-complement support stays inside the symmetric filled graph: With nonzero scalar pivots, each Hermitian Schur complement is supported inside the Hermitian filled graph.

[F3]

A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique: A Hermitian positive-definite matrix has a unique factorization $C = R R^{*}$ with $R$ lower triangular and positive real diagonal.

Proof

1.1givenF1F3algebra

A permutation preserves positive definiteness: for $x \neq 0$ , $P^{*} x \neq 0$ and $x^{*} B x = (P^{*} x)^{*} A (P^{*} x) > 0$ . Thus [F3] gives a unique exact Cholesky factor $R$ of $B$ .

2.1step 1.1F3algebra

Independently of the sparse algorithm, define dense active matrices on $a, b \geq j$ by $S_{a b}^{j} = B_{a b} - \sum_{k < j} r_{a k} \overline{r_{b k}}$ . Since $B = R R^{*}$ and $R$ is lower triangular, $S_{j j}^{j} = r_{j j}^{2} > 0$ and $S_{i j}^{j} = r_{i j} r_{j j}$ for $i > j$ . Subtracting $S_{a j}^{j} S_{j b}^{j} / S_{j j}^{j} = r_{a j} \overline{r_{b j}}$ gives $S_{a b}^{j + 1}$ . Thus these are precisely the dense Hermitian Schur updates starting from $S^{0} = B$ , with every pivot nonzero, without assuming anything about the sparse output.

3.1step 2.1F1F2algebra

Apply [F2] to the dense Schur sequence from step 2.1, using original vertex labels $v_{a}, v_{b}$ for ordered positions $a, b$ . If ${i, j} \notin E_{π}^{+}$ with $i > j$ , it is absent from the active filled graph at stage $j$ , so $S_{i j}^{j} = 0$ . As $S_{i j}^{j} = r_{i j} r_{j j}$ and $r_{j j} > 0$ , this forces $r_{i j} = 0$ . Hence the dense factor $R$ already has the required structural support, before it is compared with the sparse recurrence.

4.1step 2.1step 3.1F1baseIHinductionalgebra

Induct on the sparse column index $j$ , with no preceding columns at $j = 0$ . Assume $l_{i k} = r_{i k}$ for all $k < j$ . By step 2.1 the pivot recurrence in [F1] gives $d_{j} = S_{j j}^{j} = r_{j j}^{2} > 0$ and $l_{j j} = r_{j j}$ . On every permitted position its numerator is $S_{i j}^{j} = r_{i j} r_{j j}$ , so the computed $l_{i j}$ equals $r_{i j}$ . On an omitted position the algorithm sets $l_{i j} = 0$ , which equals $r_{i j}$ by step 3.1. This completes the induction, proving $L = R$ and success at every exact pivot.

5.1step 3.1step 4.1F1algebra

At each permitted strict-lower position, the recurrence gives $l_{i j} = ν_{i j} / l_{j j}$ and step 4.1 gives $l_{j j} > 0$ . Hence $ν_{i j} \neq 0$ implies $l_{i j} \neq 0$ . Under the stated no-cancellation condition every permitted position is nonzero; together with step 3.1 and $L = R$ this gives equality of patterns.

6.1step 3.1step 4.1step 5.1discharge-induction∎

Step 4.1 establishes that the exact algorithm returns the unique Cholesky factor; step 3.1 proves the structural upper pattern in the complex Hermitian case; step 5.1 proves equality under the no-cancellation hypothesis. No finite-precision success or stability claim follows from this exact-arithmetic theorem.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

13 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

Jennifer Scott and Miroslav Tůma, Algorithms for Sparse Linear Systems, Chapter 4, §§4.1–4.3 (standard reference, not scraped)
Timothy A. Davis, Siva Rajamanickam, and Wissam M. Sid-Lakhdar, A survey of direct methods for sparse linear systems, §§4–5 (standard reference, not scraped)