Past exam of the mathematics course of the University of Cambridge / 2005 / ii / Paper 4 / 39A (Numerical Analysis)

At step $k=1,\dots ,n-2$, isolate the active column tail $a=A_{k+1:n,k}$. If its subtail is already zero, no reflection is needed. Otherwise choose a Householder reflection $H=I-2v{v}^T/(v^{T}v)$ on the active coordinates such that $Ha$ has only its first component nonzero. A cancellation-resistant choice is $v=a+\mathrm{sgn}(a_1)\Vert a\Vert e_1$, with an arbitrary positive sign if $a_1=0$. Embed $H$ as $P=\mathrm{diag}(I_k,H)$ and replace $A$ by $P^{T}AP$. Previous reduced columns are untouched, and column $k$ now has no entries below the first subdiagonal.

Similarity by an orthogonal matrix preserves skew symmetry. Consequently an upper-Hessenberg result also has zeros above the first superdiagonal, so it is tridiagonal with zero diagonal and opposite-sign corresponding off-diagonal entries.

For the active skew-symmetric block $D$, compute $w=2Dv/(v^{T}v)$. Because $v^{T}Dv=0$, expanding the two-sided reflection simplifies toStore and update just one triangle, obtain the other by negation, and keep the diagonal exactly zero. Matrix-vector multiplication can likewise use each stored entry once to contribute to two output coordinates. This is skew-symmetric Householder tridiagonalization; there is no need for two dense matrix-matrix multiplications.

Let the active block have size $m$. Using a stored skew triangle, the product $Dv$ costs $m(m-1)$ scalar multiplications: two for each unordered off-diagonal pair. Updating its stored triangle with $v{w}^T-w{v}^T$ costs another $m(m-1)$ products. Reflector construction, scalings and the active column take only $O(m)$ additional products. Summing over $m=n-1,\dots ,2$ gives

For a symmetric block, an optimized matrix-vector calculation costs $m^2$ products, and the symmetric rank-two update of one triangle costs $m(m+1)$ products. The additional scalar $v^{T}Dv$ and its correction to the update vector cost only $O(m)$ per step. ThusThe leading terms are the same under the requested product-count convention. Skew symmetry removes the diagonal work and the scalar correction, giving lower-order savings, not a factor-of-two leading advantage over an already symmetry-aware implementation. Counting additions as well would change the reported flop constants; it is not the convention requested here.