# QR-decomposition

I am doing an exericse from my Linear Algebra text-book and my task is to find a QR-decomposition

Find the QR-decomposition of the matrix $A=\begin{bmatrix} 1 & -1 & 4 \\ 1 & 4 & -2\\ 1 & 4 & 2 \\ 1 & -1 & 0 \end{bmatrix}$

Solution:

So here's my attempt to solve the problem. The first thing i want to get is an orthonormal basis therefor I will use Gram-Schmidt. Let's put $$f_1=\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, f_2=\begin{bmatrix} -1 \\ 4 \\ 4 \\ -1 \end{bmatrix}, f_3=\begin{bmatrix} 4 \\ -2 \\ -2 \\ 0 \end{bmatrix}$$

$(f_1,f_1)=1^2+1^2+1^2+1^2=4$

Thus the first vector to form the orthonormal basis is $e_1=\frac{1}{2}\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}$

By proceeding i get the vectors

$u=f_3-(f_3,e_1)e_1=\frac{1}{2}\begin{bmatrix} -5 \\ 5 \\ 5 \\ -5 \end{bmatrix}$ and so $e_2=\frac{1}{2}\begin{bmatrix} -1 \\ 1 \\ 1 \\ -1 \end{bmatrix}$.

$u_2=f_3-((f_3,e_1)e_1+(f_3,e_2)e_2)=\begin{bmatrix} 2 \\ 0 \\ 0 \\ -2 \end{bmatrix}$ and so, lastly, $e_3=\frac{1}{\sqrt{8}}\begin{bmatrix} 2 \\ 0 \\ 0 \\ -2 \end{bmatrix}$. This should be my $Q$-matrix (?), consisting of the orthornomal vectors $e_1$, $e_2$ and $e_3$, and here is where i pretty much get stuck. Because when i look at the formula for QR-decomposition it says that Q should be an orthogonal matrix (in the real case) and $R$ should be an upper triangular matrix. Well my matrix "$Q$" can't be a orthogonal matrix because e.g it isn't a square matrix. Also earlier in my text-book they said that every upper-triangular matrix is a sqaure matrix. But when i look at an example from my text-book where the matrix A is

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

First they mention that the rank is equal to 1 so they need to complete the first non-zero column to some basis and then they say that they have to make the $QR$-decomposition for the matrix $B=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$ instead. After a little calculation they get that $R=\frac{1}{\sqrt{2}}\begin{bmatrix} 0 & 2 & 4 \\ 0 & 0 & 0 \end{bmatrix}$

which isn't a square matrix. Should i do something like they do in this example? I have also been watching some videos about this and i am even more confused after i've watched them. I would be happy if someone could help me out :)

There are really two kinds of QR decomposition: there is the full QR decomposition, where $A$ is $m \times n$, $Q$ is $m \times m$, and $R$ is $m \times n$. There is also the reduced QR decomposition, where $A$ is $m \times n$ with rank $r$, $Q$ is $m \times r$, and $R$ is $r \times n$. If $m=r$ (i.e. the column space of $A$ is all of $\mathbb{R}^m$) then they are the same, otherwise they are different.
Gram-Schmidt applied to the columns of $A$ gives you a reduced QR decomposition. If $r<m$ (as in your case) and you want to make a full QR decomposition, you have to add columns to $Q$ which are not in the column space of $A$. In practice you can do this by randomly choosing a vector and then performing Gram-Schmidt to remove the component of this vector which is in the column space of $A$. Then you add a row of zeros to $R$, corresponding to the fact that the vector you just added is not in the column space of $A$.
$$e_3=\frac{1}{2}\begin{bmatrix} 1 & -1 & 1 & -1 \end{bmatrix}'$$
$$Q=[e_1\mid e_2\mid e_3]\text{; }R=\begin{bmatrix} e_1'\cdot f_1 & e_1'\cdot f_2 & e_1'\cdot f_3 \\ 0 & e_2'\cdot f_2 & e_2'\cdot f_3 \\ 0 & 0 & e_3'\cdot f_3\end{bmatrix}=\begin{bmatrix} 2 & 3 & 2 \\ 0 & 5 & -2 \\ 0 & 0 & 4\end{bmatrix}$$