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 .
form a set of orthonormal vectors.
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 \]
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}
\)