Pipeline-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.

✓ 10 results · all verified · 6 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 4 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Direct Matrix Factorisations: LU, Cholesky and QR: Examples and Counterexamples

1 · Prerequisites

2 · Summary

These examples keep the A-page hypotheses honest. They show an invertible matrix that still fails unpivoted LU, a concrete PLU and LDU computation, a block LU solve through a Schur complement, a worked Cholesky solve, and the exact ways indefinite or merely semidefinite matrices fall outside positive-diagonal Cholesky.

The QR examples compute a short Householder factorization, use Givens rotations to preserve sparsity while zeroing chosen entries, compare reduced QR with the normal equations on a badly scaled least-squares problem, and exhibit fill-in created by Gaussian elimination.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

CounterexampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passaudited 2026-08-30Open item page →

An invertible matrix can fail unpivoted LU at the first pivot

Statement refuted

Every invertible square matrix has an unpivoted unit-lower LU factorisation.

Facts & Assumptions

Given: The matrix $A = (\begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array}) .$

[L1]

A square matrix has an unpivoted unit-lower LU factorisation with nonzero pivots exactly when every leading principal minor is nonzero (A square matrix has an unpivoted unit-lower LU factorisation exactly when all leading principal minors are nonzero).

Counterexample

technique · direct

1.1

The determinant of $A$ is $- 1$ , so $A$ is invertible. Its first leading principal minor is the $1 \times 1$ determinant $Δ_{1} = 0$ .

givenalgebra

2.1

By [L1], the vanishing of $Δ_{1}$ forbids an unpivoted unit-lower LU factorisation with nonzero pivots. Therefore invertibility alone does not suffice.

step 1.1L1

3.1

Step 2.1 refutes the statement.

step 2.1∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-30Open item page →

A full PLU factorisation can be computed explicitly by hand

Example

For $A = (\begin{array}{ccc} 0 & 1 & 1 \\ 2 & 1 & 1 \\ 1 & 1 & 2 \end{array}),$

partial pivoting gives

$P = (\begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{array}), L = (\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ \frac{1}{2} & \frac{1}{2} & 1 \end{array}), U = (\begin{array}{ccc} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{array}),$

and these satisfy $P A = L U$ .

Facts & Assumptions

Given: The displayed matrix $A$ and the candidate factors $P, L, U$ .

[L1]

Every square matrix admits a PLU factorisation, and partial pivoting records the row swaps in a permutation matrix (Every real or complex square matrix admits a PLU factorisation, and the first failed pivot marks the singular boundary, Permutation matrices, partial pivoting, and the pivot-growth factor).

Verification

technique · direct

1.1

The largest entry in modulus in the first column is $2$ in row $2$ , so the first pivot swap sends that row to the top. The first elimination multipliers are $0$ for the new second row and $1 / 2$ for the new third row, producing the intermediate matrix $(\begin{array}{ccc} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & \frac{1}{2} & \frac{3}{2} \end{array}) .$ The second pivot is already the entry $1$ in row $2$ , so no further swap is needed, and eliminating the $(3, 2)$ entry with multiplier $1 / 2$ gives the displayed $U$ . Recording the two nonzero multipliers in the permuted row order gives the displayed $L$ .

givenL1algebra

2.1

Direct multiplication gives $L U = (\begin{array}{ccc} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 2 \end{array}) = P A .$ Hence the displayed matrices are a correct PLU factorisation.

step 1.1algebra

3.1

Steps 1.1-2.1 verify the example.

step 1.1step 2.1∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-30Open item page →

An LDU factorisation isolates the pivot scalars uniquely

Example

The matrix $A = (\begin{array}{cc} 2 & 1 \\ 4 & 5 \end{array})$

has the LDU factorisation

$A = (\begin{array}{cc} 1 & 0 \\ 2 & 1 \end{array}) (\begin{array}{cc} 2 & 0 \\ 0 & 3 \end{array}) (\begin{array}{cc} 1 & \frac{1}{2} \\ 0 & 1 \end{array}),$

and the diagonal pivots $2, 3$ are uniquely determined.

Facts & Assumptions

Given: The displayed matrix $A$ and candidate LDU factors.

[L1]

An LDU factorisation has the displayed unit-lower, diagonal, and unit-upper shape (An LDU factorisation has unit lower-triangular L, diagonal D, and unit upper-triangular U).

[L2]

LDU factorisations with nonzero diagonal pivots are unique (Normalised LU and LDU factorisations with nonzero pivots are unique).

Verification

technique · direct

1.1

Multiplying the right two factors gives $(\begin{array}{cc} 2 & 0 \\ 0 & 3 \end{array}) (\begin{array}{cc} 1 & \frac{1}{2} \\ 0 & 1 \end{array}) = (\begin{array}{cc} 2 & 1 \\ 0 & 3 \end{array}),$ and then left multiplication by $(\begin{array}{cc} 1 & 0 \\ 2 & 1 \end{array})$ yields $(\begin{array}{cc} 2 & 1 \\ 4 & 5 \end{array}) = A$ .

givenL1algebra

2.1

The diagonal factor has nonzero entries $2$ and $3$ , so [L2] applies. Any other LDU factorisation of $A$ with nonzero diagonal pivots must therefore have the same diagonal factor and hence the same pivot scalars.

step 1.1L2

3.1

Steps 1.1-2.1 verify the example.

step 1.1step 2.1∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-30Open item page →

A block LU factorisation turns a linear solve into a Schur-complement solve

Example

For $A = (\begin{array}{ccc} 2 & 1 & 1 \\ 1 & 3 & 1 \\ 1 & 1 & 2 \end{array})$

with the $1 + 2$ block split, the Schur complement is

$S = (\begin{array}{cc} \frac{5}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{3}{2} \end{array}),$

and

$A = (\begin{array}{ccc} 1 & 0 & 0 \\ \frac{1}{2} & 1 & 0 \\ \frac{1}{2} & 0 & 1 \end{array}) (\begin{array}{ccc} 2 & 1 & 1 \\ 0 & \frac{5}{2} & \frac{1}{2} \\ 0 & \frac{1}{2} & \frac{3}{2} \end{array}) .$

For the right-hand side $b = (4, 5, 4)^{T}$ , the solve $A x = b$ reduces to the Schur-complement solve and yields $x = (1, 1, 1)^{T}$ .

Facts & Assumptions

Given: The displayed matrix $A$ , its block split, the right-hand side $b$ , and the candidate factorisation.

[L1]

An invertible leading block yields the block LU factorisation through its Schur complement (An invertible leading block yields block LU through its Schur complement).

[L2]

Triangular systems are solved by forward and backward substitution (Forward and backward substitution are correct, unique, and quadratic in scalar operations).

Verification

technique · direct

1.1

The leading block is $A_{11} = [2]$ , so $S = (\begin{array}{cc} 3 & 1 \\ 1 & 2 \end{array}) - \frac{1}{2} (\binom{1}{1}) (1 1)$ , which is the displayed Schur complement. The block-LU formula of [L1] gives the displayed factorisation.

givenL1algebra

2.1

Solve $L y = b$ : $y_{1} = 4$ , $y_{2} = 5 - \frac{1}{2} \cdot 4 = 3$ , $y_{3} = 4 - \frac{1}{2} \cdot 4 = 2$ . Then solve $U x = y$ from the bottom: $\frac{3}{2} x_{3} = 2 - \frac{1}{2} x_{2}$ , $\frac{5}{2} x_{2} + \frac{1}{2} x_{3} = 3$ , and $2 x_{1} + x_{2} + x_{3} = 4$ . This gives $x_{3} = 1$ , $x_{2} = 1$ , and $x_{1} = 1$ .

step 1.1L2algebra

3.1

Steps 1.1-2.1 verify both the factorisation and the Schur-complement solve.

step 1.1step 2.1∎

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-30Open item page →

A Cholesky factorisation solves a small positive-definite system efficiently

Example

The symmetric positive-definite matrix $A = (\begin{array}{cc} 4 & 2 \\ 2 & 3 \end{array})$ has Cholesky factor $L = (\begin{array}{cc} 2 & 0 \\ 1 & \sqrt{2} \end{array}),$ and for $b = (6, 5)^{T}$ the solve $A x = b$ gives $x = (1, 1)^{T}$ .

Facts & Assumptions

Given: The displayed matrix $A$ , the candidate factor $L$ , and $b = (6, 5)^{T}$ .

[L1]

Hermitian positive-definite matrices admit a unique Cholesky factorisation with positive diagonal (A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique).

[L2]

Cholesky solves $A x = b$ by two triangular substitutions (Cholesky solves Hermitian positive-definite systems and has about half the factorisation cost of LU).

Verification

technique · direct

1.1

Direct multiplication gives $L L^{T} = (\begin{array}{cc} 2 & 0 \\ 1 & \sqrt{2} \end{array}) (\begin{array}{cc} 2 & 1 \\ 0 & \sqrt{2} \end{array}) = (\begin{array}{cc} 4 & 2 \\ 2 & 3 \end{array}) = A,$ so the displayed matrix is a Cholesky factor.

givenL1algebra

2.1

Solve $L y = b$ : $2 y_{1} = 6$ and $y_{1} + \sqrt{2} y_{2} = 5$ , so $y_{1} = 3$ and $y_{2} = \sqrt{2}$ . Then solve $L^{T} x = y$ : $\sqrt{2} x_{2} = \sqrt{2}$ and $2 x_{1} + x_{2} = 3$ , hence $x_{2} = 1$ and $x_{1} = 1$ .

step 1.1L2algebra

3.1

Steps 1.1-2.1 verify the example.

step 1.1step 2.1∎

CounterexampleConstruction: AI-adaptedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-30Open item page →

Indefinite and semidefinite matrices can both fail positive-diagonal Cholesky

Statement refuted

Indefinite matrices, and even positive-semidefinite singular matrices, admit Cholesky factorisations with positive diagonal.

Facts & Assumptions

Given: The matrices $A = (\begin{array}{cc} 1 & 0 \\ 0 & - 1 \end{array}), B = (\begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array}) .$

[L1]

A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite (A matrix admits a Cholesky factorisation with positive diagonal exactly when it is Hermitian positive definite, and that factor is unique).

Counterexample

technique · direct

1.1

The matrix $A$ is Hermitian, but with $x = (0, 1)^{T}$ one has $x^{*} A x = - 1 < 0$ , so $A$ is not positive definite. Therefore [L1] forbids a positive-diagonal Cholesky factorisation of $A$ .

givenL1algebra

1.2

The matrix $B$ is positive semidefinite but singular. If $B = L L^{*}$ with positive diagonal, then every diagonal entry of $L$ is nonzero, so $L$ would be invertible and $B$ would be invertible as well, a contradiction. Hence $B$ also has no such Cholesky factorisation.

givenL1algebra

2.1

Steps 1.1-1.2 refute the statement in both the indefinite and the merely semidefinite cases.

step 1.1step 1.2∎

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-30Open item page →

A short dense matrix admits a worked Householder QR factorisation

Example

For $A = (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array}),$

the unit vector $v = \frac{1}{\sqrt{2 (2 - \sqrt{2})}} (\binom{1 - \sqrt{2}}{1})$ gives the Householder reflector

$H = I - 2 v v^{T} = \frac{1}{\sqrt{2}} (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array}) .$

Hence

$A = Q R, Q = H, R = H A = (\begin{array}{cc} \sqrt{2} & 0 \\ 0 & \sqrt{2} \end{array}) .$

Facts & Assumptions

Given: The displayed matrix $A$ , vector $v$ , and reflector $H$ .

[L1]

Successive Householder reflectors produce QR factorisations (Successive Householder or Givens transformations produce full and reduced QR factorisations with the standard dense operation counts).

Verification

technique · direct

1.1

The vector $v$ has norm $1$ , and direct multiplication of $I - 2 v v^{T}$ gives the displayed matrix $H$ . Since $H^{T} H = I$ , it is an orthogonal reflector.

givenalgebra

2.1

Multiplying by $A$ gives $H A = \frac{1}{\sqrt{2}} (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array}) (\begin{array}{cc} 1 & 1 \\ 1 & - 1 \end{array}) = (\begin{array}{cc} \sqrt{2} & 0 \\ 0 & \sqrt{2} \end{array}) .$ Thus $A = Q R$ with $Q = H$ and $R$ upper triangular, exactly as predicted by [L1].

step 1.1L1algebra

3.1

Steps 1.1-2.1 verify the example.

step 1.1step 2.1∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-30Open item page →

Givens QR can zero selected entries of a sparse matrix one at a time

Example

For $A = (\begin{array}{cc} 3 & 4 \\ 4 & 3 \\ 0 & 2 \end{array}),$ first apply a Givens rotation in rows $1, 2$ with $c = 3 / 5$ , $s = 4 / 5$ , then a second Givens rotation in rows $2, 3$ with $c = - 7 / \sqrt{149}$ , $s = 10 / \sqrt{149}$ . The product zeros one selected entry at a time and yields $R = (\begin{array}{cc} 5 & \frac{24}{5} \\ 0 & \frac{\sqrt{149}}{5} \\ 0 & 0 \end{array}) .$

Facts & Assumptions

Given: The displayed matrix $A$ and the two named Givens rotations.

[L1]

Givens transformations are unitary and can annihilate a chosen second coordinate (Householder reflectors and Givens transformations are unitary and can annihilate prescribed entries).

[L2]

Successive Givens transformations produce QR factorizations (Successive Householder or Givens transformations produce full and reduced QR factorisations with the standard dense operation counts).

Verification

technique · direct

1.1

The first rotation $G_{1} = (\begin{array}{ccc} 3 / 5 & 4 / 5 & 0 \\ - 4 / 5 & 3 / 5 & 0 \\ 0 & 0 & 1 \end{array})$ sends the first column $(3, 4, 0)^{T}$ to $(5, 0, 0)^{T}$ , so it zeros the $(2, 1)$ entry while preserving the zero in position $(3, 1)$ . Applied to the second column, it gives $(24 / 5, - 7 / 5, 2)^{T}$ .

L1algebra

2.1

The second rotation $G_{2} = (\begin{array}{ccc} 1 & 0 & 0 \\ 0 & - 7 / \sqrt{149} & 10 / \sqrt{149} \\ 0 & - 10 / \sqrt{149} & - 7 / \sqrt{149} \end{array})$ acts only on rows $2, 3$ , so it keeps the first column fixed and sends $(- 7 / 5, 2)^{T}$ to $(\sqrt{149} / 5, 0)^{T}$ . Hence $R = G_{2} G_{1} A = (\begin{array}{cc} 5 & 24 / 5 \\ 0 & \sqrt{149} / 5 \\ 0 & 0 \end{array}),$ the displayed upper-triangular matrix.

step 1.1L1algebra

3.1

Since both rotations are unitary, $Q = (G_{2} G_{1})^{*}$ and $A = Q R$ . This verifies the Givens QR factorisation promised by [L2].

step 2.1L2algebra

4.1

Steps 1.1-3.1 verify the example.

step 1.1step 2.1step 3.1∎

ExampleConstruction: Literature-sourcedVerification: AI-adaptedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-30Open item page →

Reduced QR avoids the condition-number squaring seen in the normal equations

Example

Let $A = (\begin{array}{cc} 1 & 0 \\ 0 & 10^{- 4} \\ 0 & 0 \end{array}), b = (\begin{array}{c} 1 \\ 1 \\ 0 \end{array}) .$ Then $A$ already has reduced QR factorisation $A = \hat{Q} \hat{R}$ with $\hat{Q} = (e_{1}, e_{2})$ and $\hat{R} = diag (1, 10^{- 4})$ . The least-squares solution is $x = (1, 10^{4})^{T}$ , while $κ_{2} (\hat{R}) = 10^{4}$ and $κ_{2} (A^{T} A) = 10^{8}$ .

Facts & Assumptions

Given: The displayed matrix $A$ , vector $b$ , and reduced QR factorisation.

[L1]

Reduced QR solves full-column-rank least squares through $\hat{R} x = {\hat{Q}}^{*} b$ and avoids the condition-number square of the normal equations (Reduced QR over the reals solves full-column-rank least squares without squaring the condition number).

Verification

technique · direct

1.1

The columns of $A$ are already orthogonal, so $\hat{Q} = (e_{1}, e_{2})$ and $\hat{R} = diag (1, 10^{- 4})$ form a reduced QR factorisation. Also ${\hat{Q}}^{*} b = (1, 1)^{T}$ .

givenalgebra

2.1

Solving $\hat{R} x = {\hat{Q}}^{*} b$ gives $x_{1} = 1$ and $10^{- 4} x_{2} = 1$ , hence $x = (1, 10^{4})^{T}$ . The factor $\hat{R}$ has spectral condition number $10^{4}$ , whereas $A^{T} A = diag (1, 10^{- 8})$ has spectral condition number $10^{8}$ . This is exactly the contrast described in [L1].

step 1.1L1algebra

3.1

Steps 1.1-2.1 verify the example.

step 1.1step 2.1∎

ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passaudited 2026-08-30Open item page →

Sparse Gaussian elimination can create fill-in in the factors

Example

The sparse matrix $A = (\begin{array}{ccc} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{array})$ has a zero in position $(3, 2)$ , but after the first elimination step that entry becomes $- 1$ . Thus Gaussian elimination can create nonzeros that were absent in the original matrix.

Facts & Assumptions

Given: The displayed sparse matrix $A$ .

[L1]

Pivoting language records the elimination process entry by entry (Permutation matrices, partial pivoting, and the pivot-growth factor).

Verification

technique · direct

1.1

Use the first pivot $a_{11} = 1$ . Eliminating the entries below it subtracts row $1$ from rows $2$ and $3$ , giving $(\begin{array}{ccc} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & - 1 & 1 \end{array}) .$ The entry in position $(3, 2)$ was $0$ before elimination and is now $- 1$ .

givenL1algebra

2.1

The new nonzero in step 1.1 is fill-in: it appears after one elimination step even though the corresponding original entry was zero.

step 1.1

3.1

Steps 1.1-2.1 verify the example.

step 1.1step 2.1∎

Direct Matrix Factorisations: LU, Cholesky and QR: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

An invertible matrix can fail unpivoted LU at the first pivot

Statement refuted

Facts & Assumptions

Counterexample

A full PLU factorisation can be computed explicitly by hand

Example

Facts & Assumptions

Verification

An LDU factorisation isolates the pivot scalars uniquely

Example

Facts & Assumptions

Verification

A block LU factorisation turns a linear solve into a Schur-complement solve

Example

Facts & Assumptions

Verification

A Cholesky factorisation solves a small positive-definite system efficiently

Example

Facts & Assumptions

Verification

Indefinite and semidefinite matrices can both fail positive-diagonal Cholesky

Statement refuted

Facts & Assumptions

Counterexample

A short dense matrix admits a worked Householder QR factorisation

Example

Facts & Assumptions

Verification

Givens QR can zero selected entries of a sparse matrix one at a time

Example

Facts & Assumptions

Verification

Reduced QR avoids the condition-number squaring seen in the normal equations

Example

Facts & Assumptions

Verification

Sparse Gaussian elimination can create fill-in in the factors

Example

Facts & Assumptions

Verification

Sources