= Solution
An <orthogonal similarity transformation> is $H=Q^TAQ$ with $Q^TQ=I$. An <upper Hessenberg matrix> has $H_{ij}=0$ whenever $i>j+1$; its first subdiagonal may be nonzero.
At step $k=1,\ldots,m-2$, choose a <Householder reflector> $Q_k=\operatorname{diag}(I_k,\widehat Q_k)$ whose trailing block sends the current column segment in rows $k+1,\ldots,m$ to a multiple of its first coordinate. The left multiplication zeros positions $(k+2,k),\ldots,(m,k)$. Apply the matching right multiplication to retain similarity: $A\leftarrow Q_k^TAQ_k$. Since $Q_k$ acts only on rows and columns $k+1,\ldots,m$, earlier Hessenberg zeros are preserved. Finally $Q=Q_1\cdots Q_{m-2}$ gives $H=Q^TAQ$.
Each reflector is applied through a rank-one update, costing $O(m^2)$ rather than a full matrix multiplication. Across $m-2$ steps, the <Hessenberg reduction> costs $O(m^3)$.
Back to article page
