[proofplan] We prove by induction on $k$ that $\mathbf{r}^{(k)}$ is orthogonal to $\operatorname{span}\{\mathbf{d}^{(0)}, \ldots, \mathbf{d}^{(k-1)}\}$, using the [Error Projection Along Search Direction](/theorems/1398) theorem as the key tool. The base case $k = 1$ follows directly from that theorem. The inductive step combines the inductive hypothesis ($\mathbf{e}^{(k)}$ is $A$-orthogonal to $\mathbf{d}^{(0)}, \ldots, \mathbf{d}^{(k-1)}$) with the conjugacy of the directions ($\langle \mathbf{d}^{(k)}, \mathbf{d}^{(j)} \rangle_A = 0$ for $j < k$) to show $\langle \mathbf{e}^{(k+1)}, \mathbf{d}^{(j)} \rangle_A = 0$ for all $j \leq k$. After $n$ steps, $\mathbf{e}^{(n)}$ is $A$-orthogonal to all $n$ conjugate directions, which span $\mathbb{R}^n$, forcing $\mathbf{e}^{(n)} = 0$. [/proofplan]

[step:Verify that pairwise conjugate directions form a basis of $\mathbb{R}^n$] The directions $\mathbf{d}^{(0)}, \ldots, \mathbf{d}^{(n-1)}$ are pairwise conjugate with respect to $A$: $\langle \mathbf{d}^{(i)}, \mathbf{d}^{(j)} \rangle_A = 0$ for $i \neq j$. Since $A$ is positive definite, $\langle \cdot, \cdot \rangle_A$ is an inner product on $\mathbb{R}^n$. A set of $n$ mutually orthogonal nonzero vectors in an $n$-dimensional inner product space is linearly independent (if $\sum_i c_i \mathbf{d}^{(i)} = 0$, then taking $\langle \cdot, \mathbf{d}^{(j)} \rangle_A$ gives $c_j \langle \mathbf{d}^{(j)}, \mathbf{d}^{(j)} \rangle_A = 0$, hence $c_j = 0$). Therefore $\{\mathbf{d}^{(0)}, \ldots, \mathbf{d}^{(n-1)}\}$ is a basis of $\mathbb{R}^n$. [/step]

[step:Prove by induction that $\langle \mathbf{e}^{(k)}, \mathbf{d}^{(j)} \rangle_A = 0$ for all $j < k$]**Base case ($k = 1$).** By the [Error Projection Along Search Direction](/theorems/1398), $\langle \mathbf{e}^{(1)}, \mathbf{d}^{(0)} \rangle_A = 0$. Since $\langle \mathbf{r}^{(1)}, \mathbf{d}^{(0)} \rangle = \langle A\mathbf{e}^{(1)}, \mathbf{d}^{(0)} \rangle = \langle \mathbf{e}^{(1)}, \mathbf{d}^{(0)} \rangle_A = 0$, the residual $\mathbf{r}^{(1)}$ is orthogonal to $\mathbf{d}^{(0)}$. **Inductive step.** Assume $\langle \mathbf{e}^{(k)}, \mathbf{d}^{(j)} \rangle_A = 0$ for all $j = 0, \ldots, k-1$. The error recurrence from the [Error Projection Along Search Direction](/theorems/1398) gives: \begin{align*} \mathbf{e}^{(k+1)} = \mathbf{e}^{(k)} - \frac{\langle \mathbf{e}^{(k)}, \mathbf{d}^{(k)} \rangle_A}{\langle \mathbf{d}^{(k)}, \mathbf{d}^{(k)} \rangle_A}\,\mathbf{d}^{(k)}. \end{align*} For $j < k$, take the $A$-inner product with $\mathbf{d}^{(j)}$: \begin{align*} \langle \mathbf{e}^{(k+1)}, \mathbf{d}^{(j)} \rangle_A = \underbrace{\langle \mathbf{e}^{(k)}, \mathbf{d}^{(j)} \rangle_A}_{= 0 \text{ (inductive hypothesis)}} - \frac{\langle \mathbf{e}^{(k)}, \mathbf{d}^{(k)} \rangle_A}{\langle \mathbf{d}^{(k)}, \mathbf{d}^{(k)} \rangle_A}\underbrace{\langle \mathbf{d}^{(k)}, \mathbf{d}^{(j)} \rangle_A}_{= 0 \text{ (conjugacy, } j \neq k)} = 0. \end{align*} For $j = k$, the [Error Projection Along Search Direction](/theorems/1398) directly gives $\langle \mathbf{e}^{(k+1)}, \mathbf{d}^{(k)} \rangle_A = 0$. Therefore $\langle \mathbf{e}^{(k+1)}, \mathbf{d}^{(j)} \rangle_A = 0$ for all $j = 0, \ldots, k$, completing the induction.[/step]

[guided]The inductive step uses two distinct orthogonality properties: 1. **The inductive hypothesis:** $\langle \mathbf{e}^{(k)}, \mathbf{d}^{(j)} \rangle_A = 0$ for $j < k$. This says that the error at step $k$ has already been made $A$-orthogonal to all previous search directions. 2. **Conjugacy of the directions:** $\langle \mathbf{d}^{(k)}, \mathbf{d}^{(j)} \rangle_A = 0$ for $j \neq k$. This is the structural assumption on the search directions. When we expand $\langle \mathbf{e}^{(k+1)}, \mathbf{d}^{(j)} \rangle_A$ for $j < k$, the first term vanishes by (1) and the second by (2). For $j = k$, we use the Error Projection theorem directly. The critical question is: why does the new step (along $\mathbf{d}^{(k)}$) not destroy the $A$-orthogonality to previous directions? The answer is exactly conjugacy: since $\mathbf{d}^{(k)}$ is $A$-orthogonal to $\mathbf{d}^{(0)}, \ldots, \mathbf{d}^{(k-1)}$, adding a multiple of $\mathbf{d}^{(k)}$ to $\mathbf{e}^{(k)}$ does not change the $A$-inner product with any previous direction. Since $\langle \mathbf{r}^{(k)}, \mathbf{d}^{(j)} \rangle = \langle A\mathbf{e}^{(k)}, \mathbf{d}^{(j)} \rangle = \langle \mathbf{e}^{(k)}, \mathbf{d}^{(j)} \rangle_A$, the statement "$\mathbf{r}^{(k)}$ is orthogonal to $\operatorname{span}\{\mathbf{d}^{(0)}, \ldots, \mathbf{d}^{(k-1)}\}$" is equivalent to "$\mathbf{e}^{(k)}$ is $A$-orthogonal to $\operatorname{span}\{\mathbf{d}^{(0)}, \ldots, \mathbf{d}^{(k-1)}\}$".[/guided]

[step:Conclude that $\mathbf{r}^{(n)} = 0$ from $A$-orthogonality to a basis] After $n$ steps, the induction gives $\langle \mathbf{e}^{(n)}, \mathbf{d}^{(j)} \rangle_A = 0$ for all $j = 0, \ldots, n-1$. Since $\{\mathbf{d}^{(0)}, \ldots, \mathbf{d}^{(n-1)}\}$ is a basis of $\mathbb{R}^n$ (established in the first step), the vector $\mathbf{e}^{(n)}$ is $A$-orthogonal to every vector in $\mathbb{R}^n$. In particular, $\langle \mathbf{e}^{(n)}, \mathbf{e}^{(n)} \rangle_A = 0$. Since $A$ is positive definite, $\langle \mathbf{v}, \mathbf{v} \rangle_A = 0$ implies $\mathbf{v} = 0$. Therefore $\mathbf{e}^{(n)} = 0$, which means $\mathbf{x}^{(n)} = \mathbf{x}^*$, and consequently $\mathbf{r}^{(n)} = A\mathbf{e}^{(n)} = 0$. [/step]