# 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