Using Gram-Schmidt to find the QR decomposition

Question

I'm having problems doing a QR decomposition of a matrix...

Let $A=\begin{bmatrix} {1} & {1} & {0} \\ {0} &{1} &{1} \\ {1} & {0} &{1} \end{bmatrix}$

Find the QR decomposition for A

Here's what I've been doing:

I choose this basis, $B=\left \{(1,0,1), (1,1,0), (0,1,1)\right \}$ (the columns of the matrix).

Now I use the Gram-Schmidt process (and this is where I'm having trouble)

$u_{1}=(1,0,1)$

$u_{2}=(1,1,0)$ (cuz $<(1,0,1), (1,1,0)>=0$)

$u_{3}=(0,1,1)-\frac{<(0,1,1), (1,1,0)>}{<(1,1,0), (1,1,0)>}(1,1,0)-\frac{<(0,1,1), (1,0,1)>}{<(1,0,1), (1,0,1)>}(1,0,1)=$ $(0,1,1)-1/2(1,1,0)-1/2(1,0,1)=(-1, 1/2, 1/2)$

And now I find the norm for all the three vectors:

$||u_{1}||=||u_{2}||=||u_{3}||=\sqrt{2}$

So the orthonormal basis must be $B'= \left \{(\frac{1}{\sqrt{2}},0,\frac{1}{\sqrt{2}}), (\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}},0), (\frac{-1}{\sqrt{2}}, \frac{1}{2\sqrt{2}}, \frac{1}{2\sqrt{2}})\right \}$ (Which it isn't orthonormal)

So $Q=\begin{bmatrix} {\frac{1}{\sqrt{2}}} & {\frac{1}{\sqrt{2}}} & {\frac{-1}{\sqrt{2}}} \\ {0} &{\frac{1}{\sqrt{2}}} &{\frac{1}{2\sqrt{2}}} \\ {\frac{0}{\sqrt{2}}} & {0} &{\frac{1}{2\sqrt{2}}} \end{bmatrix}$

Which $Q^{t}Q \neq I$ ($I$ being the identity matrix), so all I did was wrong... Where's my mistake?

Answer 1

You're computing $u_2$ wrongly.

I find it useful to set up a systematic way, where the information can be picked up easily.

Let $v_1$, $v_2$ and $v_3$ be the three columns of $A$.

GS1

$u_1=v_1$

$\langle u_1,u_1\rangle=2$

GS2

$\alpha_{12}=\dfrac{\langle u_1,v_2\rangle}{\langle u_1,u_1\rangle}=\dfrac{1}{2}$

$u_2=v_2-\alpha_{12}u_1=\begin{bmatrix}1/2\\1\\-1/2\end{bmatrix}$

$\langle u_2,u_2\rangle=\dfrac{3}{2}$

GS3

$\alpha_{13}=\dfrac{\langle u_1,v_3\rangle}{\langle u_1,u_1\rangle}=\dfrac{1}{2}$

$\alpha_{23}=\dfrac{\langle u_2,v_3\rangle}{\langle u_2,u_2\rangle}=\dfrac{1}{3}$

$u_3=v_3-\alpha_{13}u_1-\alpha_{23}u_2=\begin{bmatrix}-2/3\\2/3\\2/3\end{bmatrix}$

$\langle u_3,u_3\rangle=\dfrac{4}{3}$

Matrix $Q$

The matrix $Q$ has as columns the vectors $u_1$, $u_2$ and $u_3$ divided by their norms: $$ Q=\begin{bmatrix} 1/\sqrt{2} & 1/\sqrt{6} & -1/\sqrt{3} \\ 0 & 2/\sqrt{6} & 1/\sqrt{3} \\ 1/\sqrt{2} & -1/\sqrt{6} & 1/\sqrt{3} \end{bmatrix} $$

Matrix $R$

The matrix $R$ is obtained by multiplying each row of the upper unitriangular with the entries $\alpha_{ij}$ by the norm of the corresponding $u$ vector. $$ R=\begin{bmatrix} 1 & 1/2 & 1/2 \\ 0 & 1 & 1/3 \\ 0 & 0 & 1 \end{bmatrix} \begin{array}{l}\cdot\sqrt{2}\\\cdot \sqrt{6}/2\\\cdot 2/\sqrt{3}\end{array}= \begin{bmatrix} \sqrt{2} & \sqrt{2}/2 & \sqrt{2}/2 \\ 0 & \sqrt{6}/2 & \sqrt{6}/6 \\ 0 & 0 & 2/\sqrt{3} \end{bmatrix} $$

Answer 2

$u_1 $ is correct, your mistake is in $u_2$ \begin{equation} u_2 =(1,1,0) - \frac{<(1,0,1), (1,1,0)>}{<(1,0,1), (1,0,1)>}(1,0,1) \end{equation} which is \begin{equation} u_2 = (1,1,0) - (\frac{1}{2})(1,0,1) = \frac{1}{2}(1,1,-1) = (\frac{1}{2}, \frac{1}{2},-\frac{1}{2}) \end{equation} Now, \begin{equation} u_3 =(0,1,1) - \frac{<(1,0,1), (0,1,1)>}{<(1,0,1), (1,0,1)>}(1,0,1) - \frac{<(\frac{1}{2}, \frac{1}{2},-\frac{1}{2}), (0,1,1)>}{<(\frac{1}{2}, \frac{1}{2},-\frac{1}{2}), (\frac{1}{2}, \frac{1}{2},-\frac{1}{2})>}(\frac{1}{2}, \frac{1}{2},-\frac{1}{2}) \end{equation} that is \begin{equation} u_3 = (0,1,1) - \frac{1}{2}(1,0,1) - \frac{0}{\frac{3}{4}}(\frac{1}{2}, \frac{1}{2},-\frac{1}{2}) = (-\frac{1}{2},1,\frac{1}{2}) \end{equation} This is an orthogonal basis, i.e. \begin{equation} O = \begin{bmatrix} u_1 & u_2 & u_3 \end{bmatrix} \end{equation} where $O^T O $ is diagonal. To have an orthonormal one, just take (as you also mention) \begin{align} l_1 &= \frac{u_1}{\Vert u_1 \Vert}\\ l_2 &= \frac{u_2}{\Vert u_2 \Vert}\\ l_3 &= \frac{u_3}{\Vert u_3 \Vert} \end{align}

Answer 3

Suppose that we have $A$ as the following matrix

$$ A = \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{bmatrix} \tag{1} $$

modified Gram Schmidt is

$$ v_{1} =a_{1} \tag{2}$$

$$ r_{11} = \| v_{1} \| = \sqrt{ 2}\tag{3}$$

$$ q_{1} = \frac{v_{1}}{r_{11}} = \langle \frac{1}{\sqrt{2}} , 0 , \frac{1}{\sqrt{2}} \rangle \tag{4}$$

$$ r_{12} = q_{1}^{*}v_{2} \tag{5} $$ they only share one vector entry in common $$ r_{12} = \frac{1}{\sqrt{2}} \tag{6}$$ $$ v_{2} = \langle 1 , 1, 0 \rangle - \frac{1}{\sqrt{2}}\langle \frac{1}{\sqrt{2}} , 0 , \frac{1}{\sqrt{2}} \rangle \tag{7} $$

$$ v_{2} = \langle \frac{1}{2} , 1, \frac{-1}{2} \rangle \tag{8} $$

$$ r_{13} = q_{1}^{*}v_{3} \tag{9} $$ $$ r_{13} = \frac{1}{\sqrt{2}} \tag{10} $$

$$ v_{3} = \langle 0 , 1, 1 \rangle - \frac{1}{\sqrt{2}} \langle 0 , \frac{1}{\sqrt{2}} , \frac{1}{\sqrt{2}} \rangle \tag{11} $$

$$ v_{3} = \langle 0 , 1, 1 \rangle - \langle 0 , \frac{1}{2} , \frac{1}{2} \rangle = \langle 0 , \frac{1}{2} , \frac{1}{2} \rangle \tag{12} $$ Now we repeat

$$ r_{22} = \| v_{2}\| =\sqrt{(\frac{1}{2})^{2} + 1 + (\frac{1}{2})^{2} }\tag{13}$$ $$ r_{22} = \| v_{2}\| = \frac{\sqrt{6}}{2}\tag{13}$$

$$ q_{2} = \frac{v_{2}}{r_{22} } \tag{14} $$

$$ q_{2} = \langle \frac{\frac{1}{2}}{\frac{\sqrt{6}}{2}}, \frac{1}{\frac{\sqrt{6}}{2}} ,\frac{\frac{-1}{2}}{\frac{\sqrt{6}}{2}} \rangle \tag{15} $$

$$ q_{2} = \langle \frac{1}{\sqrt{6}}, \frac{2}{\sqrt{6}} ,\frac{-1}{\sqrt{6}} \rangle \tag{16} $$

Go on from there..