proof of Gram-Schmidt orthogonalization procedure

Note that, while we state the following as a theorem for the sake of logical completeness and to establish notation, our definition of Gram-Schmidt orthogonalization is wholly equivalent to that given in the defining entry.

Theorem.

(Gram-Schmidt Orthogonalization)Let ${\mathrm{\{}{\mathrm{u}}_{\mathrm{k}}\mathrm{\}}}_{k\mathrm{=}\mathrm{1}}^n$ be a basis for an inner product space $V$ with inner product . Define ${\mathrm{v}}_{\mathrm{1}}\mathrm{=}\frac{{\mathrm{u}}_{\mathrm{1}}}{\mathrm{\mid }\mathrm{\mid }{\mathrm{u}}_{\mathrm{1}}\mathrm{\mid }\mathrm{\mid }}$ and ${\mathrm{\{}{\mathrm{m}}_{\mathrm{k}}\mathrm{\}}}_{k\mathrm{=}\mathrm{2}}^n$ recursively by

(1)

where ${\mathrm{v}}_{\mathrm{k}}\mathrm{=}\frac{{\mathrm{m}}_{\mathrm{k}}}{\mathrm{\mid }\mathrm{\mid }{\mathrm{m}}_{\mathrm{k}}\mathrm{\mid }\mathrm{\mid }}$ for $\mathrm{2}\mathrm{\le }k\mathrm{\le }n$. Then ${\mathrm{\{}{\mathrm{v}}_{\mathrm{k}}\mathrm{\}}}_{k\mathrm{=}\mathrm{1}}^n$ is an orthonormal basis for $V$.

Proof.

We proceed by induction on $n$. In the case $n=1$, we suppose${\{{𝐮}_{𝐤}\}}_{k=1}^n={\{{𝐮}_{𝐤}\}}_{k=1}^1={𝐮}_{\mathrm{𝟏}}$ is a basis for the inner product space $V$. Letting ${𝐯}_{\mathrm{𝟏}}=\frac{{𝐮}_{\mathrm{𝟏}}}{\mid \mid {𝐮}_{\mathrm{𝟏}}\mid \mid }$, it is clear that ${𝐯}_{\mathrm{𝟏}}\in \mathrm{Span}\left({𝐮}_{\mathrm{𝟏}}\right)$, whence it follows that $\mathrm{Span}\left({𝐯}_{\mathrm{𝟏}}\right)=\mathrm{Span}\left({𝐮}_{\mathrm{𝟏}}\right)=V$. Thus ${𝐯}_{\mathrm{𝟏}}$ is an orthonormal basis for $V$, and the result holds for $n=1$. Now let $n\ge 1\in \mathbb{N}$, and suppose the result holds for arbitrary $n$. Let ${\{{𝐮}_{𝐤}\}}_{k=1}^{n+1}$ be a basis for an inner product space $V$. By the inductive hypothesis we may use ${\{{𝐮}_{𝐤}\}}_{k=1}^n$ to construct an orthonormal set of vectors ${\{{𝐯}_{𝐤}\}}_{k=1}^n$ such that $\mathrm{Span}\left({\{{𝐯}_{𝐤}\}}_{k=1}^n\right)=\mathrm{Span}\left({\{{𝐮}_{𝐤}\}}_{k=1}^n\right)$. In accordance with the procedure outlined in the statement of the theorem, let ${𝐦}_{𝐧+\mathrm{𝟏}}$ be defined as

First we show that the vectors ${𝐯}_{\mathrm{𝟏}},{𝐯}_{\mathrm{𝟐}},\mathrm{\dots },{𝐯}_{𝐧},{𝐦}_{𝐧+\mathrm{𝟏}}$ are mutually orthogonal.Consider the inner product of${𝐦}_{𝐧+\mathrm{𝟏}}$ with ${𝐯}_{𝐣}$ for $1\le j\le n$. By construction, we have

Now since ${\{{𝐯}_{𝐤}\}}_{k=1}^n$ is an orthonormal set of vectors, whence, each term in the summation on the right-hand side of the preceding equation will vanish except for the term where $i=j$. Thus by this and the preceding equation, we have

Thus ${𝐦}_{𝐧+\mathrm{𝟏}}$ is orthogonal to ${𝐯}_{𝐣}$ for $1\le j\le n$, so we may take ${𝐯}_{𝐧+\mathrm{𝟏}}=\frac{{𝐦}_{𝐧+\mathrm{𝟏}}}{\mid \mid {𝐦}_{𝐧+\mathrm{𝟏}}\mid \mid }$ to have ${\{{𝐯}_{𝐤}\}}_{k=1}^{n+1}$ an orthonormal set of vectors. Finally we show that ${\{{𝐯}_{𝐤}\}}_{k=1}^{n+1}$ is a basis for $V$.By construction, each ${𝐯}_{𝐤}$ is a linear combination of the vectors ${\{{𝐮}_{𝐤}\}}_{k=1}^{n+1}$, so we have $n+1$ orthogonal, hence linearly independent vectors in the $n+1$ dimensional space $V$, from which it follows that ${\{{𝐯}_{𝐤}\}}_{k=1}^{n+1}$ is a basis for $V$. Thus the result holds for $n+1$, and by the principle of induction, for all $n$.∎