# QR Factorization

### General Gram-Schmidt procedure

The standard Gram-Schmidt procedure assumes that the input vectors ${\displaystyle a_{1},\dots ,a_{k}\in \mathbb {R} ^{n}}$ are independent. If we remove the requirement of independence, what we have is the general Gram-Schmidt procedure. Clearly, the ${\displaystyle R}$ in the factorization ${\displaystyle A=QR}$ is not an upper triangular vector anymore, but it has the upper staircase form. Of course, we can always permute the columns via permutation matrices ${\displaystyle S,P}$ such that the ${\displaystyle {\tilde {R}}}$ in ${\displaystyle A=Q[{\tilde {R}}\,S]P}$ becomes an upper triangular matrix concatenated to the right with some other matrix.

### Full QR Factorization

Assume that the ${\displaystyle QR}$ factorization of ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ is ${\displaystyle A=Q_{1}R_{1}}$. Note that the set columns of ${\displaystyle Q_{1}}$ have to be orthonormal, but ${\displaystyle Q_{1}}$ does not have to be an orthogonal matrix. Sometimes we want to "complete" it to an orthogonal matrix ${\displaystyle Q=[Q_{1}\,\,Q_{2}]}$; this leads to the full QR factorization:

${\displaystyle A=[Q_{1}\,\,Q_{2}]{\begin{bmatrix}R_{1}\\0\end{bmatrix}}}$.

This is pretty simple to achieve. Find any matrix ${\displaystyle {\tilde {A}}}$ such that ${\displaystyle [A\,\,{\tilde {A}}]}$ is full rank (e.g. ${\displaystyle {\tilde {A}}=I}$) and apply general Gram-Schmidt to ${\displaystyle [A\,\,{\tilde {A}}]}$. This operation would be called extending the original input set of vectors to an orthonormal basis.

${\displaystyle Q_{1}}$ and ${\displaystyle Q_{2}}$ are very interesting: The ranges ${\displaystyle {\mathcal {R}}(Q_{1})}$ and ${\displaystyle {\mathcal {R}}(Q_{2})}$ are complementary subspaces, since

• They are orthogonal, i.e. with an overloaded notation of ${\displaystyle \perp }$, we can write ${\displaystyle {\mathcal {R}}(Q_{1})\perp {\mathcal {R}}(Q_{2})}$
• Their sum is ${\displaystyle \mathbb {R} ^{n}}$, i.e. with the over-loaded notation of ${\displaystyle +}$, ${\displaystyle {\mathcal {R}}(Q_{1})+{\mathcal {R}}(Q_{2})=\mathbb {R} ^{n}}$.

This can also be written as

${\displaystyle {\mathcal {R}}(Q_{2})={\mathcal {R}}(Q_{1})^{\perp }}$ and ${\displaystyle {\mathcal {R}}(Q_{1})={\mathcal {R}}(Q_{2})^{\perp }}$.

Clearly, ${\displaystyle {\mathcal {R}}(Q_{1})={\mathcal {R}}(A)}$ and, less clearly, ${\displaystyle {\mathcal {R}}(Q_{2})={\mathcal {N}}(A^{T})}$ [1].

### Connection to Least-squares and projection

The matrix ${\displaystyle QQ^{T}}$ is the projection matrix in the context of least-squares.

#### References

1. Stephen Boyd, EE263 Lecture Notes 4