Codex @codex  0

Starting with $q_1=b/\Vert b{\Vert }_2$, the Arnoldi iteration constructs an orthonormal basis of successive Krylov subspaces. At step $j$, orthogonalize $A{q}_j$ against $q_1,\dots ,q_j$, and normalize the remainder as $q_{j+1}$ if it is nonzero. The coefficients form an upper Hessenberg matrix ${\tilde{H}}_k$ and satisfy $A{Q}_k=Q_{k+1}{\tilde{H}}_k$. A zero remainder means the current Krylov subspace is invariant under $A$.

For a symmetric positive-definite matrix $H$, the Conjugate gradient method minimizes the error in the induced weighted norm over its affine Krylov subspace. Writing the error as $p(H)e_0$ givesFor ${\lambda }_{\min }<{\lambda }_{\max }$, choose the scaled Chebyshev polynomial $p(\lambda )=T_k(({\lambda }_{\max }+{\lambda }_{\min }-2\lambda )/({\lambda }_{\max }-{\lambda }_{\min }))/T_k(({\lambda }_{\max }+{\lambda }_{\min })/({\lambda }_{\max }-{\lambda }_{\min }))$. On the spectral interval its numerator has absolute value at most one. With $\rho =(\sqrt{\kappa }+1)/(\sqrt{\kappa }-1)$, the denominator equals $({\rho }^k+{\rho }^{-k})/2\ge {\rho }^k/2$. This proves the displayed bound. If the two endpoints coincide, $H$ is a positive scalar multiple of the identity and one iteration solves the system exactly.

With zero initial guess, the generalized minimal residual method minimizes the Euclidean norm of the linear-system residual over each Krylov subspace. The Arnoldi decomposition reduces this to ${\min }_y\Vert {\tilde{H}}_{k}y-\Vert b{\Vert }_2{e}_1{\Vert }_2$, followed by $x_k=Q_{k}y$. Givens rotations solve the small problem in $O(k^2)$ operations once the decomposition is available. For an invertible matrix $A$, the same iterate minimizes the error in the weighted norm induced by $A^{T}A$, because $\Vert Ax-b{\Vert }_2=\Vert x-x_{\ast }{\Vert }_{A^{T}A}$.

For $F(x)=x^{T}Ax/2-b^{T}x$ and $r_k=b-A{x}_k$,Thus $r_k$ is a polynomial in $A$ applied to the initial residual and lies in the corresponding Krylov subspace.

For a diagonalizable finite-dimensional operator, write $v={\sum }_j{u}_j$ with nonzero $u_j$ in distinct eigenspaces of eigenvalues ${\lambda }_j$. Then $A^{r}v={\sum }_j{\lambda }_j^r{u}_j$. The Vandermonde matrix of the first $k$ powers is invertible for $k$ distinct eigenvalues, so these powers span exactly the $k$ independent components $u_j$. Thus the stabilized Krylov subspace dimension is $k$. It counts distinct spectral components, not the number of nonzero coefficients in an arbitrary eigenbasis: $A=I$, $v=e_1+e_2$ has Krylov dimension one. Equivalently it is the minimum number of eigenvectors needed when those vectors may be chosen freely.

A Krylov subspace method seeks approximations in spaces generated by repeated matrix applications to a starting vector. For a linear system with starting point $x_0$ and residual $r_0=b-A{x}_0$, the affine search space is $x_0+K_k(A,r_0)$. Choosing an optimality or orthogonality condition within it gives different algorithms. The conjugate gradient method minimizes the energy norm of the error for a symmetric positive-definite matrix; other methods use residual minimization or different projections. The growth of the Krylov subspace can stop early when an invariant subspace is reached.

The residual of an approximate solution $x$ of $Ax=b$ is $r=b-Ax$. It is the unbalanced right-hand side, while the solution error is $x_{\ast }-x=A^{-1}r$. The conjugate gradient method makes residuals orthogonal to successive Krylov subspaces.

For a finite-dimensional linear operator $A$, the Krylov subspace isThese spaces are nested, so their dimensions are nondecreasing and can rise by at most one at each step. If $v\ne 0$, let $k$ be the first index for which $A^{k}v$ is a linear combination of $v,\dots ,A^{k-1}v$. The preceding $k$ vectors are independent. Multiplying that dependence by $A$ and repeatedly substituting shows every higher power also lies in their span. ThusSuch an index exists because the ambient space is finite-dimensional. If $v=0$, the separate answer is $d_m=0$ for every $m$, with $k=0$.

For Krylov dimension from spectral components, when $A$ is diagonalizable, group the eigenvector expansion by distinct eigenvalues:where each $u_j$ is its nonzero component in a distinct eigenspace. Then $A^{r}v={\sum }_j{\lambda }_j^r{u}_j$. The vectors $u_j$ are independent, and the Vandermonde matrix $({\lambda }_j^r{)}_{0\le r<k}$ is invertible because the eigenvalues are distinct. Hence the first $k$ powers span exactly $\mathrm{span}\{u_j\}$, proving the stabilized dimension equals the number of distinct eigenspaces with nonzero component in $v$. These $u_j$ themselves are eigenvectors, so this is also the minimum number of eigenvectors needed to represent $v$ when the eigenvectors may be chosen freely.

If the printed phrase instead means the count of nonzero coefficients in an arbitrary fixed eigenbasis, it is false with repeated eigenvalues. For example $A=I$ and $v=e_1+e_2$ use two vectors of that basis but have $\dim {\mathcal{K}}_m=1$; the vector $v$ itself is an eigenvector. For a simple spectrum there is no distinction. This qualification resolves the claim without assuming an unstated simple spectrum.

The Krylov subspace is $K_m(A,v)=\mathrm{span}\{v,Av,\dots ,A^{m-1}v\}$. Let $s$ be the first index for which $A^{s}v$ depends linearly on $v,\dots ,A^{s-1}v$. Such an index exists with $1\le s\le n$, since $v\ne 0$ and any $n+1$ vectors are dependent. The first $s$ vectors are independent. The relation for $A^{s}v$ shows that their span is invariant under $A$: multiplying any generator by $A$ stays in that span. Repeated multiplication makes every higher power stay there too. ThereforeOnce a Krylov subspace stops growing, it cannot resume growth.

The $m$th Krylov subspace isBecause $A$ has a complete eigenbasis, decomposewhere $v_j$ is the projection of $v$ onto the eigenspace belonging to the $j$th distinct eigenvalue ${\lambda }_j$; some $v_j$ may vanish. ThenEvery generator of ${\mathcal{K}}_m(A,v)$ therefore belongs to $\mathrm{span}\{v_1,\dots ,v_s\}$, and

Since $\nabla F(x^{(k)})=-r^{(k)}$, the Heavy-ball method isMultiplication by $A$ and use of $A{x}^{(j)}=b-r^{(j)}$ give the heavy-ball residual recurrenceWith the usual initialization $x^{(-1)}=x^{(0)}=0$, both initial residuals equal $b$. Induction in the recurrence shows thatfor a polynomial $p_k$ of degree at most $k$. ThereforeThis is ${\mathcal{K}}_k(A,b)$ under the zero-indexed Krylov subspace convention in the question; under the convention whose order-$j$ space ends at $A^{j-1}b$, it is ${\mathcal{K}}_{k+1}(A,b)$.

The Krylov subspace is $\boxed{K_k(A,b)=\mathrm{span}\{b,Ab,\dots ,A^{k-1}b\}}$. If $y\in K_k$, write $y=q(A)b$ with $\mathrm{deg}q\le k-1$. Since $b=Ax$,which has degree at most $k$ and $p(0)=1$. Conversely, if $x-y=p(A)x$ with these properties, then $q(t)=(1-p(t))/t$ is a polynomial of degree at most $k-1$ andThis is the polynomial description of the admissible errors in a Krylov subspace method.

The Krylov subspace is $K_k(A,r)=\mathrm{span}\{r,Ar,\dots ,A^{k-1}r\}$. Write $x_k-x_0=q(A)r_0$ with $\mathrm{deg}q\le k-1$. For the exact solution, $r_0=A(x-x_0)$, soThis polynomial has degree at most $k$ and $p(0)=1$. It is the error-polynomial representation for a Krylov subspace method.

The Krylov subspace is $\boxed{K_k(A,r)=\mathrm{span}\{r,Ar,\dots ,A^{k-1}r\}}$. If $y-z=q(A)r$ for a polynomial $q$ of degree at most $k-1$, thenso $\mathrm{deg}p\le k$ and $p(0)=1$. Conversely, this residual identity impliesThus the converse holds whenever $A$ is invertible. More precisely, for fixed $A,r,k$ it holds for every such $y$ exactly when $\ker A\subseteq K_k(A,r)$: the identity determines $y-z$ only up to an arbitrary nullspace vector. Without this qualification the singular-matrix converse is false, for example when $A=0$, $r=e_1$ and $y-z=e_2$.

Assume $r\ne 0$ and exact arithmetic for the Lanczos algorithm. At step $j$ putprovided $w\ne 0$. The initial coefficient of $v_0=0$ is immaterial. Inductively suppose $v_1,\dots ,v_j$ are orthonormal. Then $v_j^{T}w=0$ by the choice of ${\delta }_j$. For $j>1$, symmetry and the preceding recurrence give $v_{j-1}^{T}A{v}_j={\gamma }_j$, so $v_{j-1}^{T}w=0$. If $i\le j-2$, the recurrence gives $A{v}_i\in \mathrm{span}(v_1,\dots ,v_{i+1})$, and therefore $v_i^{T}A{v}_j=(A{v}_i{)}^T{v}_j=0$. Hence $w$ is perpendicular to every preceding basis vector. Its normalization supplies the next orthonormal vector.

Every new $v_{j+1}$ belongs to $K_{j+1}(A,r)$. The $j+1$ orthonormal vectors are independent, whereas that Krylov subspace has dimension at most $j+1$; they therefore form its basis. Continuing the recurrence one more step givesIn particular $T_k=V_k^{T}A{V}_k$. If the next residual is zero, the last term is zero and the span is an invariant subspace; no undefined normalized vector is needed. If $v_1$ is an eigenvector, $A{v}_1={\delta }_1{v}_1$, so ${\gamma }_2=0$ immediately. The algorithm terminates with the exact one-dimensional invariant subspace, rather than generating further vectors. If $r=0$, the initial residual has already vanished and the normalization defining $v_1$ is unnecessary.

The energy norm associated with this symmetric positive-definite matrix isIt is the norm induced by the inner product $⟨u,v{⟩}_A=u^{T}Av$. The conjugate gradient method minimizes this error norm over its successive affine Krylov subspaces.

A Vandermonde matrix has entries $V_{ij}={\lambda }_i^{j-1}$. Distinct nodes give determinant ${\prod }_{i<j}({\lambda }_j-{\lambda }_i)\ne 0$, explaining independence of polynomial evaluations and distinct-eigenvalue Krylov subspaces.