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 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$