The Gram-Schmidt Algorithm

In any inner product space, we can choose the basis in which to work. It often greatly simplifies calculations to work in an orthogonal basis. For one thing, if $S = \{ {\bf v}_1, {\bf v}_2, \dots , {\bf v}_n \}$ is an orthogonal basis for an inner product space $V$, then it is a simple matter to express any vector ${\bf w} \in V$ as a linear combination of the vectors in $S$:
$$w=\frac{\langle {\bf w},{\bf v}_1\rangle}{\| {\bf v}_1 \|^{2}}{\bf v}_1 + \frac{\langle {\bf w},{\bf v}_2\rangle}{\| {\bf v}_2 \|^{2}}{\bf v}_2 + \cdots + \frac{\langle {\bf w},{\bf v}_n\rangle}{\| {\bf v}_n \|^{2}}{\bf v}_n.$$ Given an arbitrary basis $\{{\bf u}_1, {\bf u}_2, \ldots, {\bf u}_n\}$ for an $n$-dimensional inner product space $V$, the Gram-Schmidt algorithm constructs an orthogonal basis $\{{\bf v}_1, {\bf v}_2, \ldots, {\bf v}_n\}$ for $V$:
 That is, ${\bf w}$ has coordinates $$\left[\begin{array}{c} \frac{\langle {\bf w},{\bf v}_1\rangle}{\| {\bf v}_1 \|^{2}}{\bf v}_1\\ \frac{\langle {\bf w},{\bf v}_2\rangle}{\| {\bf v}_2 \|^{2}}{\bf v}_2\\ \vdots\\ \frac{\langle {\bf w},{\bf v}_n\rangle}{\| {\bf v}_n \|^{2}}{\bf v}_n \end{array} \right]$$ relative to the basis $S$.

Step 1 Let ${\bf v}_1 = {\bf u}_1$.

Step 2 Let ${\bf v}_2={\bf u}_2 - \mbox{proj}_{W_{1}}{\bf u}_2 = {\bf u}_2 - \frac{\langle {\bf u}_2,{\bf v}_1\rangle}{\| {\bf v}_1 \|^{2}}{\bf v}_1$ where $W_1$ is the space spanned by ${\bf v}_1$, and $\mbox{proj}_{W_{1}}{\bf u}_2$ is the orthogonal projection of ${\bf u}_2$ on $W_1$.

Step 3 Let ${\bf v}_3 = {\bf u}_3 - \mbox{proj}_{W_{2}} {\bf u}_3 = {\bf u}_3- \frac{\langle {\bf u}_3,{\bf v}_1\rangle}{\| {\bf v}_1 \|^{2}}{\bf v}_1 - \frac{\langle {\bf u}_3,{\bf v}_2\rangle}{\| {\bf v}_2 \|^{2}}{\bf v}_2$ where $W_2$ is the space spanned by ${\bf v}_1$ and ${\bf v}_2$.

Step 4 Let ${\bf v}_4 = {\bf u}_4 - \mbox{proj}_{W_{3}} {\bf u}_4 = {\bf u}_4- \frac{\langle {\bf u}_4,{\bf v}_1\rangle}{\| {\bf v}_1 \|^{2}}{\bf v}_1 - \frac{\langle {\bf u}_4,{\bf v}_2\rangle}{\| {\bf v}_2 \|^{2}}{\bf v}_2 - \frac{\langle {\bf u}_4,{\bf v}_3\rangle}{\| {\bf v}_3 \|^{2}}{\bf v}_3$ where $W_3$ is the space spanned by ${\bf v}_1, {\bf v}_2$ and ${\bf v}_3$.

$\vdots$

Continue this process up to ${\bf v}_n$. The resulting orthogonal set $\left\{{\bf v}_1,{\bf v}_2,\ldots,{\bf v}_n\right\}$ consists of $n$ linearly independent vectors in $V$ and so forms an orthogonal basis for $V$.

Notes
• To obtain an orthonormal basis for an inner product space $V$, use the Gram-Schmidt algorithm to construct an orthogonal basis. Then simply normalize each vector in the basis.

• For $R^{n}$ with the Eudlidean inner product (dot product), we of course already know of the orthonormal basis $\left\{ (1,0,0,\ldots,0), (0,1,0,\ldots,0), \ldots , (0, \ldots, 0,1)\right\}$. For more abstract spaces, however, the existence of an orthonormal basis is not obvious. The Gram-Schmidt algorithm is powerful in that it not only guarantees the existence of an orthonormal basis for any inner product space, but actually gives the construction of such a basis.

#### Example

Let $V=R^{3}$ with the Euclidean inner product. We will apply the Gram-Schmidt algorithm to orthogonalize the basis $\left\{ (1,-1,1),(1,0,1),(1,1,2)\right\}$.

Step 1 ${\bf v}_1 = (1,-1,1)$.

Step 2 $\begin{array}{rcl} {\bf v}_2 & = & (1,0,1) - \frac{(1,0,1) \cdot (1,-1,1)}{\|(1,-1,1)\|^{2}}(1,-1,1)\\ & = & (1,0,1) - \frac{2}{3}(1,-1,1)\\ & = & (\frac{1}{3},\frac{2}{3},\frac{1}{3}). \end{array}$

Step 3 $\begin{array}{rcl} {\bf v}_3 & = & (1,1,2) - \frac{(1,1,2) \cdot (1,-1,1)}{\|(1,-1,1)\|^{2}}(1,-1,1) - \frac{(1,1,2) \cdot (\frac{1}{3},\frac{2}{3},\frac{1}{3}) \strut}{\|(\frac{1}{3},\frac{2}{3},\frac{1}{3})\|^{2}} (\frac{1}{3},\frac{2}{3},\frac{1}{3}) \\ & = & (1,1,2) - \frac{2}{3}(1,-1,1)-\frac{5}{2}(\frac{1}{3},\frac{2}{3},\frac{1}{3})\\ & = & (\frac{-1}{2},0,\frac{1}{2}). \end{array}$

You can verify that $\left\{ (1,-1,1),(\frac{1}{3},\frac{2}{3},\frac{1}{3}),(\frac{-1}{2},0,\frac{1}{2})\right\}$ forms an orthogonal basis for $R^{3}$. Normalizing the vectors in the orthogonal basis, we obtain the orthonormal basis $$\left\{ \left( \frac{\sqrt{3}}{3}, \frac{-\sqrt{3}}{3}, \frac{\sqrt{3}}{3}\right), \left( \frac{\sqrt{6}}{6}, \frac{\sqrt{6}}{3}, \frac{\sqrt{6}}{6}\right), \left ( \frac{-\sqrt{2}}{2}, 0, \frac{\sqrt{2}}{2}\right) \right\}.$$

### Key Concepts

Given an arbitrary basis $\left\{ {\bf u}_1,{\bf u}_2,\ldots,{\bf u}_n\right\}$ for an $n$-dimensional inner product space $V$, the Gram-Schmidt algorithm constructs an orthogonal basis $\left\{ {\bf v}_1,{\bf v}_2,\ldots,{\bf v}_n\right\}$ for $V$:

Step 1 Let ${\bf v}_1 = {\bf u}_1$.

Step 2 Let ${\bf v}_2 = {\bf u}_2 - \frac{\langle {\bf u}_2,{\bf v}_1\rangle}{\| {\bf v}_1 \|^{2}}{\bf v}_1$.

Step 3 Let ${\bf v}_3 = {\bf u}_3- \frac{\langle {\bf u}_3,{\bf v}_1\rangle}{\| {\bf v}_1 \|^{2}}{\bf v}_1 - \frac{\langle {\bf u}_3,{\bf v}_2\rangle}{\| {\bf v}_2 \|^{2}}{\bf v}_2$.

$\vdots$