Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

9.5: The Gram-Schmidt Orthogonalization procedure

( \newcommand{\kernel}{\mathrm{null}\,}\)

We now come to a fundamentally important algorithm, which is called the Gram-Schmidt orthogonalization procedure. This algorithm makes it possible to construct, for each list of linearly independent vectors (resp. basis), a corresponding orthonormal list (resp. orthonormal basis).

Theorem 9.5.1

If (v1,,vm) is a list of linearly independent vectors in V, then there exists an orthonormal list (e1,,em) such that

span(v1,,vk)=span(e1,,ek),for all k=1,,m.

Proof

The proof is constructive, that is, we will actually construct vectors e1,,em having the desired properties. Since (v1,,vm) is linearly independent, vk0 for each k=1,2,,m. Set e1=v1v1. Then e1 is a vector of norm 1 and satisfies Equation (9.5.1) for k=1. Next, set

e2=v2v2,e1e1v2v2,e1e1.

This is, in fact, the normalized version of the orthogonal decomposition Equation(9.3.1)~(???). I.e.,

w=v2v2,e1e1,

where we1. Note that e2=1 and span(e1,e2)=span(v1,v2).

Now, suppose that e1,,ek1 have been constructed such that (e1,,ek1) is an orthonormal list and span(v1,,vk1)=span(e1,,ek1). Then define
ek=vkvk,e1e1vk,e2e2vk,ek1ek1vkvk,e1e1vk,e2e2vk,ek1ek1.

Since (v1,,vk) is linearly independent, we know that vkspan(v1,,vk1). Hence, we also know that vkspan(e1,,ek1). It follows that the norm in the definition of ek is not zero, and so ek is well-defined (i.e., we are not dividing by zero). Note that a vector divided by its norm has norm 1 so that ek=1. Furthermore,

ek,ei=vkvk,e1e1vk,e2e2vk,ek1ek1vkvk,e1e1vk,e2e2vk,ek1ek1,ei=vk,eivk,eivkvk,e1e1vk,e2e2vk,ek1ek1=0,

for each 1i<k. Hence, (e1,,ek) is orthonormal.

From the definition of ek, we see that vkspan(e1,,ek) so that span(v1,,vk)span(e1,,ek). Since both lists (e1,,ek) and (v1,,vk) are linearly independent, they must span subspaces of the same dimension and therefore are the same subspace. Hence Equation (9.5.1) holds.

Example 9.5.2

Take v1=(1,1,0) and v2=(2,1,1) in R3. The list (v1,v2) is linearly independent (as you should verify!). To illustrate the Gram-Schmidt procedure, we begin by setting
e1=v1v1=12(1,1,0).
Next, set
e2=v2v2,e1e1v2v2,e1e1.
The inner product v2,e1=12(1,1,0),(2,1,1)=32,
so
u2=v2v2,e1e1=(2,1,1)32(1,1,0)=12(1,1,2).
Calculating the norm of u2, we obtain u2=14(1+1+4)=62.
Hence, normalizing this vector, we obtain
e2=u2u2=16(1,1,2).
The list (e1,e2) is therefore orthonormal and has the same span as (v1,v2).

Corollary 9.5.3.

Every finite-dimensional inner product space has an orthonormal basis.

Proof

Let (v1,,vn) be any basis for V. This list is linearly independent and spans V. Apply the Gram-Schmidt procedure to this list to obtain an orthonormal list (e1,,en), which still spans V by construction. By Proposition9.4.2~???, this list is linearly independent and hence a basis of V.

Corollary 9.5.4.

Every orthonormal list of vectors in V can be extended to an orthonormal basis of V.

Proof

Let (e1,,em) be an orthonormal list of vectors in V. By Proposition9.4.2~???, this list is linearly independent and hence can be extended to a basis (e1,,em,v1,,vk) of V by the Basis Extension Theorem. Now apply the Gram-Schmidt procedure to obtain a new orthonormal basis (e1,,em,f1,,fk). The first m vectors do not change since they already are orthonormal. The list still spans V and is linearly independent by Proposition9.4.2~??? and therefore forms a basis.

Recall Theorem7.5.3~???: given an operator TL(V,V) on a complex vector space V, there exists a basis B for V such that the matrix M(T) of T with respect to B is upper triangular. We would like to extend this result to require the additional property of orthonormality.

Corollary 9.5.5

Let V be an inner product space over F and TL(V,V). If T is upper-triangular with respect to some basis, then T is upper-triangular with respect to some orthonormal basis.

Proof

Let (v1,,vn) be a basis of V with respect to which T is upper-triangular. Apply the Gram-Schmidt procedure to obtain an orthonormal basis (e1,,en), and note that

span(e1,,ek)=span(v1,,vk),for all 1kn.

We proved before that T is upper-triangular with respect to a basis (v1,,vn) if and only if span(v1,,vk) is invariant under T for each 1kn. Since these spans are unchanged by the Gram-Schmidt procedure, T is still upper triangular for the corresponding orthonormal basis.


This page titled 9.5: The Gram-Schmidt Orthogonalization procedure is shared under a not declared license and was authored, remixed, and/or curated by Isaiah Lankham, Bruno Nachtergaele, & Anne Schilling.

Support Center

How can we help?