# The QR Decomposition of a Matrix

   

## Matrices with Orthonormal Columns

A set of vectors is called orthonormal if each vector in the set has a length (or norm) equal to $1$ and each vector in the set in orthogonal to all the other vectors in the set.
A matrix $Q$ whose columns is a set of orthonomal vectors has the property
$Q^T Q = I_n$ where $Q^T$ is the transpose matrix of $Q$.
Example of Matrices with Orthonormal Columns and the Property $Q^T Q = I_n$
1)
The columns of matrix $A = \begin{bmatrix} 1 & 0 \\ 0 & 0 \\ 0 & -1 \end{bmatrix}$ form an orthonormal set.

The transpose of $A$ is $A^T = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & - 1 \end{bmatrix}$
and therefore
$A^T A = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & - 1 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 0 \\ 0 & -1 \end{bmatrix} = \begin{bmatrix}1&0\\ 0&1\end{bmatrix} = I_2$

2)
The columns of matrix $B = \begin{bmatrix} \dfrac{1}{\sqrt 2} & 0 & \dfrac{1}{\sqrt {10}}\\ 0 & \dfrac{1}{\sqrt 2} & \dfrac{2}{\sqrt {10}}\\ \dfrac{1}{\sqrt 2} & 0 & - \dfrac{1}{\sqrt {10}} \\ 0 & \dfrac{1}{\sqrt 2} & - \dfrac{2}{\sqrt {10}} \end{bmatrix}$ form a set of orthonormal vectors.

The trasnpose of matrix $B$ is $B^T = \begin{bmatrix} \dfrac{1}{\sqrt{2}}&0&\dfrac{1}{\sqrt{2}}&0 \\ 0&\dfrac{1}{\sqrt{2}}&0&\dfrac{1}{\sqrt{2}}\\ \dfrac{1}{\sqrt{10}}&\dfrac{2}{\sqrt{10}}&-\dfrac{1}{\sqrt{10}}&-\dfrac{2}{\sqrt{10}} \end{bmatrix}$
and therefore
$B^T B = \begin{bmatrix} \dfrac{1}{\sqrt{2}}&0&\dfrac{1}{\sqrt{2}}&0 \\ 0&\dfrac{1}{\sqrt{2}}&0&\dfrac{1}{\sqrt{2}}\\ \dfrac{1}{\sqrt{10}}&\dfrac{2}{\sqrt{10}}&-\dfrac{1}{\sqrt{10}}&-\dfrac{2}{\sqrt{10}} \end{bmatrix} \begin{bmatrix} \dfrac{1}{\sqrt 2} & 0 & \dfrac{1}{\sqrt {10}}\\ 0 & \dfrac{1}{\sqrt 2} & \dfrac{2}{\sqrt {10}}\\ \dfrac{1}{\sqrt 2} & 0 & - \dfrac{1}{\sqrt {10}} \\ 0 & \dfrac{1}{\sqrt 2} & - \dfrac{2}{\sqrt {10}} \end{bmatrix} = \begin{bmatrix}1&0&0\\ 0&1&0\\ 0&0&1 \end{bmatrix} = I_3$

## The QR Decomposition of a Matrix Applying the Gram-Schmidt process

An $m \times n$ matrix $A$, whose columns form a set of linearly independent vectors, may be factored (or decomposed) as the product of two matrices $Q$ and $R$ as follows
$A = Q R$ where $Q$ is an $m \times n$ matrix whose columns form an orthonormal set of vectors and $R$ is an $n \times n$ upper triangular matrix.
Matrix $Q$ has orthonormal columns and therefore has the property discussed above
$Q^T Q = I_n$
where $I_n$ is the $n \times n$ identity matrix

We now describe the Gram-Schmidt process to factor a matrix $A$ with linearly independent columns.
Step 1: We write matrix $A$ as
$A = [v_1 v_2 .... v_n]$
where $v_1$ , $v_2$ .... $v_n$ are column vectors
Step 2: Use the Gram-Schmidt process to generate an orthonormal set of vectors $q_1$ , $q_2$ .... $q_n$ form the vectors $v_1$ , $v_2$ .... $v_n$
Step 3: Write matrix $A$ as a the product of two matrices $A = Q R$ where $Q$ is an $m \times n$ matrix with orthonormal columns $q_1$ , $q_2$ .... $q_n$ generated in step 2 and $R$ as an upper triangular $n \times n$ matrix given by
$R = Q^T A$.

How to obtain $R = Q^T A$?
Multiply both side of the equation by $A = Q R$ by $Q^T$
$Q^T A = Q^T Q R$
Use the property $Q^T Q = I_n$ of matrices with orthonormal columns discussed above
$Q^T A = I_n R$
Simplify to obtain
$R = Q^T A$

## Examples with Solutions

Example 1

Find the $QR$ decomposition (or factorization) of matrix $A = \begin{bmatrix} 1 & 0 & 2\\ 0 & 2 & 0 \\ 0 & -1 & 1 \end{bmatrix}$.

Solution to Example 1
Let $\textbf v_1 , \textbf v_2 , \textbf v_3$ be the columns of matrix $A$.
$\textbf {v}_1 = \begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix}$ , $\textbf {v}_2 = \begin{bmatrix} 0\\ 2\\ -1 \end{bmatrix}$ , $\textbf {v}_3 = \begin{bmatrix} 2\\ 0\\ 1 \end{bmatrix}$

Use the Gram-Schmidt process to generate orthonormal vectors

$\textbf {q}_1 = \begin{bmatrix} 1\\ 0\\ 0 \end{bmatrix}$ , $\textbf {q}_2 = \begin{bmatrix} 0\\ \dfrac{2}{\sqrt 5}\\ -\dfrac{1}{\sqrt 5} \end{bmatrix}$ , $\textbf {q}_3 = \begin{bmatrix} 0\\ \dfrac{1}{\sqrt 5}\\ \dfrac{2}{\sqrt 5} \end{bmatrix}$
We now write matrix $Q$ whose columns are the vectors $\textbf q_1 , \textbf q_2 , \textbf q_3$
$Q = \begin{bmatrix} 1 & 0 & 0\\ 0 & \dfrac{2}{\sqrt 5} & \dfrac{1}{\sqrt 5} \\ 0 & -\dfrac{1}{\sqrt 5} & \dfrac{2}{\sqrt 5} \end{bmatrix}$
We now calculate $R$
$R = Q^T A = \begin{bmatrix} 1 & 0 & 0\\ 0 & \dfrac{2}{\sqrt 5} & - \dfrac{1}{\sqrt 5} \\ 0 & \dfrac{1}{\sqrt 5} & \dfrac{2}{\sqrt 5} \end{bmatrix} \begin{bmatrix} 1 & 0 & 2\\ 0 & 2 & 0 \\ 0 & -1 & 1 \end{bmatrix} = \begin{bmatrix}1&0&2\\ 0&\sqrt{5}&-\frac{1}{\sqrt{5}}\\ 0&0&\frac{2}{\sqrt{5}} \end{bmatrix}$
We now write the given matrix $A$ in factored form as follows
$A = Q R = \begin{bmatrix} 1 & 0 & 0\\ 0 & \dfrac{2}{\sqrt 5} & \dfrac{1}{\sqrt 5} \\ 0 & -\dfrac{1}{\sqrt 5} & \dfrac{2}{\sqrt 5} \end{bmatrix} \begin{bmatrix}1&0&2\\ 0&\sqrt{5}&-\frac{1}{\sqrt{5}}\\ 0&0&\frac{2}{\sqrt{5}} \end{bmatrix}$

Example 2

Find the $QR$ decomposition (or factorization) of matrix $A = \begin{bmatrix} 0 & 1 & 0\\ 0 & 1 & 2 \\ -1 & 0 & 1 \\ 0 & -1 & 1 \end{bmatrix}$.

Solution to Example 2
Let $\textbf v_1 , \textbf v_2 , \textbf v_3$ be the columns of matrix $A$.
$\textbf {v}_1 = \begin{bmatrix} 0\\ 0\\ -1\\ 0 \end{bmatrix}$ , $\textbf {v}_2 = \begin{bmatrix} 1\\ 1\\ 0\\ -1 \end{bmatrix}$ , $\textbf {v}_3 = \begin{bmatrix} 0\\ 2\\ 1\\ 1 \end{bmatrix}$

Use the Gram-Schmidt process to generate orthonormal vectors

$\textbf {q}_1 = \begin{bmatrix} 0 \\ 0\\ -1\\ 0 \end{bmatrix}$ , $\textbf {q}_2 = \begin{bmatrix} \dfrac{1}{\sqrt 3}\\ \dfrac{1}{\sqrt 3}\\ 0\\ -\dfrac{1}{\sqrt 3} \end{bmatrix}$ , $\textbf {q}_3 = \begin{bmatrix} - \dfrac{1}{\sqrt {42}}\\ \dfrac{5}{\sqrt {42}}\\ 0\\ \dfrac{4}{\sqrt {42}}\\ \end{bmatrix}$
We now write matrix $Q$ whose columns are the vectors $\textbf q_1 , \textbf q_2 , \textbf q_3$
$Q = \begin{bmatrix} 0 & \dfrac{1}{\sqrt 3} & - \dfrac{1}{\sqrt {42}}\\ 0 & \dfrac{1}{\sqrt 3} & \dfrac{5}{\sqrt {42} }\\ -1 & 0 & 0 \\ 0 & -\dfrac{1}{\sqrt 3} & \dfrac{4}{\sqrt {42}} \end{bmatrix}$
We now calculate $R$
$R = Q^T A = \begin{bmatrix} 0 & 0 & -1 & 0\\ \dfrac{1}{\sqrt 3} & \dfrac{1}{\sqrt 3} & 0 & -\dfrac{1}{\sqrt 3}\\ - \dfrac{1}{\sqrt {42}} & \dfrac{5}{\sqrt {42} } & 0 & \dfrac{4}{\sqrt {42} } \end{bmatrix} \begin{bmatrix} 0 & 1 & 0\\ 0 & 1 & 2 \\ -1 & 0 & 1 \\ 0 & -1 & 1 \end{bmatrix} = \begin{bmatrix} 1&0&-1\\ 0&\sqrt{3}&\frac{1}{\sqrt{3}}\\ 0&0&\sqrt{\frac{14}{3}} \end{bmatrix}$
We now write the given matrix $A$ in factored form as follows
$A = Q R = \begin{bmatrix} 0 & \dfrac{1}{\sqrt 3} & - \dfrac{1}{\sqrt {42}}\\ 0 & \dfrac{1}{\sqrt 3} & \dfrac{5}{\sqrt {42} }\\ -1 & 0 & 0 \\ 0 & -\dfrac{1}{\sqrt 3} & \dfrac{4}{\sqrt {42}} \end{bmatrix} \begin{bmatrix} 1&0&-1\\ 0&\sqrt{3}&\frac{1}{\sqrt{3}}\\ 0&0&\sqrt{\frac{14}{3}} \end{bmatrix}$