[proofplan] We show that after $k$ CG iterations, $\|\mathbf{e}^{(k)}\|_A = \min_{P_k} \|P_k(A)\mathbf{e}^{(0)}\|_A$ where the minimum is over polynomials $P_k$ of degree $\leq k$ with $P_k(0) = 1$. The proof has two parts. First, we show that $\mathbf{e}^{(k)}$ minimizes the $A$-norm of $\mathbf{e}^{(0)} - \mathbf{v}$ over $\mathbf{v} \in K_k(A, \mathbf{r}^{(0)})$, using the $A$-orthogonality property from the conjugate direction theory. Second, we identify $K_k(A, \mathbf{r}^{(0)})$ with $\{(I - P_k(A))\mathbf{e}^{(0)} : P_k(0) = 1, \deg P_k \leq k\}$ via the relation $\mathbf{r}^{(0)} = A\mathbf{e}^{(0)}$, establishing the polynomial characterization. [/proofplan]

[step:Show $\mathbf{e}^{(k)}$ is the $A$-orthogonal projection of $\mathbf{e}^{(0)}$ away from $K_k(A, \mathbf{r}^{(0)})$]From the [Error Projection Along Search Direction](/theorems/1398), the error update satisfies $\mathbf{e}^{(j+1)} = \mathbf{e}^{(j)} - \alpha_j \mathbf{d}^{(j)}$ for each $j = 0, \ldots, k-1$. Summing these telescopically: \begin{align*} \mathbf{e}^{(0)} - \mathbf{e}^{(k)} = \sum_{j=0}^{k-1} \alpha_j \mathbf{d}^{(j)} \in \operatorname{span}\{\mathbf{d}^{(0)}, \ldots, \mathbf{d}^{(k-1)}\}. \end{align*} By the [Properties of the Conjugate Gradient Method](/theorems/1400), $\operatorname{span}\{\mathbf{d}^{(0)}, \ldots, \mathbf{d}^{(k-1)}\} = K_k(A, \mathbf{r}^{(0)})$. Moreover, by the [Finite Termination of Conjugate Direction Methods](/theorems/1399), $\langle \mathbf{e}^{(k)}, \mathbf{d}^{(j)} \rangle_A = 0$ for all $j = 0, \ldots, k-1$, which means $\mathbf{e}^{(k)}$ is $A$-orthogonal to $K_k(A, \mathbf{r}^{(0)})$. This is exactly the characterisation of the $A$-orthogonal projection: $\mathbf{e}^{(0)} - \mathbf{e}^{(k)} \in K_k(A, \mathbf{r}^{(0)})$ and $\mathbf{e}^{(k)} \perp_A K_k(A, \mathbf{r}^{(0)})$. By the Pythagorean theorem in the $A$-inner product, for any $\mathbf{v} \in K_k(A, \mathbf{r}^{(0)})$: \begin{align*} \|\mathbf{e}^{(0)} - \mathbf{v}\|_A^2 = \|\mathbf{e}^{(k)}\|_A^2 + \|(\mathbf{e}^{(0)} - \mathbf{e}^{(k)}) - \mathbf{v}\|_A^2 \geq \|\mathbf{e}^{(k)}\|_A^2, \end{align*} with equality iff $\mathbf{v} = \mathbf{e}^{(0)} - \mathbf{e}^{(k)}$. Therefore: \begin{align*} \|\mathbf{e}^{(k)}\|_A = \min_{\mathbf{v} \in K_k(A, \mathbf{r}^{(0)})} \|\mathbf{e}^{(0)} - \mathbf{v}\|_A. \end{align*}[/step]

[guided]The Pythagorean theorem applies because $\mathbf{e}^{(k)}$ and $(\mathbf{e}^{(0)} - \mathbf{e}^{(k)}) - \mathbf{v}$ are $A$-orthogonal: since $(\mathbf{e}^{(0)} - \mathbf{e}^{(k)}) - \mathbf{v} \in K_k(A, \mathbf{r}^{(0)})$ (as a difference of two elements of $K_k$), and $\mathbf{e}^{(k)} \perp_A K_k(A, \mathbf{r}^{(0)})$. This shows that CG solves a best approximation problem: among all corrections $\mathbf{v}$ in the Krylov subspace, CG picks the one that minimizes the $A$-norm of the resulting error. The $A$-orthogonality condition is the necessary and sufficient condition for this optimality.[/guided]

[step:Identify $K_k(A, \mathbf{r}^{(0)})$ with the set $\{(I - P_k(A))\mathbf{e}^{(0)} : P_k(0) = 1, \deg P_k \leq k\}$]Since $\mathbf{r}^{(0)} = A\mathbf{e}^{(0)}$: \begin{align*} K_k(A, \mathbf{r}^{(0)}) = \operatorname{span}\{A\mathbf{e}^{(0)}, A^2\mathbf{e}^{(0)}, \ldots, A^k\mathbf{e}^{(0)}\}. \end{align*} Any $\mathbf{v} \in K_k(A, \mathbf{r}^{(0)})$ has the form $\mathbf{v} = \sum_{i=1}^{k} c_i A^i \mathbf{e}^{(0)}$ for some coefficients $c_1, \ldots, c_k \in \mathbb{R}$. Therefore: \begin{align*} \mathbf{e}^{(0)} - \mathbf{v} = \mathbf{e}^{(0)} - \sum_{i=1}^{k} c_i A^i \mathbf{e}^{(0)} = \left(I - \sum_{i=1}^{k} c_i A^i\right)\mathbf{e}^{(0)} = P_k(A)\mathbf{e}^{(0)}, \end{align*} where $P_k(t) := 1 - \sum_{i=1}^{k} c_i t^i$ is a polynomial of degree at most $k$ satisfying $P_k(0) = 1$. Conversely, every polynomial $P_k$ of degree $\leq k$ with $P_k(0) = 1$ can be written as $P_k(t) = 1 - \sum_{i=1}^{k} c_i t^i$ for some coefficients $c_i$, so $P_k(A)\mathbf{e}^{(0)} = \mathbf{e}^{(0)} - \mathbf{v}$ with $\mathbf{v} = \sum_{i=1}^{k} c_i A^i \mathbf{e}^{(0)} \in K_k(A, \mathbf{r}^{(0)})$. This establishes a bijection between elements $\mathbf{v} \in K_k(A, \mathbf{r}^{(0)})$ and polynomials $P_k$ of degree $\leq k$ with $P_k(0) = 1$. Combining with the previous step: \begin{align*} \|\mathbf{e}^{(k)}\|_A = \min_{\mathbf{v} \in K_k(A, \mathbf{r}^{(0)})} \|\mathbf{e}^{(0)} - \mathbf{v}\|_A = \min_{\substack{P_k : \deg P_k \leq k \\ P_k(0) = 1}} \|P_k(A)\mathbf{e}^{(0)}\|_A. \end{align*}[/step]

[guided]The constraint $P_k(0) = 1$ comes from the fact that the identity term in $I - \sum c_i A^i$ contributes $1$ at $t = 0$, and the higher-order terms vanish. Geometrically, $P_k(0) = 1$ means the polynomial has no effect on the null space of $A$ — but since $A$ is positive definite, $0$ is not an eigenvalue, so this constraint is really about normalisation. The polynomial minimization framework is powerful because it decouples the problem from the initial error $\mathbf{e}^{(0)}$: we seek a single polynomial $P_k$ that is small on the spectrum of $A$, subject to $P_k(0) = 1$. This is a classical problem in approximation theory, and the Chebyshev polynomials provide the optimal solution (as used in the [Chebyshev Convergence Bound for CG](/theorems/1403)). The bijection between $\mathbf{v} \in K_k$ and polynomials $P_k$ with $P_k(0) = 1$ is central: $\mathbf{v} = (I - P_k(A))\mathbf{e}^{(0)}$ represents the correction applied after $k$ steps, and $P_k(A)\mathbf{e}^{(0)} = \mathbf{e}^{(k)}$ is the remaining error. CG automatically finds the polynomial $P_k$ that minimizes $\|P_k(A)\mathbf{e}^{(0)}\|_A$.[/guided]