Page 345 - Matrix Analysis & Applied Linear Algebra

5.7 Orthogonal Reduction 341
5.7 ORTHOGONAL REDUCTION

We know that a matrix A can be reduced to row echelon form by elementary row
operations. This is Gaussian elimination, and, as explained on p. 143, the basic
“Gaussian transformation” is an elementary lower triangular matrix T k whose
action annihilates all entries below the k th pivot at the k th elimination step.
But Gaussian elimination is not the only way to reduce a matrix. Elementary
reflectors R k can be used in place of elementary lower triangular matrices T k
to annihilate all entries below the k th pivot at the k th elimination step, or a
sequence of plane rotation matrices can accomplish the same purpose.
When reflectors are used, the process is usually called Householder re-
duction, and it proceeds as follows. For A m×n =[A ∗1 | A ∗2 |· · · | A ∗n ] , use
x = A ∗1 in (5.6.10) to construct the elementary reflector
uu ∗
R 1 = I − 2 , where u = A ∗1 ± µ A ∗1 e 1 , (5.7.1)
u u
∗
so that
 
t 11
 0 
R 1 A ∗1 = ∓µ A ∗1 e 1 =  .  . (5.7.2)
.
 . 
0
Applying R 1 to A yields
 
t 11 t 12 ··· t 1n

  T
 0 ∗ · · · ∗  t 11 t 1
R 1 A=[R 1 A ∗1 | R 1 A ∗2 | ··· | R 1 A ∗n ]= . . . = ,
 . . 0 A 2
. . . . 
0 ∗ · · · ∗
where A 2 is m − 1 × n − 1. Thus all entries below the (1, 1)-position are an-
nihilated. Now apply the same procedure to A 2 to construct an elementary
ˆ
reflector R 2 that annihilates all entries below the (1, 1)-position in A 2 . If we
1 0
set R 2 = ˆ , then R 2 R 1 is an orthogonal matrix (Exercise 5.6.5) such
0 R 2
that
 
t 11 t 12 t 13 ··· t 1n
 
T  0 t 22 t 23 ··· t 2n 
t  
t 11 1
R 2 R 1 A = ˆ =   .
 0
0 R 2 A 2 0 ∗ · · · ∗ 
 . . . . 
 . . . . 
. . . .
0 0 ∗ · · · ∗
˜
The result after k − 1 steps is R k−1 ··· R 2 R 1 A = T k−1 T k−1 . At step
0 A k
ˆ
k an elementary reflector R k is constructed in a manner similar to (5.7.1)