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

For a nonzero vector $v\in {\mathbb{R}}^n$, a Householder reflection isIt is immediately symmetric. If $P=v{v}^T/(v^{T}v)$, then $P^2=P$, soHence $H$ is also an orthogonal matrix, with $H^{-1}=H$.

The similarity transformation can be expanded asComputing $v^{T}A$, $Av$, and the scalar $v^{T}Av$ costs $O(n^2)$ arithmetic operations, after which the remaining updates are outer products and scalar multiples, also costing $O(n^2)$. Thus $HA{H}^{-1}$ can be formed in $O(n^2)$ operations rather than by two general $O(n^3)$ matrix multiplications.