= Solution
Starting with $A_1=A$, for $k=1,\ldots,n-2$ choose a <Householder reflection> $H_k$ that acts only on coordinates $k+1,\ldots,n$ and maps the tail of column $k$,
$$
(A_k)_{k+1:n,k},
$$
to a multiple of its first coordinate vector. Set
$$
A_{k+1}=H_kA_kH_k.
$$
This zeros all entries in column $k$ below its first subdiagonal. Because $H_k$ fixes the first $k$ coordinates, it preserves the zeros created in earlier columns. After $n-2$ steps,
$$
T=A_{n-1}
$$
is an <upper Hessenberg matrix>.
Each $H_k$ is <orthogonal matrix>[orthogonal] and symmetric. If
$$
Q=H_{n-2}\cdots H_1,
$$
then $Q$ is orthogonal and
$$
\boxed{T=QAQ^T}.
$$
Part (a) shows that each similarity update costs $O(n^2)$ arithmetic operations, and there are $O(n)$ updates. The total cost is therefore
$$
\boxed{O(n^3)}.
$$
Back to article page
