Page 346 - Matrix Analysis & Applied Linear Algebra

342 Chapter 5 Norms, Inner Products, and Orthogonality

to annihilate all entries below the (1, 1)-position in A k , and R k is defined

I k−1 0
as R k = , which is another elementary reflector (Exercise 5.6.7).
ˆ
0 R k
Eventually, all of the rows or all of the columns will be exhausted, so the final
result is one of the two following upper-trapezoidal forms:

 
∗∗· · · ∗


 0 ∗· · · ∗  

 . .
 . . . . .  n×n
.
. 
  

00 ··· ∗ 
  
R n ··· R 2 R 1 A m×n =   when m>n,
 
 00 ··· 0 
 . . . 
 . .
.
. . . 
00 ··· 0
 
∗∗· · · ∗ ∗ ··· ∗
 0 ∗· · · ∗ ∗ ··· ∗ 
R m−1 ··· R 2 R 1 A m×n =  . . . . .  when m<n.
 . . . . . 
. . . . .
00 ··· ∗ ∗ ··· ∗
) *+ ,
m×m
If m = n, then the final form is an upper-triangular matrix.
A product of elementary reflectors is not necessarily another elementary re-
flector, but a product of unitary (orthogonal) matrices is again unitary (orthogo-
nal) (Exercise 5.6.5). The elementary reflectors R i described above are unitary
(orthogonal in the real case) matrices, so every product R k R k−1 ··· R 2 R 1 is a
unitary matrix, and thus we arrive at the following important conclusion.
Orthogonal Reduction
m×n
• For every A ∈C , there exists a unitary matrix P such that
PA = T (5.7.3)
has an upper-trapezoidal form. When P is constructed as a prod-
uct of elementary reflectors as described above, the process is called
Householder reduction.
• If A is square, then T is upper triangular, and if A is real, then
the P can be taken to be an orthogonal matrix.