1.9 Gram-schmidt process

The Gram-Schmidt algorithm or procedure is used to find an orthonormal basis for the subspace $\left[S\right]$ , even if $S$ is not linearly independent. The algorithm is formally defined as follows:

• Inputs : Set of vectors $S=\left\{s_1,,,\cdots ,,,s_n\right\}$ .
• Outputs : Orthonormal basis elements $W=\left\{w_1,,,\cdots ,,,w_n\right\}$ that span the same space: $\left[W\right]=\left[S\right]$ .
• Procedure:
  1. Take the first element of the set and divide it by its norm (that is, normalize the element):
     $$w_1=\frac{s_1}{\parallel s_1\parallel }.$$
  2. Take the second element and subtract the projection into the first basis element:
     $$t_2=s_2-〈s_2,,,w_1〉w_1.$$
     Normalize the result $t_2$ :
     $$w_2=\frac{t_2}{\parallel t_2\parallel }.$$
     It is easy to check that $w_1$ and $w_2$ are orthonormal:
     $$\begin{array}{cc}\hfill 〈w_1,,,w_2〉& =〈w_1,,,\frac{t_2}{\parallel t_2\parallel }〉=\frac{1}{\parallel t_2\parallel }〈w_1,,,s_2,-,〈s_2,,,w_1〉,w_1〉\hfill \\ & =\frac{1}{\parallel t_2\parallel }\left(〈w_1,,,s_2〉,-,\overline{〈s_2,,,w_1〉},〈w_1,,,w_1〉\right)=\frac{1}{\parallel t_2\parallel }\left(〈w_1,,,s_2〉,-,\overline{〈s_2,,,w_1〉}\right)\hfill \\ & =\frac{1}{\parallel t_2\parallel }·0=0.\hfill \end{array}$$
     Thus, $w_1$ and $w_2$ are orthonormal.
  3. The second step is repeated for each additional element; $i^{th}$ element follows the following formula:
     $$\begin{array}{cc}\hfill t_i& =s_i-\sum _{j=1}^{i-1}〈s_i,,,w_j〉w_j,\hfill \\ \hfill w_i& =\frac{t_i}{\parallel t_i\parallel }.\hfill \end{array}$$

When the set $S$ includes linearly dependent vectors, some of the unnormalized vectors $t_i=0$ , as the projections will cancel out with some elements of $S$ . As a result, the number of vectors needed will be higher than the dimensionality of the space; in other words, the dimensionality of $\left[S\right]$ will be smaller than the cardinality of the set $\left|S\right|$ .

Example 1 Let $S=\left\{1,,,t,,,t^2\right\}$ , where $s_1=1$ , $s_2=t$ and $s_3=t^2$ . We can therefore write the set of quadratic functions as $Q=\left[S\right]$ , and $S\subseteq C\left(T\right)$ , where $T=[0,1]$ . Recall that for this space, the inner product is written as $〈x,,,y〉={\int }_0^{1}x\left(t\right)y\left(t\right)dt.$ We obtain a basis for $Q$ using the Gram-Schmidt procedure: it requires us to compute several norms and inner products on the way.

1. Solve for $w_1:$ $\parallel s_1\parallel =\sqrt{⟨s_1,s_1⟩}=\sqrt{{\int }_0^{1}1·1dt}=1,$ and so $w_1\left(t\right)=\frac{s_1\left(t\right)}{\parallel s_1\parallel }=\frac{1}{1}=1$ .
2. Solve for $w_2:$
   $$\begin{array}{cc}\hfill 〈s_2,,,w_1〉& ={\int }_0^{1}t·1dt={\left(\frac{t^2}{2}\right|}_{t=[0,1]}=\frac{1}{2},\hfill \\ \hfill t_2\left(t\right)& =s_2\left(t\right)-⟨s_2,w_1⟩w_1\left(t\right)=t-\frac{1}{2}·1=t-\frac{1}{2},\hfill \\ \hfill \parallel t_2\parallel & =\sqrt{〈t_2,,,t_2〉}=\sqrt{{\int }_0^1\left(t,-,\frac{1}{2}\right)·\left(t,-,\frac{1}{2}\right)dt}\hfill \\ & =\sqrt{{\int }_0^1\left(t^2,-,t,+,\frac{1}{4}\right)dt}=\sqrt{\left(\frac{t^3}{3},-,\frac{t^2}{2},+,\frac{t}{4}\right){|}_{t=[0,1]}}=\sqrt{\frac{1}{12}},\hfill \\ \hfill w_2& =\frac{t-\frac{1}{2}}{\sqrt{\frac{1}{12}}}=\sqrt{12}t-\frac{\sqrt{12}}{2}=2\sqrt{3}t-\sqrt{3}.\hfill \end{array}$$
   It is easy to check that $w_2$ has unit norm and is orthogonal to $w_1$ .
3. Solve for $w_3:$
   $$\begin{array}{cc}\hfill 〈s_3,,,w_1〉& ={\int }_0^1{t}^2·1dt=\frac{t^3}{3}{|}_{t=[0,1]}=\frac{1}{3},\hfill \\ \hfill 〈s_3,,,w_2〉& ={\int }_0^1{t}^2·\left(2,\sqrt{3},t,-,\sqrt{3}\right)dt=\left(\frac{\sqrt{3}}{2},t^4,-,\frac{1}{\sqrt{3}},t^3\right){|}_{t=[0,1]}=\frac{1}{2\sqrt{3}},\hfill \\ \hfill t_3& =s_3-〈s_3,,,w_1〉w_1-〈s_3,,,w_2〉w_2=t^2-\frac{1}{3}-\frac{1}{2\sqrt{3}}·\left(2,t,\sqrt{3},-,\sqrt{3}\right)\hfill \\ & =t^2-t-\frac{1}{6},\hfill \\ \hfill \parallel t_3\parallel & =\sqrt{〈t_3,,,t_3〉}=\sqrt{{\int }_0^1{\left(t^2,-,t,-,\frac{1}{6}\right)}^{2}dt},\hfill \\ \hfill w_3\left(t\right)& =\frac{t_3}{\parallel t_3\parallel }.\hfill \end{array}$$
   We can check that $\left[W\right]=Q.$