Past exam of the mathematics course of the University of Cambridge / 2025 / ib / Paper 1 / 17A (Numerical Analysis)

For a unit vector $v$, a Householder reflection is $H=I-2v{v}^T$. Clearly $H^T=H$, and $H^{T}H=(I-2v{v}^T{)}^2=I$.

The vector $v$ has eigenvalue $-1$, while every vector in $v^{\perp }$ has eigenvalue $1$. Their multiplicities are one and $n-1$, respectively.

At step $k$, choose a Householder reflection acting only on coordinates $k,\dots ,n$ that maps the trailing part of column $k$ to a multiple of the first coordinate in that block. It zeros every entry below the diagonal without changing earlier columns. Induction produces $H_n\cdots H_{1}A=R$ upper triangular.

For symmetric $A$, apply at stage $k$ the same reflection on both sides, choosing it to zero entries below the first subdiagonal in column $k$. Orthogonal similarity preserves symmetry, so the corresponding row entries vanish too and previous zeros remain. After finitely many stages $QA{Q}^T$ is symmetric tridiagonal. Constructing each reflector uses only arithmetic and one square root.