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$, which means all pairs of distinct vectors in S are orthogonal: $$ < {\bf v}_i, {\bf v}_j >\ = 0 {\small\textrm{ for all }} {\bf v}_i, {\bf v}_j \in S. $$
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, which is an orthogonal set in which each vector has norm 1, 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 algorithmconstructs 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$