Page 347 - Matrix Analysis & Applied Linear Algebra

5.7 Orthogonal Reduction 343
Example 5.7.1

Problem: Use Householder reduction to find an orthogonal matrix P such
that PA = T is upper triangular with positive diagonal entries, where
 
0 −20 −14
A =  3 27 −4  .
4 11 −2

Solution: To annihilate the entries below the (1, 1)-position and to guarantee
that t 11 is positive, equations (5.7.1) and (5.7.2) dictate that we set
 
−5 T
u 1 u 1
u 1 = A ∗1 − A ∗1 e 1 = A ∗1 − 5e 1 =  3  and R 1 = I − 2 .
T
4 u u 1
1
To compute a reflector-by-matrix product RA =[RA ∗1 | RA ∗2 | ··· | RA ∗n ] ,
T
T
it’s wasted effort to actually determine the entries in R = I−2uu /u u. Simply
T
compute u A ∗j and then

T
u A ∗j
RA ∗j = A ∗j − 2 u for each j =1, 2,...,n. (5.7.4)
T
u u
By using this observation we obtain
 
5 25 −4
R 1 A =[R 1 A ∗1 | R 1 A ∗2 | R 1 A ∗3 ]=  0 0 −10  .
0 −25 −10
To annihilate the entry below the (2, 2)-position, set

0 −10 −1

A 2 = and u 2 =[A 2 ] ∗1 −
[A 2 ] ∗1
e 1 =25 .

−25 −10 −1
1 0
ˆ
T
T
If R 2 = I − 2u 2 u /u u 2 and R 2 = 0 R 2 (neither is explicitly computed),
ˆ
2
2
then
 
525 −4
25 10
ˆ
R 2 A 2 = and R 2 R 1 A = T =  025 10  .
010
0 0 10
ˆ
T
T
If R k = I − 2ˆ uˆ u /ˆ u ˆ u is an elementary reflector, then so is
T
I 0 uu 0
R k = ˆ = I − 2 with u = ,
T
0 R k u u ˆ u
and consequently the product of any sequence of these R k ’s can be formed by
using the observation (5.7.4). In this example,
 
0 15 20
1
P = R 2 R 1 =  −20 12 −9  .
25
−15 −16 12
Youmay wish to check that P really is an orthogonal matrix and PA = T.