Gram-Schmidt Process and QR Factorization

by Dave
(DAVE)—

In this article, I explain what the Gram-Schmidt Process is and what a QR Factorization is. I do this by working through several examples. Also, I include the commutative diagrams for the corresponding transformations.

Gram-Schmidt Process

The GramSchmidt process represents a change of basis from a basis $\mathcal{B}=(v_1, v_2, \ldots,v_m)$ of a subspace $V$ of $\mathbb{R}^n$ to an orthonormal basis $\mathcal{U}=(u_1, u_2, \ldots,u_m)$ of $V$; it is most sufficiently described in terms of the change of basis matrix $R$ from $\mathcal{B}$ to $\mathcal{U}$ via,

\begin{equation} M:=\begin{bmatrix} v_1 & v_2 & \cdots & v_m \end{bmatrix} =\begin{bmatrix} u_1 & u_2 & \cdots & u_m \end{bmatrix} R=:QR \end{equation}

We can represent the relationship among the matrices $M, Q$, and $R$ in a commutative diagram:

Gram-Schmidt Process and QR Factorization

The $QR$ factorization is an effective way to organize and record the work performed in the Gram-Schmidt process; it is also useful for many computational and theoretical purposes.

Theorem. (Gram-Schmidt Process) Let $v_1, v_2, \ldots, v_m$ be a basis of a subspace $V$ of $\mathbb{R}^n.$ Then \begin{equation} \begin{array}{cccc} u_1 = \frac{1}{||v_1 || } v_1, & u_2 = \frac{1}{||v_2^{\perp} || } v_2^\perp, & \ldots, & u_m = \frac{1}{|| v_m^\perp || } v_m^\perp \end{array} \end{equation} is an orthonormal basis of $V$ where \begin{equation} v_j^\perp = v_j – (u_1 \cdot v_j) u_1 – (u_2 \cdot v_j) u_2 – \cdots – (u_{j-1} \cdot v_j) u_{j-1}. \end{equation}

Proof. For each $j$, we resolve the vectors $v_j$ into its components parallel and perpendicular to the span of the preceding vectors $v_1, v_2, \ldots, v_{j-1}$: $$ v_j = v_j^\parallel + v_j^\perp \hspace{1cm} \text{with respect to } \mathop{span}(v_1, v_2, \ldots, v_{j-1}).$$ Then use Orthogonal Projection.

Perform the Gram-Schmidt Process on the Following Sequence of Vectors

Example. Perform the Gram-Schmidt process on the vectors $$ v_1=\begin{bmatrix}4 \\ 0 \\ 3\end{bmatrix}, \qquad v_2=\begin{bmatrix}25 \\ 0 \\ -25\end{bmatrix}, \qquad v_3=\begin{bmatrix}0 \\ -2 \\ 0\end{bmatrix}. $$ By Gram-Schmidt Process, we determine $u_1, u_2, u_3$ as follows: $$ u_1= \begin{bmatrix}4/5 \\ 0 \\ 3/5\end{bmatrix}, \hspace{1cm} u_2=\frac{v_2^\perp}{\left|\left|v_2^\perp\right|\right|} =\frac{v_2-\left(u_1 \cdot v_2\right) u_1}{\left|\left|v_2-\left(u_1 \cdot v_2\right)u_1\right|\right|} =\begin{bmatrix}3/5 \\ 0 \\ -4/5\end{bmatrix}, $$ and $$ u_3=\frac{v_3^\perp}{\left|\left|v_3^\perp\right|\right|} =\frac{v_3-\left(u_1 \cdot v_3\right) u_1-\left(u_2 \cdot v_3\right) u_2 }{\left|\left|v_3-\left(u_1 \cdot v_3\right) u_1-\left(u_2 \cdot v_3\right) u_2\right|\right|} =\begin{bmatrix}0 \\ -1 \\ 0\end{bmatrix}. $$ Therefore $$ \left( \begin{bmatrix}4/5 \\ 0 \\ 3/5\end{bmatrix}, \begin{bmatrix}3/5 \\ 0 \\ -4/5\end{bmatrix}, \begin{bmatrix}0 \\ -1 \\ 0\end{bmatrix}\right). $$ is an orthonormal basis for $\mathop{span} (v_1, v_2, v_3).$

QR Factorization

When performing Gram-Schmidt Process the information to perform a QR Factorization is also obtained.

Theorem. (QR Factorization) Let $M$ be an $n \times m$ matrix with linearly independent columns $v_1 , v_2,\ldots, v_m.$ Then there exists an $n\times m$ matrix $Q$ whose columns $u_1, u_2, \ldots, u_m$ are orthonormal and an upper triangular matrix $R$ with positive diagonal entries such that $M=Q R$; and this representation is unique. Furthermore, the entries $r_{ij}$ of $R$ are given by

$r_{11}=\left|\left|v_1\right|\right|$,

$r_{jj}=||v_j^\perp||$ (for $j=2,\ldots,m$), and

$r_{i j}=u_i \cdot v_j$ (for $i<j$).

Example. Find the $QR$ factorization of the matrix and display the commutative diagram. $$ M=\begin{bmatrix} 4 & 25 & 0 \\ 0 & 0 & -2 \\ 3 & -25 & 0\end{bmatrix} $$ Let $$ \begin{array}{ccc} v_1=\begin{bmatrix}4 \\ 0 \\ 3\end{bmatrix}, & v_2=\begin{bmatrix}25 \\ 0 \\ -25\end{bmatrix}, & v_3=\begin{bmatrix}0 \\ -2 \\ 0\end{bmatrix} \end{array} $$ then (as determined above) an orthonormal basis for the column vectors of $M$ is $$ \left(u_1, u_2, u_3\right)=\left( \begin{bmatrix}4/5 \\ 0 \\ 3/5\end{bmatrix}, \begin{bmatrix}3/5 \\ 0 \\ -4/5\end{bmatrix}, \begin{bmatrix}0 \\ -1 \\ 0\end{bmatrix}\right). $$ Determining the entries of $R$ (also as determined above): $$ \begin{array}{ccc} r_{11}=\left|\left|v_1\right|\right|=5, & r_{22}=\left|\left|v_2^\perp\right|\right|=35, & r_{33}=\left|\left|v_3^\perp\right|\right|=2 \end{array} $$ $$ \begin{array}{ccc} r_{12}=u_1 \cdot v_2=5, & r_{13}=u_1 \cdot v_3=0, & r_{23}=u_2 \cdot v_3=0 \end{array} $$ and therefore, the $QR$-factorization of $M$ is $$ M= \begin{bmatrix} 4 & 25 & 0 \\ 0 & 0 & -2 \\ 3 & -25 & 0\end{bmatrix} = \begin{bmatrix}4/5 & 3/5 & 0 \\ 0 & 0 & -1 \\ 3/5 & -4/5 & 0 \end{bmatrix} \begin{bmatrix}5 & 5 & 0 \\ 0 & 35 & 0 \\ 0 & 0 & 2\end{bmatrix} =QR. $$ The commutative diagram is:

Gram Schmidt Process figure 2

Example. (a) Perform the Gram-Schmidt process on the vectors $$ v_1=\begin{bmatrix}1 \\ 7 \\ 1 \\ 7\end{bmatrix}, \qquad v_2= \begin{bmatrix}0 \\ 7 \\ 2 \\ 7\end{bmatrix}, \qquad v_3 = \begin{bmatrix}1 \\ 8 \\ 1 \\ 6\end{bmatrix}. $$ (b) Find the $QR$ factorization of the matrix $M=\begin{bmatrix} v_1 & v_2 & v_3\end{bmatrix}.$

By Gram-Schmidt Process, we determine $u_1, u_2, u_3$ as follows:

$$u_1 = \begin{bmatrix}1/10 \\ 7/10 \\ 1/10 \\ 7/10\end{bmatrix}, \quad u_2 = \frac{v_2^\perp }{ \left|\left|v_2^\perp\right|\right| } =\frac{v_2-\left(u_1 \cdot v_2\right) u_1 }{\left|\left|v_2-\left(u_1 \cdot v_2\right)u_1\right|\right|} =\begin{bmatrix}-1/\sqrt{2} \\ 0 \\ 1/\sqrt{2} \\ 0\end{bmatrix}, $$

and

$$ u_3=\frac{v_3^\perp}{\left|\left|v_3^\perp\right|\right|} =\frac{v_3-\left(u_1 \cdot v_3\right) u_1-\left(u_2 \cdot v_3\right) u_2 }{ \left|\left|v_3-\left(u_1 \cdot v_3\right) u_1-\left(u_2 \cdot v_3\right) u_2 \right|\right| } =\begin{bmatrix} 0 \\ 1/\sqrt{2} \\ 0 \\ -1/\sqrt{2}\end{bmatrix}. $$

Therefore an orthonormal basis for $\mathop{span} (v_1, v_2, v_3)$ is

$$ \left( \begin{bmatrix}1/10 \\ 7/10 \\ 1/10 \\ 7/10\end{bmatrix}, \begin{bmatrix}-1/\sqrt{2} \\ 0 \\ 1/\sqrt{2} \\ 0\end{bmatrix}, \begin{bmatrix}0 \\ 1/\sqrt{2} \\ 0 \\ -1/\sqrt{2}\end{bmatrix}\right). $$

Determining the entries of $R$ (also as determined above):

$$ \begin{array}{ccc} r_{11} = \left|\left| v_1\right|\right| =10, & r_{22}=\left|\left| v_2^\perp \right|\right| =\sqrt{2}, & r_{33} = \left|\left|v_3^\perp \right|\right|=\sqrt{2} \end{array} $$

$$ \begin{array}{ccc} r_{12}=u_1 \cdot v_2=10, & r_{13}=u_1 \cdot v_3=10, & r_{23}=u_2 \cdot v_3=0 \end{array} $$

and therefore, the $QR$-factorization of $M$ is

$$ M=\begin{bmatrix} 1 & 0 & 1 \\ 7 & 7 & 8 \\ 1 & 2 & 1 \\ 7 & 7 & 6 \end{bmatrix} = \begin{bmatrix}1/10 & -1/\sqrt{2} & 0 \\ 7/10 & 0 & 1/\sqrt{2} \\ 1/10 & 1/\sqrt{2} & 0 \\ 7/10 & 0 & -1/\sqrt{2}\end{bmatrix} \begin{bmatrix}10 & 10 & 10 \\ 0 & \sqrt{2} & 0 \\ 0 & 0 & \sqrt{2}\end{bmatrix} =QR. $$

The commutative diagram is

Gram Schmidt Process figure 3