# Gram-Schmidt Method

Page
The Gram-Schmidt Algorithm – HMC Calculus Tutorial

In any inner product space, we can choose the basis in which to work.

An inner product space is a real vector space $V$ with an inner product. Recall that an inner product $< \cdot, \cdot >$ is a function that, for each pair of vectors ${\bf u}, {\bf v} \in V$, assigns a real number in such a way that

1. $< {\bf u}, {\bf v} >\ =\ < {\bf v}, {\bf u} >$
2. $< {\bf u} + {\bf v}, {\bf w} >\ =\ < {\bf u}, {\bf w} > + < {\bf v}, {\bf w} > {\small\textrm{ for all }} {\bf w} \in V.$
3. $< k{\bf u}, {\bf v} >\ =\ k < {\bf u}, {\bf v} >$
4. $< {\bf v}, {\bf v} >\ \geq 0, {\small\textrm{ where }} < {\bf v}, {\bf v} >\ = 0 {\small\textrm{ if and only if }} {\bf v} = 0.$

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

According to the Projection Theorem, if $W$ is a finite dimensional subspace of an inner product space $V$ , then every vector ${\bf u} \in V$ can be expressed uniquely as $${\bf u} = {\bf w}_1 + {\bf w}_2,$$ where ${\bf w}_1 \in W$ and ${\bf w}_2$ is orthogonal to $W$. The vector ${\bf w}_1$ is called the orthogonal projection of ${\bf u}$ on $W$ and is denoted by ${\bf w}_1 = \textrm{proj}_{W} {\bf u}$.

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$