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} \)

More References and links

  1. Vector Spaces - Questions with Solutions
  2. identity matrix
  3. Linear Algebra and its Applications - 5 th Edition - David C. Lay , Steven R. Lay , Judi J. McDonald
  4. Elementary Linear Algebra - 7 th Edition - Howard Anton and Chris Rorres

Share
Popular Pages