TheoremStatement: AI-adaptedProof: AI-generatedprecheck passaudited 2026-08-31

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.

Before breakdown, Arnoldi produces an orthonormal Krylov basis and a rectangular upper-Hessenberg factorization

Statement

Let $A$ be an $n \times n$ matrix over $R$ or $C$ , let $b$ be a nonzero vector of matching size, and let $m \geq 1$ . Assume the Arnoldi process for $(A, b)$ runs through step $m$ without breakdown. Let

$Q_{m} = [v_{1} \dots v_{m}], Q_{m + 1} = [v_{1} \dots v_{m + 1}],$

and let ${\overset{ˉ}{H}}_{m} = (h_{i j})_{1 \leq i \leq m + 1, 1 \leq j \leq m}$ , where the Arnoldi coefficients occupy the positions $i \leq j + 1$ and $h_{i j} : = 0$ for $i > j + 1$ . Then:

$v_{1}, \dots, v_{m}$ are orthonormal;
$span {v_{1}, \dots, v_{m}} = K_{m} (A, b)$ ;
${\overset{ˉ}{H}}_{m}$ has the rectangular upper-Hessenberg zero pattern $h_{i j} = 0$ for $i > j + 1$ ;
$A Q_{m} = Q_{m + 1} {\overset{ˉ}{H}}_{m}$ .

Facts & Assumptions

Given: A square matrix $A$ over $R$ or $C$ , a nonzero start vector $b$ of matching size, an integer $m \geq 1$ , and an Arnoldi run through step $m$ with no breakdown.

[F1]

In Arnoldi, each step defines $w_{j} = A v_{j} - \sum_{i = 1}^{j} h_{i j} v_{i}$ with $h_{i j} = ⟨ A v_{j}, v_{i} ⟩$ , and when $h_{j + 1, j} = ∥ w_{j} ∥ \neq 0$ one sets $v_{j + 1} = w_{j} / h_{j + 1, j}$ (The Arnoldi process for building an orthonormal basis of a Krylov subspace).

[F2]

For $m \geq 1$ , one has $K_{m} (A, b) = span {b, A b, \dots, A^{m - 1} b}$ (The Krylov subspace $K_{m} (A, b) = span {b, A b, \dots, A^{m - 1} b}$ ).

[F3]

The square-matrix upper-Hessenberg condition is the zero pattern $h_{i j} = 0$ for $i > j + 1$ (Upper Hessenberg matrices and real symmetric tridiagonal matrices).

Proof

technique · direct

1.1F1algebra

By construction in [F1], the vector $w_{j}$ is orthogonal to each $v_{i}$ for $1 \leq i \leq j$ , because $h_{i j} = ⟨ A v_{j}, v_{i} ⟩$ subtracts exactly the orthogonal projection of $A v_{j}$ onto $v_{i}$ . Since there is no breakdown, $w_{j} \neq 0$ , so $v_{j + 1} = w_{j} / ∥ w_{j} ∥$ is a unit vector orthogonal to $v_{1}, \dots, v_{j}$ . Starting from the unit vector $v_{1} = b / ∥ b ∥$ , induction gives orthonormality of $v_{1}, \dots, v_{m}$ .

1.2F1F2algebra

Again by [F1], each $v_{j + 1}$ is a linear combination of $A v_{j}, v_{1}, \dots, v_{j}$ . Induction using [F2] therefore gives $v_{i} \in K_{i} (A, b) \subseteq K_{m} (A, b)$ for $i \leq m$ . Conversely, $A v_{j} = \sum_{i = 1}^{j + 1} h_{i j} v_{i}$ lies in $span {v_{1}, \dots, v_{j + 1}}$ , and induction from $v_{1} = b / ∥ b ∥$ shows that $b, A b, \dots, A^{m - 1} b$ all lie in $span {v_{1}, \dots, v_{m}}$ . By [F2], the two spans are equal.

2.1F1F3algebra∎

For each column $j$ , the Arnoldi relation from [F1] involves only $v_{1}, \dots, v_{j + 1}$ . By the definition of ${\overset{ˉ}{H}}_{m}$ in the Statement, its remaining entries satisfy $h_{i j} = 0$ for $i > j + 1$ , the same zero pattern as the square upper-Hessenberg condition [F3]. The column relations assemble exactly into $A Q_{m} = Q_{m + 1} {\overset{ˉ}{H}}_{m}$ .

Depends on

Used by

Dependency tree · two levels

6 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

Yousef Saad, Iterative Methods for Sparse Linear Systems — lecture notes on Arnoldi's method (standard reference, not scraped)
Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra (standard reference, not scraped)