CorollaryStatement: 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.

If $A$ is invertible, the exact solution of $A x = b$ lies in the Krylov space at the grade

Statement

Let $A$ be invertible, let $b$ be a vector, and let $ν = ν (A, b)$ . If $x_{*}$ is the exact solution of $A x = b$ , then

$x_{*} \in K_{ν} (A, b) .$

Facts & Assumptions

Given: An invertible matrix $A$ , a vector $b$ , its grade $ν = ν (A, b)$ , and the exact solution $x_{*} = A^{- 1} b$ .

[F1]

The relative minimal polynomial $q_{A, b}$ is monic of degree $ν$ and satisfies $q_{A, b} (A) b = 0$ (The grade of a start vector and its relative minimal polynomial).

[L1]

For every $m \geq ν$ , one has $K_{m} (A, b) = K_{ν} (A, b)$ (The dimensions of the Krylov spaces grow by one until the grade and then stabilize).

Proof

technique · direct

1.1

If $b = 0$ , then $x_{*} = 0 \in K_{0} (A, b) = K_{ν} (A, b)$ . Assume now that $b \neq 0$ . Write $q_{A, b} (z) = a_{0} + a_{1} z + \dots + a_{ν - 1} z^{ν - 1} + z^{ν}$ . The constant term $a_{0}$ is nonzero, because $a_{0} = 0$ would give $q_{A, b} (z) = z r (z)$ and then $0 = q_{A, b} (A) b = A r (A) b$ , so invertibility of $A$ would imply $r (A) b = 0$ with $\deg r = ν - 1$ , contradicting [F1].

givenF1algebra

2.1

From $q_{A, b} (A) b = 0$ we obtain $a_{0} b + A (a_{1} I + \dots + a_{ν - 1} A^{ν - 2} + A^{ν - 1}) b = 0.$ Multiplying by $A^{- 1}$ and dividing by $a_{0}$ yields $x_{*} = A^{- 1} b = - a_{0}^{- 1} (a_{1} I + \dots + a_{ν - 1} A^{ν - 2} + A^{ν - 1}) b,$ so $x_{*} \in K_{ν} (A, b)$ . The inclusion is already enough, and [L1] shows it persists in every later Krylov space.

F1L1algebra∎

Depends on

Used by

In exact arithmetic, unrestarted GMRES terminates no later than the relative grade Theorem

Dependency tree · two levels

7 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, CSCI 8314 Set 13: Krylov subspace methods; Introduction; Krylov subspaces; Gram-Schmidt process (review); The Arnoldi process; FOM and GMRES (standard reference, not scraped)

If AA is invertible, the exact solution of Ax=bAx=b lies in the Krylov space at the grade