Let $A=\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix}$.
How to transform this matrix with Householder transformations to an upper triangular matrix?
I started like this:
$\alpha_1=$sgn$(0)(0^2+0^2+1^2+0^2)^{\frac{1}{2}}=1$.
So $v_1=\begin{pmatrix} 0\\0\\1\\0 \end{pmatrix}+\begin{pmatrix} 1\\0\\0\\0 \end{pmatrix}=\begin{pmatrix} 1\\0\\1\\0 \end{pmatrix}$
Then $\frac{2vv^T}{v^Tv}=\begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix}$
$Q_1= I-\frac{2vv^T}{v^Tv}=\begin{pmatrix} 0 & 0 & -1 & 0 \\ 0 & 1 & 0 & 0 \\ -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$
So I get:
$Q_1A=\begin{pmatrix} 0 & 0 & -1 & 0 \\ 0 & 1 & 0 & 0 \\ -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix}=\begin{pmatrix} -1 & 0 & -1 \\ 0 & 0 & 1 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$
Then I used the lower-right $(3 \times 2)$-submatrix and I got:
$\alpha_2=$sgn$(0)(0^2+(-1)^2+0^2)^{\frac{1}{2}}=1$
$v_2=\begin{pmatrix} 0\\-1\\0 \end{pmatrix}+\begin{pmatrix} 1\\0\\0 \end{pmatrix}=\begin{pmatrix} 1\\-1\\0 \end{pmatrix}$
$Q_2=\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$
and $Q_2Q_1A=\begin{pmatrix} -1 & 0 & -1 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{pmatrix}$
How to continue from here? I'm not sure which submatrix I have to take.
If I take the lower-right $(2 \times 1)$-submatrix I get $\sqrt2$ for $\alpha_3$ and a matrix $Q_3$ which looks wrong to me.
Best Answer
You are full on track towards $\,\left(\begin{smallmatrix}\ddot\smile& *& *\\ 0& \ddot\smile& *\\ 0& 0& \ddot\smile\\ 0& 0& 0\end{smallmatrix}\right)\;$ just go ahead: $$v_3\:=\: \begin{pmatrix}0\\ 0\\ \sqrt 2+1\\ 1\end{pmatrix}\quad\Longrightarrow\; -2\frac{v_3\,v_3^T}{v_3^Tv_3}\:=\: -\frac 2{\left(\sqrt 2+1\right)^2+1}\: \begin{pmatrix}0\\ 0\\ \sqrt 2+1\\ 1\end{pmatrix} \begin{pmatrix}0&0&\sqrt 2+1&1\end{pmatrix}$$ Thus, $$Q_3\:=\:\mathbb 1_{4\times 4}\: -\frac{2-\sqrt 2}2\: \begin{pmatrix}0\\ 0\\ \sqrt2+1\\ 1\end{pmatrix} \begin{pmatrix}0 &0 &\sqrt 2+1 &1\end{pmatrix}$$ and $$Q_3Q_2Q_1A\,=\, \begin{pmatrix}-1& 0& -1\\ 0& -1& 0\\ 0& 0& 1\\ 0& 0& 1\end{pmatrix} \,-\frac{2-\sqrt2}2\:\begin{pmatrix}0\\ 0\\ \sqrt2+1\\ 1\end{pmatrix} \begin{pmatrix}0&0&2+\sqrt2\end{pmatrix} =\begin{pmatrix}-1& 0& -1\\ 0& -1& 0\\ 0& 0& -\sqrt2\\ 0& 0& 0\end{pmatrix}$$
"Householder updates never entail the explicit formation of the Householder matrix."$\ $ is a quotation from Golub & Van Loan's book "Matrix computations" (on page 236, 4th edition 2013). So $Q_3$ was intentionally left in the form above, because treating it as a general matrix considerably increases work.