1.7. INNER PRODUCT SPACES 19

Lemma 1.7.7 Let {x1, · · · ,xn} be a linearly independent subset of Fp, p ≥ n. Thenthere exist orthonormal vectors {u1, · · · ,un} which have the property that for each k ≤ n,span(x1, · · · ,xk) = span(u1, · · · ,uk) .

Proof: Let u1 ≡ x1/ |x1| . Thus for k = 1, span(u1) = span(x1) and {u1} is an or-thonormal set. Now suppose for some k < n, u1, · · · , uk have been chosen such that(u j,ul) = δ jl and span(x1, · · · ,xk) = span(u1, · · · ,uk). Then define

uk+1 ≡xk+1−∑

kj=1 (xk+1,u j)u j∣∣∣xk+1−∑kj=1 (xk+1,u j)u j

∣∣∣ , (1.9)

where the denominator is not equal to zero because the x j form a basis, and so

xk+1 /∈ span(x1, · · · ,xk) = span(u1, · · · ,uk)

Thus by induction,

uk+1 ∈ span(u1, · · · ,uk,xk+1) = span(x1, · · · ,xk,xk+1) .

Also, xk+1 ∈ span(u1, · · · ,uk,uk+1) which is seen easily by solving 1.9 for xk+1 and itfollows

span(x1, · · · ,xk,xk+1) = span(u1, · · · ,uk,uk+1) .

If l ≤ k,

(uk+1,ul) =C

((xk+1,ul)−

k

∑j=1

(xk+1,u j)(u j,ul)

)=

C

((xk+1,ul)−

k

∑j=1

(xk+1,u j)δ l j

)=C ((xk+1,ul)− (xk+1,ul)) = 0.

The vectors,{

u j}n

j=1 , generated in this way are therefore orthonormal because each vectorhas unit length. ■

The following lemma is a fairly simple observation about the Gram Schmidt processwhich says that if you start with orthonormal vectors, the process will not undo what youalready have.

Lemma 1.7.8 Suppose{

w1, · · · ,wr,vr+1, · · · ,vp}

is a linearly independent set of vec-tors such that {w1, · · · ,wr} is an orthonormal set of vectors. Then when the Gram Schmidtprocess is applied to the vectors in the given order, it will not change any of the w1, · · · ,wr.

Proof: Let{

u1, · · · ,up}

be the orthonormal set delivered by the Gram Schmidt process.Then u1 = w1 because by definition, u1 ≡ w1/ |w1| = w1. Now suppose u j = w j for allj ≤ k ≤ r. Then if k < r, consider the definition of uk+1.

uk+1 ≡wk+1−∑

k+1j=1 (wk+1,u j)u j∣∣∣wk+1−∑k+1j=1 (wk+1,u j)u j

∣∣∣By induction, u j = w j and so this reduces to wk+1/ |wk+1|= wk+1. ■