Theorem 6.5.1.
Every \(m\times n\) matrix with linearly independent columns has a \(QR\) factorization, \(A=QR\text{,}\) where columns of \(Q\) are orthonormal and \(R\) is an upper triangular matrix with positive diagonal entries.
Section 6.5 QR-Factorization
Let \(A\) be an \(m\times n\) matrix whose columns are \(a_1,\ldots, a_n\text{.}\) Further assume that columns of \(A\) are linearly independent. Using the Gram-Schmidt orthogonalization process
\begin{align*}
u_1:\amp = a_1\\
u_2:\amp = a_2 -\frac{a_2\cdot u_1}{\norm{u_1}^2}u_1 \\
\vdots\amp\\
u_k: \amp=a_k-\frac{a_k\cdot u_1}{\norm{u_1}^2}u_1-\cdots -
\frac{a_k\cdot u_{k-1}}{\norm{u_{k-1}}^2}u_{k-1}\\
\vdots\amp
\end{align*}
and define \(q_k:= \frac{u_k}{\norm{u_k}}, k=1,\ldots, n\text{.}\) This implies
\begin{align*}
\norm{u_k}q_k \amp = u_k = a_k-\frac{a_k\cdot u_1}{\norm{u_1}^2}u_1-\cdots -\frac{a_k\cdot u_{k-1}}{\norm{u_{k-1}}^2}u_{k-1}\\
\amp =a_k-(a_k\cdot q_1)q_1-(a_k\cdot q_2)q_2+\cdots - (a_k\cdot q_{k-1})q_{k-1}\text{.}
\end{align*}
Hence
\begin{equation*}
a_k = (a_k\cdot q_1)q_1+(a_k\cdot q_2)q_2+\cdots + (a_k\cdot q_{k-1})q_{k-1}+\norm{u_k}q_k, k=1,2,\ldots, n\text{.}
\end{equation*}
Thus we have
\begin{align*}
a_1: = \amp \norm{u_1}q_1\\
a_2: = \amp (a_2\cdot q_1)q_1+\norm{u_2}q_2\\
\amp \vdots\\
a_k: =\amp (a_k\cdot q_1)q_1+(a_k\cdot q_2)q_2+\cdots + (a_k\cdot q_{k-1})q_{k-1}+\norm{u_k}q_k\\
\amp \vdots
\end{align*}
Thus
\begin{align*}
A \amp = [a_1~~a_2~~a_3~~\cdots~~a_n]\\
\amp = [q_1~~q_2~~q_3~~\cdots~~q_n]
\begin{bmatrix}\norm{u_1} \amp a_2\cdot q_1 \amp a_3\cdot q_1\amp \cdots \amp a_n\cdot q_1\\
0\amp \norm{u_2} \amp a_3\cdot q_2 \amp \cdots \amp a_n\cdot q_2\\
0\amp 0 \amp \norm{u_3}\amp \cdots \amp a_n\cdot q_3\\
\vdots \amp \vdots \amp \vdots \amp \ddots \amp \vdots\\ 0\amp 0 \amp 0 \amp \cdots \amp \norm{u_n} \end{bmatrix}\\
\amp =QR
\end{align*}
Here \(Q\) has orthogonal columns and \(R\) is upper triangular whose diagonal entries are positive, hence non-singular. This is what is known as \(QR\) factorization. Thus we have the following result.
Example 6.5.2.
Let \(A = \begin{pmatrix}0 \amp 1 \amp 1\\ 1 \amp 1 \amp -2\\ 1 \amp 1 \amp 2 \end{pmatrix} = \begin{bmatrix}a_1 \amp a_2 \amp a_3 \end{bmatrix}\text{.}\) Let us find the \(QR\) factorization of \(A\text{.}\) Note that columns of \(A\) are vectors \(v_1, v_2, v_3\) in the Example 6.2.1. We have found \(q_1, q_2, q_3\) in this example. Hence
\begin{equation*}
Q = \begin{bmatrix}q_1 \amp q_2 \amp q_3 \end{bmatrix} = \begin{pmatrix}0 \amp 1 \amp 0 \\ \frac{1}{\sqrt{2}} \amp 0 \amp \frac{-1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \amp 0 \amp \frac{1}{\sqrt{2}} \end{pmatrix}\text{.}
\end{equation*}
We also have
\begin{equation*}
u_1= (0, 1, 1), u_2=(1,0,0), u_3=(0,-2,2)
\end{equation*}
Hence
\begin{equation*}
R = \begin{pmatrix}\norm{u_1} \amp a_2 \cdot q_1 \amp a_3 \cdot q_1\\ 0 \amp \norm{u_2} \amp a_3 \cdot q_2\\ 0 \amp 0 \amp \norm{u_3} \end{pmatrix} = \begin{pmatrix}\sqrt{2} \amp \sqrt(2) \amp 0\\ 0 \amp 1 \amp 1 \\ 0 \amp 0 \amp 2\sqrt{2} \end{pmatrix}
\end{equation*}
Note that once we have \(Q\text{,}\) then \(R = Q^TA\text{.}\)
Example 6.5.3.
Find the QR-factorization of \(A=\left(\begin{array}{rrr} -1 \amp 1 \amp -1 \\ 1 \amp -1 \amp 0 \\ 0 \amp 0 \amp 2 \\ 1 \amp 1 \amp 1 \end{array} \right)=\begin{bmatrix}a_1\amp a_2\amp a_3 \end{bmatrix}\text{.}\) It is easy to check that columns of \(A\) are linearly independent. In fact, columns of \(A\) are rows of the matrix defined in the Example Example 6.2.2. From this example, we have
\begin{equation*}
u_1 = \begin{pmatrix}-1\\ 1\\ 0\\ 1 \end{pmatrix},
q_1 = \begin{pmatrix}-\frac{1}{\sqrt{3}}\\\frac{1}{\sqrt{3}}\\0\\\frac{1}{\sqrt{3}} \end{pmatrix},
u_2 = \begin{pmatrix}2/3\\ -2/3\\ 0\\ 4/3 \end{pmatrix},
\end{equation*}
\begin{equation*}
q_2 = \begin{pmatrix}\frac{1}{\sqrt{6}}\\ -\frac{1}{\sqrt{6}}\\0\\\sqrt{\frac{2}{3}} \end{pmatrix},
u_3 = \begin{pmatrix}-1/2\\-1/2\\2\\0 \end{pmatrix},
q_3 = \begin{pmatrix}-\frac{1}{3} \, \sqrt{\frac{1}{2}}\\-\frac{1}{3} \, \sqrt{\frac{1}{2}}\\\frac{4}{3} \, \sqrt{\frac{1}{2}}\\0 \end{pmatrix}
\end{equation*}
Hence
\begin{equation*}
Q = [q_1~q_2~q_3]=\left(\begin{array}{rrr} -\frac{1}{3} \, \sqrt{3} \amp \frac{1}{2} \, \sqrt{\frac{2}{3}} \amp -\frac{1}{3} \, \sqrt{\frac{1}{2}} \\ \frac{1}{3} \, \sqrt{3} \amp -\frac{1}{2} \, \sqrt{\frac{2}{3}} \amp -\frac{1}{3} \, \sqrt{\frac{1}{2}} \\ 0 \amp 0 \amp \frac{4}{3} \, \sqrt{\frac{1}{2}} \\ \frac{1}{3} \, \sqrt{3} \amp \sqrt{\frac{2}{3}} \amp 0 \end{array} \right)\text{.}
\end{equation*}
Also
\begin{equation*}
R = Q^TA=\left(\begin{array}{rrr} \sqrt{3} \amp -\frac{1}{3} \, \sqrt{3} \amp \frac{2}{3} \, \sqrt{3} \\ 0 \amp 2 \, \sqrt{\frac{2}{3}} \amp \frac{1}{2} \, \sqrt{\frac{2}{3}} \\ 0 \amp 0 \amp 3 \, \sqrt{\frac{1}{2}} \end{array} \right)\text{.}
\end{equation*}
Remark 6.5.4.
If a matrix \(A\) has independent rows, then we apply \(QR\) factorization to \(A^T\text{.}\) Thus
\begin{equation*}
A^T = (QR)^T=R^TQ^T=LP
\end{equation*}
where \(L\) is the the invertible lower triangular matrix with positive diagonal entries and and \(P\) has orthogonal rows.
Remark 6.5.5.
In case a matrix \(A\) has linearly independent columns then the \(QR\) factorization is unique. That is, if \(A= Q_1R_1=Q_2R_2\text{,}\) then \(Q_1=Q_2\) and \(R_1=R_2\text{.}\)
Checkpoint 6.5.6.
Find the QR-factorization of the following matrices:
\begin{equation*}
\begin{bmatrix}2 \amp 1 \\ 1 \amp 1 \end{bmatrix} ,
\begin{bmatrix}1 \amp -1 \amp 1\\ 2 \amp 0 \amp 1\\2 \amp 1 \amp -2 \end{bmatrix} ,
\begin{bmatrix}1 \amp 1 \amp 0 \\-1 \amp 0 \amp 1\\0 \amp 1 \amp 1\\1 \amp -1 \amp 0 \end{bmatrix}
\end{equation*}
