[proofplan]
We show that CG terminates after at most $s$ iterations, where $s$ is the number of distinct eigenvalues of $A$. By the [Properties of the Conjugate Gradient Method](/theorems/1400), the mutually orthogonal residuals $r^{(0)}, r^{(1)}, \ldots$ all lie in $K_n(A, r^{(0)})$. We bound the dimension of this Krylov subspace by expanding $r^{(0)}$ in the eigenbasis and grouping by distinct eigenvalue, showing $\dim K_n(A, r^{(0)}) \leq s$. Since there can be at most $s$ mutually orthogonal nonzero vectors in an $s$-dimensional subspace, the iteration must produce $r^{(k)} = 0$ for some $k \leq s$.
[/proofplan]
[step:Bound $\dim K_n(A, r^{(0)}) \leq s$ by expanding $r^{(0)}$ in the eigenbasis and grouping by distinct eigenvalue]
Since $A \in \mathbb{R}^{n \times n}$ is symmetric positive definite, it is diagonalisable with an orthonormal eigenbasis $u_1, \ldots, u_n$ and positive eigenvalues $\lambda_1, \ldots, \lambda_n$. Let $\lambda_{\nu_1}, \ldots, \lambda_{\nu_s}$ denote the $s$ distinct eigenvalues. Expand $r^{(0)}$ in this eigenbasis:
\begin{align*}
r^{(0)} = \sum_{i=1}^{n} a_i u_i.
\end{align*}
For each distinct eigenvalue $\lambda_{\nu_j}$ ($j = 1, \ldots, s$), define the grouped component:
\begin{align*}
w_j := \sum_{\{i : \lambda_i = \lambda_{\nu_j}\}} a_i u_i.
\end{align*}
Then $r^{(0)} = \sum_{j=1}^{s} w_j$. Since $Au_i = \lambda_i u_i$, applying $A^k$ to $r^{(0)}$ gives:
\begin{align*}
A^k r^{(0)} = \sum_{i=1}^{n} \lambda_i^k a_i u_i = \sum_{j=1}^{s} \lambda_{\nu_j}^k w_j.
\end{align*}
Therefore every vector $A^k r^{(0)}$ lies in $\operatorname{span}\{w_1, \ldots, w_s\}$, and consequently:
\begin{align*}
K_n(A, r^{(0)}) = \operatorname{span}\{r^{(0)}, Ar^{(0)}, \ldots, A^{n-1}r^{(0)}\} \subset \operatorname{span}\{w_1, \ldots, w_s\}.
\end{align*}
Hence $\dim K_n(A, r^{(0)}) \leq s$.
[guided]
The key observation is that grouping eigenvectors by their eigenvalue collapses the $n$-dimensional eigenbasis into at most $s$ directions. Even though $A$ has $n$ eigenvectors, eigenvectors sharing the same eigenvalue produce the same scaling under powers of $A$: $A^k u_i = \lambda_i^k u_i$. So $A^k$ cannot distinguish between eigenvectors with the same eigenvalue. This means $A^k r^{(0)} = \sum_{j=1}^{s} \lambda_{\nu_j}^k w_j$ is always a linear combination of only $s$ vectors $w_1, \ldots, w_s$.
For example, if $A = I$ (so $s = 1$, all eigenvalues equal $1$), then $K_n(I, r^{(0)}) = \operatorname{span}\{r^{(0)}\}$, which is $1$-dimensional. CG converges in one iteration, as expected.
Note that the dimension could be strictly less than $s$ if $r^{(0)}$ happens to be orthogonal to the eigenspace of some eigenvalue (i.e., $w_j = 0$ for some $j$). In the generic case where $r^{(0)}$ has components along all eigenspaces, the dimension is exactly $s$.
[/guided]
[/step]
[step:Conclude termination from mutual orthogonality of residuals in a finite-dimensional subspace]
By the [Properties of the Conjugate Gradient Method](/theorems/1400), the residuals $r^{(0)}, r^{(1)}, \ldots$ are mutually orthogonal: $\langle r^{(i)}, r^{(j)} \rangle = 0$ for $i \neq j$. Moreover, each $r^{(k)}$ lies in $K_{k+1}(A, r^{(0)}) \subset K_n(A, r^{(0)})$, which has dimension at most $s$ by the previous step.
In a subspace of dimension at most $s$, any set of mutually orthogonal nonzero vectors has at most $s$ elements. Therefore, among $r^{(0)}, r^{(1)}, \ldots, r^{(s)}$, at least one must be the zero vector. Since $r^{(k)} = 0$ implies $r^{(\ell)} = 0$ for all $\ell \geq k$ (the iteration has converged), there exists $k \leq s$ such that $r^{(k)} = 0$, i.e., $x^{(k)} = A^{-1}b$.
[/step]
