Page 312 - Matrix Analysis & Applied Linear Algebra

308 Chapter 5 Norms, Inner Products, and Orthogonality

k
so u k+1 x k+1 =e iθ
x k+1 −
for some 0 ≤ θ< 2π, and
i=1 u i x k+1 u i
k
x k+1 − i=1 u i x k+1 u i
u k+1 =

.
iθ
k
e
x k+1 − u i x k+1 u i
i=1
Since the value of θ in the scalar e iθ neither affects span {u 1 , u 2 ,..., u k+1 } nor
the facts that u k+1 =1 and u k+1 u i =0 for all i ≤ k, we can arbitrarily
define u k+1 to be the vector corresponding to the θ =0 or, equivalently,
iθ
e =1. For the sake of convenience, let
k

ν k+1 =
x k+1 − u i x k+1 u i
i=1
so that we can write
k
x 1 x k+1 − i=1 u i x k+1 u i
u 1 = and u k+1 = for k> 0. (5.5.2)
x 1 ν k+1
This sequence of vectors is called the Gram–Schmidt sequence. A straight-
forward induction argument proves that O k = {u 1 , u 2 ,..., u k } is indeed an or-
thonormal basis for span {x 1 , x 2 ,..., x k } for each k =1, 2,... . Details are
called for in Exercise 5.5.7.
The orthogonalization procedure defined by (5.5.2) is valid for any inner-
m m
product space, but if we concentrate on subspaces of or C with the stan-
dard inner product and euclidean norm, then we can formulate (5.5.2) in terms
of matrices. Suppose that B = {x 1 , x 2 ,..., x n } is a basis for an n-dimensional
m×1
subspace S of C so that the Gram–Schmidt sequence (5.5.2) becomes
k−1
∗
x 1 x k − i=1 (u x k ) u i
i
u 1 = and u k =

for k =2, 3,...,n. (5.5.3)
k−1
x 1
∗

x k −
i
i=1 (u x k ) u i
To express this in matrix notation, set

U 1 = 0 m×1 and U k = u 1 | u 2 |···| u k−1 for k> 1,
m×k−1
and notice that
 ∗ 
u x k
1
∗ k−1 k−1
2
 u x k 
∗
∗
U x k =  .  and U k U x k = u i (u x k )= (u x k ) u i .
∗
∗
i
k
i
k
 . 
.
i=1 i=1
u ∗ k−1 k
x
Since
k−1

∗
∗
∗
x k − (u x k ) u i = x k − U k U x k =(I − U k U ) x k ,
k
k
i
i=1
the vectors in (5.5.3) can be concisely written as
∗
(I − U k U ) x k
k
u k = for k =1, 2,...,n.
∗
(I − U k U ) x k
k
Below is a summary.