QR Decomposition

Theorem

Let $A$ : an $m\times n$ matrix with linearly independent columns.

If

• $Q$ is an $m\times n$ matrix with orthonormal columns
• $R$ is an $n\times n$ upper triangular matrix with positive diagonal entries

Then $A$ can be factored as

$$A=QR$$

Procedure

1. Apply Gram-Schmidt Orthogonalization to columns of $A$ to obtain orthogonal vectors $\{{\mathbf{v}}_1,\dots ,{\mathbf{v}}_n\}$
2. Normalize to get orthonormal vectors ${\mathbf{q}}_i={\mathbf{v}}_i/||{\mathbf{v}}_i||$
3. Form $Q=[{\mathbf{q}}_1{\mathbf{q}}_2\cdots {\mathbf{q}}_n]$
4. Form $R=Q^{T}A$

Example

Find the QR decomposition of $A=\left[\begin{array}{cc}1& 0\\ 1& 1\\ 1& 1\end{array}\right]$

Using the columns ${\mathbf{u}}_1=(1,1,1)$ and ${\mathbf{u}}_2=(0,1,1)$:

1. Apply Gram-Schmidt:

   • ${\mathbf{v}}_1=(1,1,1)$
   • ${\mathbf{v}}_2=(0,1,1)-\frac{2}{3}(1,1,1)=\left(-\frac{2}{3},\frac{1}{3},\frac{1}{3}\right)$

2. Normalize:

   • ${\mathbf{q}}_1=\frac{1}{\sqrt{3}}(1,1,1)$
   • ${\mathbf{q}}_2=\frac{3}{\sqrt{6}}\left(-\frac{2}{3},\frac{1}{3},\frac{1}{3}\right)=\left(-\frac{2}{\sqrt{6}},\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}}\right)$

3. Form $Q$:

$$Q=\left[\begin{array}{cc}\frac{1}{\sqrt{3}}& -\frac{2}{\sqrt{6}}\\ \frac{1}{\sqrt{3}}& \frac{1}{\sqrt{6}}\\ \frac{1}{\sqrt{3}}& \frac{1}{\sqrt{6}}\end{array}\right]$$

4. Compute $R=Q^{T}A$:

$$\begin{array}{rl}R& =\left[\begin{array}{cc}⟨{\mathbf{c}}_1,{\mathbf{q}}_1⟩& ⟨{\mathbf{c}}_2,{\mathbf{q}}_1⟩\\ 0& ⟨{\mathbf{c}}_2,{\mathbf{q}}_2⟩\end{array}\right]\\ & =\left[\begin{array}{cc}\sqrt{3}& \frac{2}{\sqrt{3}}\\ 0& \frac{\sqrt{6}}{3}\end{array}\right]\end{array}$$

Therefore:

$$A=\left[\begin{array}{cc}\frac{1}{\sqrt{3}}& -\frac{2}{\sqrt{6}}\\ \frac{1}{\sqrt{3}}& \frac{1}{\sqrt{6}}\\ \frac{1}{\sqrt{3}}& \frac{1}{\sqrt{6}}\end{array}\right]\left[\begin{array}{cc}\sqrt{3}& \frac{2}{\sqrt{3}}\\ 0& \frac{\sqrt{6}}{3}\end{array}\right]$$