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$ . ∎

Title	proof of Gram-Schmidt orthogonalization procedure
Canonical name	ProofOfGramSchmidtOrthogonalizationProcedure
Date of creation	2013-03-22 16:27:17
Last modified on	2013-03-22 16:27:17
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	11
Author	rspuzio (6075)
Entry type	Proof
Classification	msc 65F25
Synonym	Gram-Schmidt
Synonym	orthogonalization
Related topic	GramSchmidtOrthogonalization
Related topic	ExampleOfGramSchmidtOrthogonalization
Related topic	InnerProductSpace
Related topic	InnerProduct
Related topic	QRDecomposition
Related topic	NormedVectorSpace
Related topic	Orthogonal
Related topic	OrthogonalVectors
Related topic	Basis
Related topic	Span
Related topic	LinearIndependence
Related topic	Orthonormal
Related topic	OrthonormalBasis
Defines	Gram-Schmidt orthogonalization