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 $\\{\\mathbf{u_{k}}\\}_{k=1}^{n}$ be a basis for an inner product space $V$ with inner product $\\big{<},\\big{>}$ . Define $\\mathbf{v_{1}}=\\tfrac{\\mathbf{u_{1}}}{\\mid\\mid\\mathbf{u_{1}}\\mid\\mid}$ and $\\{\\mathbf{m_{k}}\\}_{k=2}^{n}$ recursively by

\\mathbf{m_{k}}=\\mathbf{u_{k}}-\\big{<}\\mathbf{u_{k}},\\mathbf{v_{1}}\\big{>}%\\mathbf{v_{1}}-\\big{<}\\mathbf{u_{k}},\\mathbf{v_{2}}\\big{>}\\mathbf{v_{2}}-%\\ldots-\\big{<}\\mathbf{u_{k}},\\mathbf{v_{k-1}}\\big{>}\\mathbf{v_{k-1}}\\text{,}

(1)

where $\\mathbf{v_{k}}=\\tfrac{\\mathbf{m_{k}}}{\\mid\\mid\\mathbf{m_{k}}\\mid\\mid}$ for $2\\leq k\\leq n$ . Then $\\{\\mathbf{v_{k}}\\}_{k=1}^{n}$ is an orthonormal basis for $V$ .

Proof.

We proceed by induction on $n$ . In the case $n=1$ , 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 $V$ . Letting $\\mathbf{v_{1}}=\\tfrac{\\mathbf{u_{1}}}{\\mid\\mid\\mathbf{u_{1}}\\mid\\mid}$ , it is clear that $\\mathbf{v_{1}}\\in\\operatorname{Span}\\big{(}\\mathbf{u_{1}}\\big{)}$ , whence it follows that $\\operatorname{Span}\\big{(}\\mathbf{v_{1}}\\big{)}=\\operatorname{Span}\\big{(}%\\mathbf{u_{1}}\\big{)}=V$ . Thus $\\mathbf{v_{1}}$ is an orthonormal basis for $V$ , and the result holds for $n=1$ . Now let $n\\geq 1\\in\\mathbb{N}$ , and suppose the result holds for arbitrary $n$ . Let $\\{\\mathbf{u_{k}}\\}_{k=1}^{n+1}$ be a basis for an inner product space $V$ . 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 $\\operatorname{Span}\\big{(}\\{\\mathbf{v_{k}}\\}_{k=1}^{n}\\big{)}=\\operatorname{%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

\\mathbf{u_{n+1}}-\\big{<}\\mathbf{u_{n+1}},\\mathbf{v_{1}}\\big{>}\\mathbf{v_{1}}-%\\big{<}\\mathbf{u_{n+1}},\\mathbf{v_{2}}\\big{>}\\mathbf{v_{2}}-\\ldots-\\big{<}%\\mathbf{u_{n+1}},\\mathbf{v_{n}}\\big{>}\\mathbf{v_{n}}=\\mathbf{u_{n+1}}-\\sum%\\limits_{i=1}^{n}\\big{<}\\mathbf{u_{n+1}},\\mathbf{v_{i}}\\big{>}\\mathbf{v_{i}}%\\text{.}

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

\\big{<}\\mathbf{m_{n+1}},\\mathbf{v_{j}}\\big{>}=\\biggl{<}\\mathbf{u_{n+1}}-\\sum_{%i=1}^{n}\\big{<}\\mathbf{u_{n+1}},\\mathbf{v_{i}}\\big{>}\\mathbf{v_{i}},\\mathbf{v_%{j}}\\biggr{>}=\\big{<}\\mathbf{u_{n+1}},\\mathbf{v_{j}}\\big{>}-\\biggl{<}\\sum%\\limits_{i=1}^{n}\\big{<}\\mathbf{u_{n+1}},\\mathbf{v_{i}}\\big{>}\\mathbf{v_{i}},%\\mathbf{v_{j}}\\biggr{>}\\text{.}

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 $i=j$ . Thus by this and the preceding equation, we have

\\displaystyle\\big{<}\\mathbf{m_{n+1}},\\mathbf{v_{j}}\\big{>}=\\big{<}\\mathbf{u_{n%+1}},\\mathbf{v_{j}}\\big{>}-\\biggl{<}\\sum\\limits_{i=1}^{n}\\big{<}\\mathbf{u_{n+1%}},\\mathbf{v_{i}}\\big{>}\\mathbf{v_{i}},\\mathbf{v_{j}}\\biggr{>}=\\big{<}\\mathbf{%u_{n+1}},\\mathbf{v_{j}}\\big{>}-\\biggl{<}\\big{<}\\mathbf{u_{n+1}},\\mathbf{v_{j}}%\\big{>}\\mathbf{v_{j}},\\mathbf{v_{j}}\\biggr{>}\\\\\\displaystyle=\\big{<}\\mathbf{u_{n+1}},\\mathbf{v_{j}}\\big{>}-\\big{<}\\mathbf{u_{%n+1}},\\mathbf{v_{j}}\\big{>}\\big{<}\\mathbf{v_{j}},\\mathbf{v_{j}}\\big{>}=\\big{<}%\\mathbf{u_{n+1}},\\mathbf{v_{j}}\\big{>}-\\big{<}\\mathbf{u_{n+1}},\\mathbf{v_{j}}%\\big{>}=0\\text{.}

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 $V$ .By construction, each $\\mathbf{v_{k}}$ is a linear combination of the vectors $\\{\\mathbf{u_{k}}\\}_{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 $\\{\\mathbf{v_{k}}\\}_{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$ .∎