= Solution
Let $e_1=(1,0,\ldots,0)^T$. The displayed lower-bidiagonal matrix $Q$ satisfies
$$
A=QQ^T+e_1e_1^T.
$$
Since $P=Q^{-1}$, the <Preconditioned conjugate gradient method> uses
$$
PAP^T
=I+(Pe_1)(Pe_1)^T.
$$
Solving $Qz=e_1$ gives
$$
z=Pe_1=(1,-1,1,-1,\ldots)^T,
\qquad
z^Tz=n.
$$
The rank-one matrix $I+zz^T$ has eigenvalue $1+n$ in the direction $z$ and eigenvalue $1$ on the $(n-1)$-dimensional orthogonal complement of $z$. It therefore has only two distinct eigenvalues. Part (b) gives
$$
\boxed{\text{the preconditioned method terminates after at most two iterations}}.
$$
Back to article page
