# 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

QT Q = In

where QT is the transpose matrix of Q .
Example of Matrices with Orthonormal Columns and the Property QT Q = In
1)
The columns of matrix

form an orthonormal set.

The transpose of A is

and therefore

2)
The columns of matrix form a set of orthonormal vectors.

The trasnpose of matrix B is
and therefore



## 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}$$