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, vk≠0 for each k=1,2,…,m. Set e1=v1‖v1‖. Then e1 is a vector of norm 1 and satisfies Equation (9.5.1) for k=1. Next, set
e2=v2−⟨v2,e1⟩e1‖v2−⟨v2,e1⟩e1‖.
This is, in fact, the normalized version of the orthogonal decomposition Equation(9.3.1)~(???). I.e.,
w=v2−⟨v2,e1⟩e1,
where w⊥e1. Note that ‖e2‖=1 and span(e1,e2)=span(v1,v2).
Now, suppose that e1,…,ek−1 have been constructed such that (e1,…,ek−1) is an orthonormal list and span(v1,…,vk−1)=span(e1,…,ek−1). Then define
ek=vk−⟨vk,e1⟩e1−⟨vk,e2⟩e2−⋯−⟨vk,ek−1⟩ek−1‖vk−⟨vk,e1⟩e1−⟨vk,e2⟩e2−⋯−⟨vk,ek−1⟩ek−1‖.
Since (v1,…,vk) is linearly independent, we know that vk∉span(v1,…,vk−1). Hence, we also know that vk∉span(e1,…,ek−1). 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⟩=⟨vk−⟨vk,e1⟩e1−⟨vk,e2⟩e2−⋯−⟨vk,ek−1⟩ek−1‖vk−⟨vk,e1⟩e1−⟨vk,e2⟩e2−⋯−⟨vk,ek−1⟩ek−1‖,ei⟩=⟨vk,ei⟩−⟨vk,ei⟩‖vk−⟨vk,e1⟩e1−⟨vk,e2⟩e2−⋯−⟨vk,ek−1⟩ek−1‖=0,
for each 1≤i<k. Hence, (e1,…,ek) is orthonormal.
◻
From the definition of ek, we see that vk∈span(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=v1‖v1‖=1√2(1,1,0).
Next, set
e2=v2−⟨v2,e1⟩e1‖v2−⟨v2,e1⟩e1‖.
The inner product ⟨v2,e1⟩=1√2⟨(1,1,0),(2,1,1)⟩=3√2,
so
u2=v2−⟨v2,e1⟩e1=(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=u2‖u2‖=1√6(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 T∈L(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 T∈L(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 1≤k≤n.
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 1≤k≤n. Since these spans are unchanged by the Gram-Schmidt procedure, T is still upper triangular for the corresponding orthonormal basis.
Contributors
- Isaiah Lankham, Mathematics Department at UC Davis
- Bruno Nachtergaele, Mathematics Department at UC Davis
- Anne Schilling, Mathematics Department at UC Davis
Both hardbound and softbound versions of this textbook are available online at WorldScientific.com.