13.2. FUNDAMENTAL THEORY AND GENERALIZATIONS 305

Lemma 13.2.7 Let {x1, · · · ,xn} be a linearly independent subset of Fp, p≥ n. Then thereexist 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

∣∣∣ , (13.8)

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 13.8 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 process by which these vectors were generated is called the Gram Schmidt process.Note that from the construction, each xk is in the span of {u1, · · · ,uk}. In terms of matrices,this says

(x1 · · ·xn) = (u1 · · ·un)R

where R is an upper triangular matrix. This is closely related to the QR factorization dis-cussed earlier. It is called the thin QR factorization. If the Gram Schmidt process is usedto enlarge {u1 · · ·un} to an orthonormal basis for Fm, {u1 · · ·un,un+1, · · · ,um} then if Q isthe matrix which has these vectors as columns and if R is also enlarged to R′ by adding inrows of zeros, if necessary, to form an m×n matrix, then the above would be of the form

(x1 · · ·xn) = (u1 · · ·um)R′

and you could read off the orthonormal basis for span(x1 · · ·xn) by simply taking the firstn columns of Q = (u1 · · ·um). This is convenient because computer algebra systems are setup to find QR factorizations.