QR decompostion - how to finish decomposition?

Question

I try to find $QR$ decomposition, but I got stuck in some etap and I can't continue - how to finish it ?

$$ A= \left[\begin{matrix} 1 & -1 \\ 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{matrix}\right] $$

$v = \left[\begin{matrix} 1+2 \\ 1 \\ 1 \\ 1 \end{matrix}\right] \cdot \frac{1}{\sqrt{9+1+1+1}} = \frac{1}{2\sqrt{3}}\cdot \left[\begin{matrix} 1+2 \\ 1 \\ 1 \\ 1 \end{matrix}\right] $

$$Q_1 = I - 2vv^t = I - \frac16 A= \left[\begin{matrix} 9 & 3 & 3 &3 \\ 3 & 1 & 1 &1 \\ 3 & 1 & 1 &1 \\ 3 & 1 & 1 &1 \\ \end{matrix}\right] = \left[\begin{matrix} -\frac{1}{2} & -\frac{1}{2} & -\frac{1}{2} &-\frac{1}{2} \\ -\frac{1}{2} & \frac{5}{6} & -\frac{1}{6} &-\frac{1}{6} \\ -\frac{1}{2} &- \frac{1}{6} & \frac{5}{6} &-\frac{1}{6} \\ -\frac{1}{2} &- \frac{1}{6} & -\frac{1}{6} &\frac{5}{6} \\ \end{matrix}\right] $$

$$Q_1A =\left[\begin{matrix} -2 & -1 \\ 0 & 0 \\ 0 &1 \\ 0 &2 \\ \end{matrix}\right] $$

Answer 1

I checked it yesterday night, you computed the first Householder-Matrix right and I assume that multiplication is right.

Applying the first Householder-Transformation, you somehow mapped the first column of your matrix $A$ to a constant $c$ ($c=2$ in your case) times the first unit vector. This is what should happen.

So now you're in

Iteration 2

As your current Matrix you now consider a Submatrix of $Q_1A$, namely you cut out the first row and first column, so you just consider the matrix

$ (Q_1A)^{1,1}=\begin{bmatrix}0\\1\\2\end{bmatrix} $

(the subscript denotes the row and column where you cut off)

You now want the second Householder-Transformation to map the first column of this matrix to $c_2 e_2$, where $c_2\not=0$ is constant and $e_1$ is the first unit vector. So you calculate again:

$\tilde{v_2} = \begin{bmatrix}0\\1\\2\end{bmatrix}-\sqrt{1^2+2^2}\begin{bmatrix}1\\0\\0\end{bmatrix} = \begin{bmatrix}-\sqrt{5}\\1\\2\end{bmatrix}$.

The vector can be normalized:

$\bar{v_2} = \frac{1}{\sqrt{5+1+4}}\begin{bmatrix}-\sqrt{5}\\1\\2\end{bmatrix} = \begin{bmatrix}-\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{10}}\\ \sqrt{\frac{2}{5}}\end{bmatrix}$

Next we compute the (reduced) Householder-Transformation matrix as usual

$Q_2^{1,1} = I - \bar{v_2}\bar{v_2}^T$

NOTE: We reduced the dimension of our system in the begin of iteration 2 by one (by considering the submatrix). Our Householder-Transformation needs to be appropriate for the initial system, therefore we need to embed the matrix $Q_2^{1,1}$ in a higher dimensional matrix as follows:

$ Q_2 = \begin{bmatrix}1&0\\0&Q_2^{1,1}\end{bmatrix} $

Using this matrix $Q_2$ we are done computing the QR-Decomposition of $A$:

$ Q_2Q_1 A = R = \begin{bmatrix}2&1\\0&\sqrt{5}\\0&0\\0&0\end{bmatrix} $

Remark: If a third iteration was necessary, you would need to cut off after row 2 and column 2 to get the reduced system. Analogously, the embedding would be slightly different, namely in the top-left corner there would be $I_2 = \begin{bmatrix}1&0\\0&1\end{bmatrix}$

EDIT: I had some wrong order of the transformation matrices when applied to A

Answer 2

Let me try again: using my $v_2$ from the answer compute the second Householder matrix. This matrix is $Q_2$.

You have already computed $Q_1$ in your question-post.

Then define a matrix $Q^T$ as the product of both in this very order:

$Q^T =Q_2Q_1$

Then you have that $Q^T$ is an orthogonal matrix and therefore $Q^TQ=I$ is the unit matrix.

You have by the computation the equation

$Q_2Q_1A=R$

This is nothing else (using the definition of $Q^T$ on the Left hand side and the orthogonality of Q on the Right hand side):

$Q^TA = Q^TQR$

And now you multiply both sides with Q to get

$\underbrace{QQ^T}_{=I}A = \underbrace{QQ^T}_{=I}QR$

So

$ A = QR$