TheoremGram-Schmidt orthonormalization

Given an ordered linearly independent set \(\EuScript{A}\DefEq (\Vect{a}_1,\dots ,\Vect{a}_r)\) of vectors in \(\RNrSpc{n}\), the ordered set of vectors \(\EuScript{B}\DefEq (\Vect{v}_1,\dots ,\Vect{v}_r)\) defined below is an ordered ONB of \(\span(\EuScript{A})\).

\(\Vect{v}_1\)\(\DefEq \)\(\dfrac{ \Vect{a}_1 }{ \Norm{ \Vect{a}_1} }\)
\(\Vect{v}_2\)\(\DefEq \)\(\dfrac{ \Vect{a}_2 - (\DotPr{ \Vect{a}_2 }{ \Vect{v}_1 })\Vect{v}_1 }{ \Norm{ \Vect{a}_2 - (\DotPr{ \Vect{a}_2 }{ \Vect{v}_1 })\Vect{v}_1} }\)
\(\vdots\)\(\)\(\qquad \vdots \qquad\qquad \vdots\)
\(\Vect{v}_r\)\(\DefEq \)\(\dfrac{ \Vect{a}_r - (\DotPr{ \Vect{a}_r }{ \Vect{v}_1 })\Vect{v}_1 - (\DotPr{ \Vect{a}_r }{ \Vect{v}_2 })\Vect{v}_2 - \cdots - (\DotPr{ \Vect{a}_r }{ \Vect{v}_{r-1} })\Vect{v}_{r-1} }{ \Norm{ \Vect{a}_r - (\DotPr{ \Vect{a}_r }{ \Vect{v}_1 })\Vect{v}_1 - (\DotPr{ \Vect{a}_r }{ \Vect{v}_2 })\Vect{v}_2 - \cdots - (\DotPr{ \Vect{a}_r }{ \Vect{v}_{r-1} })\Vect{v}_{r-1} } }\)

Moreover, \(\span\Set{ \Vect{a}_1,\dots ,\Vect{a}_j } = \span\Set{ \Vect{v}_1,\dots ,\Vect{v}_j }\) for each \(1\leq j\leq r\) and, if \(\Vect{a}_1,\dots ,\Vect{a}_j\) are already orthonormal, then \(\Vect{a}_k=\Vect{v}_k\) for each \(1\leq k\leq j\).

Proof

We prove the theorem by induction on \(r\). If \(r=1\), \(\EuScript{B}_1 \DefEq ( \Vect{v}_1 )\) is an ordered ONB of \(\span\Set{ \Vect{a}_1 }\) for the following reasons:

  1. the definition of \(\Vect{v}_1\) is valid since \(\Vect{a}_1\neq \Vect{0}\).
  2. \(\span\Set{ \Vect{v}_1 } = \span\Set{ \Vect{a}_1 }\) because \(t \Vect{a}_1 = (t \Norm{ \Vect{a}_1 }) \Vect{v}_1\) for all \(t\in \RNr\)
  3. \(\EuScript{B}_1\) is linearly independent since \(\Norm{ \Vect{v}_1 } = 1\).

So suppose the theorem is true for \( 1\leq (j-1) < r \). We need to deduce that the theorem is true for \(j\). The induction hypothesis tells us that, \(\EuScript{B}_{j-1} \DefEq (\Vect{v}_1,\dots ,\Vect{v}_{j-1})\) is an ordered ONB of \(\EuScript{A}_{j-1}\DefEq \span\Set{ \Vect{a}_1,\dots ,\Vect{a}_{j-1} }\). Therefore the following hold

  1. \(\Vect{a}_j - (\DotPr{ \Vect{a}_j }{ \Vect{v}_1 })\Vect{v}_1 - \cdots - (\DotPr{ \Vect{a}_j }{ \Vect{v}_{j-1} })\Vect{v}_{j-1}\neq \Vect{0}\), and so the definition of \(\Vect{v}_j\) is valid

  2. \(\EuScript{A}_{j}\DefEq \span\Set{ \Vect{a}_1,\dots ,\Vect{a}_j} \subseteq \span\Set{ \Vect{v}_1,\dots ,\Vect{v}_{j-1} }=:\EuScript{B}_j\). To see this, it only remains to show that \(\Vect{a}_j\in \span(\EuScript{B}_j)\). Indeed, the defining equation for \(\Vect{v}_j\) yields

    \(\Vect{v}_j\)\(=\)\((\DotPr{ \Vect{a}_j }{ \Vect{v}_1 })\Vect{v}_1 + \cdots + (\DotPr{ \Vect{a}_j }{ \Vect{v}_{j-1} })\Vect{v}_{j-1} + s \Vect{v}_j\)

    where \(s=\Norm{ \Vect{a}_j - (\DotPr{ \Vect{a}_j }{ \Vect{v}_1 })\Vect{v}_1 - \cdots - (\DotPr{ \Vect{a}_j }{ \Vect{v}_{j-1} })\Vect{v}_{j-1}}\). Therefore, \(\span(\EuScript{A}_j) \subseteq \span( \EuScript{B}_j)\).

  3. Conversely, \(\span(\EuScript{B}_j)\subseteq \span(\EuScript{A}_j)\): Indeed, \(\span(\EuScript{B}_{j-1})=\span(\EuScript{A}_{j-})\) by induction hypothesis, and \(\span(\EuScript{A}_{j-1})\subset \span(\EuScript{A}_j)\). So, \(\Vect{v}_r\) is a linear combination of vectors in \(\span(\EuScript{A}_j)\).
  4. So \(\span(\EuScript{A}_j)=\span(\EuScript{B}_j)\).
  5. \(\EuScript{B}_j\) is an orthonormal set of vectors: In view of the induction hypothesis it only remains to show that \(\Norm{ \Vect{v}_j } = 1\), which holds by design, and that \(\DotPr{ \Vect{v}_j }{ \Vect{v}_k } = 0\) for \(1\leq k\leq j-1\). We find
    \(\DotPr{ \Vect{v}_j }{ \Vect{v}_k }\)\(=\)\((1/s)\left( \DotPr{ \Vect{a}_j }{ \Vect{v}_k } - (\DotPr{ \Vect{a}_j }{ \Vect{v}_1 }(\DotPr{ \Vect{v}_1 }{ \Vect{v}_k }) - \cdots - (\DotPr{ \Vect{a}_j }{ \Vect{v}_k }(\DotPr{ \Vect{v}_k }{ \Vect{v}_k })\right.\)
    \(\)\(\)\(\left.\qquad - \cdots - (\DotPr{ \Vect{a}_j }{ \Vect{v}_{j-1} }(\DotPr{ \Vect{v}_{j-1} }{ \Vect{v}_k })\right)\)
    \(\)\(=\)\((1/s)(\DotPr{ \Vect{a}_j }{ \Vect{v}_k } - \DotPr{ \Vect{a}_j }{ \Vect{v}_k })\)
    \(\)\(=\)\(0\)

It only remains to consider the situation where \(\EuScript{A}_j\) is already orthonormal. By induction hypothesis, \(\Vect{a}_1=\Vect{v}_1\), \(\Vect{a}_{j-1}=\Vect{v}_{j-1}\). In the defining formula for \(\Vect{v}_j\), we find \(\DotPr{ \Vect{a}_j }{ \Vect{v}_k }=0\), for \(1\leq k\leq j-1\). Therefore

\(\Vect{v}_j\)\(=\)\(\Vect{a}_j/\Norm{ \Vect{a}_j } = \Vect{a}_j\)

This completes the induction and, with it, the proof of the validity of the Gram-Schmidt orthonormalization procedure.