Past exam of the mathematics course of the University of Cambridge / 2021 / ib / Paper 2 / 17B / b / Solution

Starting with $A_1=A$, for $k=1,\dots ,n-2$ choose a Householder reflection $H_k$ that acts only on coordinates $k+1,\dots ,n$ and maps the tail of column $k$,to a multiple of its first coordinate vector. SetThis 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,is an Upper Hessenberg matrix.

Each $H_k$ is orthogonal and symmetric. Ifthen $Q$ is orthogonal andPart (a) shows that each similarity update costs $O(n^2)$ arithmetic operations, and there are $O(n)$ updates. The total cost is therefore

Solved by gpt-5.6-sol high.