# Householder transformations to upper triangular form

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.

• How did you arrive at this $v_1$? – VorKir Jan 20 '19 at 2:39
• I corrected it. – Olsgur Jan 20 '19 at 11:30
• You continue by moving down the main diagonal and applying the algorithm to the lower-right $3\times2$ submatrix. – amd Jan 20 '19 at 23:32
• Thanks for the hint. Now I got $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}$. But if I take the lower-right $(2 \times 1)$ submatrix of $Q_2Q_1A$ I get $\alpha_3=\sqrt2$ which looks wrong to me. – Olsgur Jan 21 '19 at 10:54

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.