Gram-Schmidt Process (G.S)

The Gram-Schmidt process is a method for orthonormalizing a set of vectors in an vector space, most commonly the Euclidean space ${\mathbb{R}}^n$. The process takes a finite, linearly independent set of vectors and generates an orthogonal basis for the subspace spanned by those vectors.

Process

Given a basis $\beta$ of the subspace $V$, the G.S. process will construct an orthogonal basis using the basis $\beta$.

Consider the following set if $\beta =\{\overrightarrow{v_1},\overrightarrow{v_2},\dots ,\overrightarrow{v_k}\}$ in ${\mathbb{R}}^n$.

1. Set $\overrightarrow{u_1}=\overrightarrow{v_1}$
2. For $j=2$ to $k$:

Compute the projection of $\overrightarrow{v_j}$ onto each of the previous $\overrightarrow{u_i}$:

$${\text{proj}}_{\overrightarrow{u_i}}(\overrightarrow{v_j})=\frac{\overrightarrow{v_j}\cdot \overrightarrow{u_i}}{\overrightarrow{u_i}\cdot \overrightarrow{u_i}}\overrightarrow{u_i}$$

Subtract these projections from $\overrightarrow{v_j}$ to get $\overrightarrow{u_j}$:

$$\overrightarrow{u_j}=\overrightarrow{v_j}-\sum _{i=1}^{j-1}{\text{proj}}_{\overrightarrow{u_i}}(\overrightarrow{v_j})$$

4. (Optional) Normalize each $\overrightarrow{u_j}$ to get an orthonormal set $\{\overrightarrow{e_1},\overrightarrow{e_2},\dots ,\overrightarrow{e_k}\}$:

$$\overrightarrow{e_j}=\frac{\overrightarrow{u_j}}{\Vert \overrightarrow{u_j}\Vert }$$

Example

Consider the following basis:

$$\beta =\left\{\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right],\left[\begin{array}{c}0\\ 1\\ 1\\ 1\end{array}\right],\left[\begin{array}{c}0\\ 0\\ 1\\ 1\end{array}\right]\right\}$$

The process is as follows

$$\overrightarrow{u_1}=\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]$$ $$\overrightarrow{v_2}=\overrightarrow{u_2}-{\mathrm{proj}}_{W_1}\overrightarrow{u_2}=\left[\begin{array}{c}0\\ 1\\ 1\\ 1\end{array}\right]-\frac{\left[\begin{array}{c}0\\ 1\\ 1\\ 1\end{array}\right]\cdot \left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]}{\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]\cdot \left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]}\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]=\left[\begin{array}{c}-\frac{3}{4}\\ \frac{1}{4}\\ \frac{1}{4}\\ \frac{1}{4}\end{array}\right]$$

As this is a basis, we can also set and multiply $\overrightarrow{v_2}$ by some constant $k$ to simplicity.

$$\overrightarrow{u_2}=k\overrightarrow{v_2}=\left[\begin{array}{c}-3\\ 1\\ 1\\ 1\end{array}\right]$$

Now we continue

$$\overrightarrow{v_3}=\overrightarrow{u_3}-{\mathrm{proj}}_{W_1}\overrightarrow{u_3}-{\mathrm{proj}}_{W_2}\overrightarrow{u_3}=\left[\begin{array}{c}0\\ 0\\ 1\\ 1\end{array}\right]-\frac{\left[\begin{array}{c}0\\ 0\\ 1\\ 1\end{array}\right]\cdot \left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]}{\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]\cdot \left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]}\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]-\frac{\left[\begin{array}{c}0\\ 0\\ 1\\ 1\end{array}\right]\cdot \left[\begin{array}{c}-3\\ 1\\ 1\\ 1\end{array}\right]}{\left[\begin{array}{c}-3\\ 1\\ 1\\ 1\end{array}\right]\cdot \left[\begin{array}{c}-3\\ 1\\ 1\\ 1\end{array}\right]}\left[\begin{array}{c}-3\\ 1\\ 1\\ 1\end{array}\right]=\left[\begin{array}{c}\frac{2}{3}\\ -\frac{2}{3}\\ \frac{2}{3}\\ \frac{2}{3}\end{array}\right]$$ $$\overrightarrow{u_3}=k\overrightarrow{v_3}=\left[\begin{array}{c}2\\ -2\\ 2\\ 2\end{array}\right]$$

The orthogonal basis is now

$${\beta }_{orthogonal}=\left\{\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right],\left[\begin{array}{c}-3\\ 1\\ 1\\ 1\end{array}\right],\left[\begin{array}{c}2\\ -2\\ 2\\ 2\end{array}\right]\right\}$$

The General Case

Given $V$, a subspace of ${\mathbb{R}}^n$, and $\{\overrightarrow{v_1},\overrightarrow{v_2},\dots ,\overrightarrow{v_k}\}$, we construct an orthogonal basis with the process:

$$\begin{array}{rl}\overrightarrow{u_1}& =\overrightarrow{v_1}\\ \overrightarrow{u_2}& =\overrightarrow{v_2}-{\mathrm{proj}}_{W_1}\overrightarrow{v_2}\\ \overrightarrow{u_3}& =\overrightarrow{v_3}-{\mathrm{proj}}_{W_1}\overrightarrow{v_3}-{\mathrm{proj}}_{W_2}\overrightarrow{v_3}\\ \dots & \\ \overrightarrow{u_k}& =\overrightarrow{v_k}-{\mathrm{proj}}_{W_1}\overrightarrow{v_k}-{\mathrm{proj}}_{W_2}\overrightarrow{v_k}-\cdots -{\mathrm{proj}}_{W_{k-1}}\overrightarrow{v_k}\end{array}$$

Or in other words

$$\overrightarrow{v_k}=\overrightarrow{u_k}+\sum _{i=1}^{k-1}{\mathrm{proj}}_{W_i}\overrightarrow{v_k}$$