In the previous lecture, we saw a few reasons why we would like to work with orthogonal bases:

• With an orthogonal basis, we can easily write a vector as a linear combination of the basis vectors.
• With an orthogonal basis, we can find the projection of a vector onto a subspace (which is the vector in the subspace closest to our given vector).

What we did not see is any explanation of how we can have an orthogonal basis. The process by which we construct an orthogonal basis for a space is called Gram-Schmidt Orthogonalization.

The key idea of Gram-Schmidt orthogonalization is from the previous lecture: given a vector $\large \vec{u}$ and a subspace $\large W$, we break $\large \vec{u}$ into a sum of vectors:

$$\large\vec{u}=\hat{u}+\vec{z}\quad \text{ where } \quad \hat{u}\in W \text{ and } \vec{z}\in W^\perp$$

Once we've split $\large \vec{u}$ in this way, we can remove the part of the vector that is not orthogonal to a subspace.

We will illustrate this algorithm first with an example, and then we will generalize it.

We start with a set of linearly independent vectors:

$$\large \vec{x}_1=\begin{bmatrix} 1\\ 1\\ 1\\ 1\\ \end{bmatrix}, \vec{x}_2=\begin{bmatrix} 0\\ 1\\ 1\\ 1\\ \end{bmatrix}, \vec{x}_3=\begin{bmatrix} 0\\ 0\\ 1\\ 1\\ \end{bmatrix} $$

This set is linearly independent, so it is a basis for $\large W=\text{Span}\lbrace \vec{x}_1,\vec{x}_2,\vec{x}_3 \rbrace$. But it is not an orthogonal basis. We'll use it in the Gram-Schmidt process to get an orthogonal basis for $\large W$. The steps are explained here:

1. We are building a set of vectors, and we have to start somewhere. So we get started with the following definitions. Note that $\large W_1$ is a subspace of $\large W$:

$$\large \vec{v}_1=\vec{x}_1, \quad \large W_1 = \text{Span}\lbrace \vec{v}_1 \rbrace$$

2. Now, we need a second vector orthogonal to the first. We will remove the portion of $\large \vec{x}_2$ that lies in $\large W_1$, leaving only a vector orthogonal to $\large W_1$ (and therefore, orthogonal to $\large \vec{v}_1$).

$$\large\displaystyle \vec{v}_2=\vec{x}_2-\text{proj}_{W_1}\vec{x}_2=\vec{x}_2-\frac{\vec{x}_2\cdot\vec{v}_1}{\lVert \vec{v}_1 \rVert ^2}\vec{v}_1, \quad W_2=\text{Span}\lbrace \vec{v}_1,\vec{v}_2 \rbrace$$

This is:

$$\large \vec{v}_2=\begin{bmatrix} 0\\ 1\\ 1\\ 1\\ \end{bmatrix}-\frac{3}{4}\begin{bmatrix} 1\\ 1\\ 1\\ 1\\ \end{bmatrix}=\begin{bmatrix} -3/4\\ 1/4\\ 1/4\\ 1/4\\ \end{bmatrix} $$

We now have two orthogonal vectors in $\large \vec{v}_1$ and $\large \vec{v}_2$, and we defined a subspace that includes both of them. Go ahead and double check that $\large \vec{v}_1$ and $\large \vec{v}_2$ are orthogonal.

3. (Optional Step). We can scale $\large \vec{v}_2$, and it will still be orthogonal to $\large \vec{v}_1$. Since we're doing this by hand, we'll scale it to get rid of the fractions (when we have the computer do this, we don't scale it since the computer doesn't dislike fractions like we do).

$$\large \vec{v}_2\Rightarrow\begin{bmatrix} -3\\ 1\\ 1\\ 1\\ \end{bmatrix} $$

4. We follow our pattern and remove the part of $\large\vec{x}_3$ that is aligned with $\large\vec{v}_1$ and $\large \vec{v}_2$, leaving a $\large \vec{v}_3$ that is orthogonal to both.

$$\large\displaystyle \vec{v}_3=\vec{x}_3-\text{proj}_{W_2}\vec{x}_3=\vec{x}_3-\left(\frac{\vec{x}_3\cdot\vec{v}_1}{\lVert \vec{v}_1 \rVert ^2}\vec{v}_1+\frac{\vec{x}_3\cdot\vec{v}_2}{\lVert \vec{v}_2 \rVert ^2}\vec{v}_2\right)$$

This is:

$$\large \vec{v}_3=\begin{bmatrix} 0\\ 0\\ 1\\ 1\\ \end{bmatrix}-\frac{2}{4}\begin{bmatrix} 1\\ 1\\ 1\\ 1\\ \end{bmatrix}-\frac{2}{12}\begin{bmatrix} -3\\ 1\\ 1\\ 1\\ \end{bmatrix} =\begin{bmatrix} 0\\ -2/3\\ 1/3\\ 1/3\\ \end{bmatrix} $$

We now have three orthogonal (and, therefore, linearly independent) vectors in a 3 dimensional subspace, so this set $\large \lbrace \vec{v}_1,\vec{v}_2,\vec{v}_3\rbrace$ is an orthogonal basis for $\large W$.

The general algorithm follows the pattern established in the example. At each step, we remove from our vector any part aligned with the vectors in our growing basis, leaving something completely orthogonal to what we've built so far.

We start with a subspace and a set of linearly independent vectors: $\large W=\text{Span}\lbrace \vec{x}_1,\vec{x}_2,\dots,\vec{x}_m\rbrace$.

• Define $\large \vec{v}_1$ and $\large W_1$ to get started:

$$\large\displaystyle \vec{v}_1=\vec{x}_1, \quad \large W=\text{Span}\lbrace \vec{v}_1\rbrace $$

• Subtract off of $\large \vec{x}_2$ the component that is in $\large W_1$, leaving a $\large \vec{v}_2$ that is orthogonal to $\large W_1$:

$$\large\displaystyle \vec{v}_2=\vec{x}_2-\text{proj}_{W_1}\vec{x}_2=\vec{x}_2-\frac{\vec{x}_2\cdot\vec{v}_1}{\lVert \vec{v}_1 \rVert ^2}\vec{v}_1, \quad W_2=\text{Span}\lbrace \vec{v}_1,\vec{v}_2 \rbrace $$

• Subtract off of $\large \vec{x}_3$ the component that is in $\large W_2$, leaving a $\large \vec{v}_3$ that is orthogonal to everything in $\large W_2$:

$$\large\displaystyle \vec{v}_3=\vec{x}_3-\text{proj}_{W_2}\vec{x}_3=\vec{x}_3-\frac{\vec{x}_3\cdot\vec{v}_1}{\lVert \vec{v}_1 \rVert ^2}\vec{v}_1-\frac{\vec{x}_3\cdot\vec{v}_2}{\lVert \vec{v}_2 \rVert ^2}\vec{v}_2, \quad W_3=\text{Span}\lbrace \vec{v}_1,\vec{v}_2,\vec{v}_3 \rbrace $$

$$\vdots$$

• Subtract off of $\large \vec{x}_m$ the component that is in the $\large (m-1)^{st}$ subspace, leaving a $\large \vec{v}_m$ that is orthogonal to everything in the $\large (m-1)^{st}$ subspace:

$$\large \vec{v}_{m}=\vec{x}_m-\text{proj}_{W_{m-1}}\vec{x}_m=\vec{x}_{m}-\frac{\vec{x}_{m}\cdot\vec{v}_{1}}{\lVert\vec{v}_{1}\rVert ^2}\vec{v}_{1}-\dots-\frac{\vec{x}_{m}\cdot\vec{v}_{m-1}}{\lVert \vec{v}_{m-1}\rVert ^2}\vec{v}_{m-1}$$

At the end of this process, we have an orthogonal basis $\large \lbrace \vec{v}_1,\vec{v}_2,\dots,\vec{v}_m\rbrace$ of $\large W$.

The following .gif illustrates the Gram-Schmidt process for a set of three vectors in $\large \mathbb{R}^3$. It starts by making green orthogonal to red, and then it makes blue orthogonal to both:

If we need an orthonormal basis instead of just an orthogonal basis, we simply normalize each vector at the end (divide each vector by its length).

I can:

• Use Gram-Schmidt algorithm to generate an orthogonal/orthonormal basis.