Exercise31.1

Show that computing the matrix product \(B=FA\text{,}\) where \(F\) and \(A\) are both \(m\times m\) matrices, using the “usual” algorithm, takes \(\mathcal{O}(m^3)\) operations.

Let \(F\) be the Householder reflector

\begin{equation*} F = I - 2 {v v^\star}, \end{equation*}

where \(v\) is an \(m\)-vector such that \(\|v\|_2=1\text{.}\) Show that computing \(B=FA\) is the same as \(B = A-2v (v^\star A)\text{.}\) How many operations would this require?

in-context