= Solution
For a nonzero vector $v\in\mathbb R^n$, a <Householder reflection> is
$$
H=I-2\frac{vv^T}{v^Tv}.
$$
It is immediately <symmetric matrix>[symmetric]. If $P=vv^T/(v^Tv)$, then $P^2=P$, so
$$
H^TH=H^2=(I-2P)^2=I.
$$
Hence $H$ is also an <orthogonal matrix>, with $H^{-1}=H$.
The <similarity transformation> can be expanded as
$$
HAH
=A-2P A-2A P+4PAP.
$$
Computing $v^TA$, $Av$, and the scalar $v^TAv$ costs $O(n^2)$ <arithmetic operation>[arithmetic operations], after which the remaining updates are <outer product>[outer products] and scalar multiples, also costing $O(n^2)$. Thus $HAH^{-1}$ can be formed in $O(n^2)$ operations rather than by two general $O(n^3)$ <matrix multiplication>[matrix multiplications].
Back to article page
