2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How did you arrive at this $v_1$? $\endgroup$ – VorKir Jan 20 '19 at 2:39
  • $\begingroup$ I corrected it. $\endgroup$ – Olsgur Jan 20 '19 at 11:30
  • $\begingroup$ You continue by moving down the main diagonal and applying the algorithm to the lower-right $3\times2$ submatrix. $\endgroup$ – amd Jan 20 '19 at 23:32
  • $\begingroup$ 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. $\endgroup$ – Olsgur Jan 21 '19 at 10:54
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.