Page 355 - Matrix Analysis & Applied Linear Algebra

5.7 Orthogonal Reduction 351

n×n
Problem: Reduce A ∈ to upper-Hessenberg form by means of an orthog-
onal similarity transformation—i.e., construct an orthogonal matrix P such that
T
P AP = H is upper Hessenberg.
Solution: At each step, use Householder reduction on entries below the main
ˆ
diagonal. Begin by letting A ∗1 denote the entries of the first column that are
below the (1,1)-position—this is illustrated below for n =5:
 
∗ ∗∗∗∗

  ˆ
 ∗ ∗∗∗∗  a 11 A 1∗
A =  ∗∗∗∗  = .

 ∗
ˆ
  A ∗1 A 1
∗ ∗∗∗∗
∗ ∗∗∗∗
ˆ
If R 1 is an elementary reflector determined according to (5.7.1) for which
 
∗
1 0
0
ˆ ˆ
R 1 A ∗1 =   , then R 1 = ˆ is an orthogonal matrix such that
0 0 R 1
0

ˆ
1 0 a 11 A 1∗ 1 0
R 1 AR 1 = ˆ ˆ
ˆ
0 R 1 A ∗1 A 1 0 R 1
 
∗ ∗∗∗∗

ˆ ˆ  
a 11 A 1∗ R 1  ∗ ∗∗∗∗ 
= =  0  .

ˆ ˆ ˆ ˆ ∗∗∗∗ 
R 1 A ∗1 R 1 A 1 R 1  
0 ∗∗∗∗
0 ∗∗∗∗
ˆ
ˆ
At the second step, repeat the process on A 2 = R 1 A 1 R 1 to obtain an orthogo-
 
∗ ∗ ∗ ∗

ˆ ˆ ˆ  ∗ ∗ ∗ ∗  I 2 0
nal matrix R 2 such that R 2 A 2 R 2 =  . Matrix R 2 = 0 ˆ
0 ∗ ∗ ∗ R 2
0 ∗ ∗ ∗
is an orthogonal matrix such that
 
∗ ∗ ∗∗∗
 
 ∗ ∗ ∗∗∗ 
 
0 ∗ ∗∗∗
R 2 R 1 AR 1 R 2 =   .
 
0 0 ∗∗∗
 
0 0 ∗∗∗
After n − 2of these steps, the product P = R 1 R 2 ··· R n−2 is an orthogonal
T
matrix such that P AP = H is in upper-Hessenberg form.