Gram-Schmidt Process and QR Factorization

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

David A. Smith at Dave4Math

David Smith (Dave) has a B.S. and M.S. in Mathematics and has enjoyed teaching precalculus, calculus, linear algebra, and number theory at both the junior college and university levels for over 20 years. David is the founder and CEO of Dave4Math.

Leave a Comment