PlanetMath: 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.

Proof. We proceed by induction on

. In the case

, we suppose $\{\mathbf{u_k}\}_{k=1}^n=\{\mathbf{u_k}\}_{k=1}^1=\mathbf{u_1}$ is a basis for the inner product space

. Letting $\mathbf{v_1}=\tfrac{\mathbf{u_1}}{\mid\mid\mathbf{u_1}\mid\mid}$ , it is clear that $\mathbf{v_1}\in {\mathrm{Span}}\big(\mathbf{u_1}\big)$ , whence it follows that ${\mathrm{Span}}\big(\mathbf{v_1}\big)={\mathrm{Span}}\big(\mathbf{u_1}\big)=V$ . Thus $\mathbf{v_1}$ is an orthonormal basis for

, and the result holds for

. Now let $n\geq 1\in\mathbb{N}$ , and suppose the result holds for arbitrary

. Let $\{\mathbf{u_k}\}_{k=1}^{n+1}$ be a basis for an inner product space

. By the inductive hypothesis we may use $\{\mathbf{u_k}\}_{k=1}^n$ to construct an orthonormal set of vectors $\{\mathbf{v_k}\}_{k=1}^n$ such that ${\mathrm{Span}}\big(\{\mathbf{v_k}\}_{k=1}^n\big)={\mathrm{Span}}\big(\{\mathbf{u_k}\}_{k=1}^n\big)$ . In accordance with the procedure outlined in the statement of the theorem, let $\mathbf{m_{n+1}}$ be defined as

$\displaystyle \mathbf{u_{n+1}}- \big<\mathbf{u_{n+1}},\mathbf{v_1}\big>\mathbf{... ..._{n+1}}-\sum\limits_{i=1}^n \big<\mathbf{u_{n+1}},\mathbf{v_i}\big>\mathbf{v_i}$ .

First we show that the vectors $\mathbf{v_1},\mathbf{v_2},\ldots,\mathbf{v_n},\mathbf{m_{n+1}}$ are mutually orthogonal. Consider the inner product of $\mathbf{m_{n+1}}$ with $\mathbf{v_j}$ for $1\leq j\leq n$ . By construction, we have

$\displaystyle \big<\mathbf{m_{n+1}},\mathbf{v_j}\big>=\biggl<\mathbf{u_{n+1}} -... ...{i=1}^n\big<\mathbf{u_{n+1}},\mathbf{v_i}\big> \mathbf{v_i},\mathbf{v_j}\biggr>$ .

Now since $\{\mathbf{v_k}\}_{k=1}^n$ is an orthonormal set of vectors, whence $\big<\mathbf{v_i},\mathbf{v_j}\big>=\delta_{ij}$ , each term in the summation on the right-hand side of the preceding equation will vanish except for the term where

. Thus by this and the preceding equation, we have

$\begin{multline*} \big<\mathbf{m_{n+1}},\mathbf{v_j}\big> =\big<\mathbf{u_{n+1}}... ..._{j}}\big> -\big<\mathbf{u_{n+1}},\mathbf{v_{j}}\big> =0\text{.} \end{multline*}$

Thus $\mathbf{m_{n+1}}$ is orthogonal to $\mathbf{v_j}$ for $1\leq j\leq n$ , so we may take $\mathbf{v_{n+1}}=\tfrac{\mathbf{m_{n+1}}}{\mid\mid\mathbf{m_{n+1}}\mid\mid}$ to have $\{\mathbf{v_k}\}_{k=1}^{n+1}$ an orthonormal set of vectors. Finally we show that $\{\mathbf{v_k}\}_{k=1}^{n+1}$ is a basis for

. By construction, each $\mathbf{v_k}$ is a linear combination of the vectors $\{\mathbf{u_k}\}_{k=1}^{n+1}$ , so we have

orthogonal, hence linearly independent vectors in the

dimensional space

, from which it follows that $\{\mathbf{v_k}\}_{k=1}^{n+1}$ is a basis for

. Thus the result holds for

, and by the principle of induction, for all

. $\qedsymbol$