Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2010 / A / 2 / b / Solution

An orthogonal similarity transformation is $H=Q^{T}AQ$ with $Q^{T}Q=I$. An upper Hessenberg matrix has $H_{ij}=0$ whenever $i>j+1$; its first subdiagonal may be nonzero.

At step $k=1,\dots ,m-2$, choose a Householder reflector $Q_k=\mathrm{diag}(I_k,{\hat{Q}}_k)$ whose trailing block sends the current column segment in rows $k+1,\dots ,m$ to a multiple of its first coordinate. The left multiplication zeros positions $(k+2,k),\dots ,(m,k)$. Apply the matching right multiplication to retain similarity: $A\leftarrow Q_k^{T}A{Q}_k$. Since $Q_k$ acts only on rows and columns $k+1,\dots ,m$, earlier Hessenberg zeros are preserved. Finally $Q=Q_1\cdots Q_{m-2}$ gives $H=Q^{T}AQ$.

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)$.