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\}. $$

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$