Past exam of the Probability, statistics and options II course of the University of Oxford / 2009 / P / P4

Set $P=v{v}^T/(v^{T}v)$. Since $v\ne 0$, it is well defined, symmetric and idempotent: $P^T=P$, $P^2=P$. Therefore $H_{v,\alpha }=I-\alpha P$ is symmetric, andBecause $P\ne 0$, this equals $I$ exactly when $\alpha (\alpha -2)=0$. Hence $\boxed{H_{v,\alpha }\text{ orthogonal}⟺\alpha \in \{0,2\}}$.

If $x\in S_v$, then $v^{T}x=0$ and $Px=0$, so $\boxed{H_{v}x=x}$. For arbitrary $x$, $v^{T}P=v^T$, givingThus the Householder map fixes the hyperplane orthogonal to $v$ and reverses the component in its normal direction: it is a reflection, not merely an arbitrary orthogonal map.

Choose $c=-{\mathrm{sgn}}_{+}(x_1)\Vert x\Vert$, with ${\mathrm{sgn}}_{+}(0)=1$, and put $v=x-c{e}_1$. The opposite sign choice guarantees $v\ne 0$, even if $x$ is already parallel to $e_1$. Since $c^2=\Vert x{\Vert }^2$,Consequently $H_{v}x=x-2v(v^{T}x)/(v^{T}v)=x-v$, yieldingThe sign choice also avoids cancellation in constructing $v$ numerically.

Proceed column by column. At stage $j=1,\dots ,n-2$, consider the entries below the diagonal in column $j$, indexed $j+1,\dots ,n$. If this tail is nonzero, part (c) provides a Householder matrix sending it to a multiple of its first coordinate vector. Embed this matrix as an orthogonal matrix acting identically on coordinates $1,\dots ,j$, and apply the similarity transformation $A\mapsto Q_j^{T}A{Q}_j$. The tail's entries below row $j+1$ become zero. Symmetry is preserved, so the corresponding entries in row $j$ vanish too. If the tail is already zero, use the identity transformation.

Earlier reduced columns remain unchanged in their required zero positions: all their entries in the newly mixed tail coordinates were already zero, and the first $j$ coordinates are fixed. Thus each stage preserves the previous zeros while creating the next ones. After $n-2$ stages, all entries at distance greater than one from the diagonal vanish. With the product $Q=Q_1\cdots Q_{n-2}$ one has $Q^{T}Q=I$ andThis constructive reduction uses only reflections on successive trailing subspaces.