Page 374 - Matrix Analysis & Applied Linear Algebra

370 Chapter 5 Norms, Inner Products, and Orthogonality

Decomposing the Fourier Matrix

r
If n =2 , then

F n/2 D n/2 F n/2
F n = P n , (5.8.15)
F n/2 −D n/2 F n/2
where  
1
ξ
 2 
D n/2 =  ξ 
 . . . 
n −1
ξ 2
contains half of the n th roots of unity and P n is the “even–odd” per-
mutation matrix defined by

T
P =[e 0 e 2 e 4 ··· e n−2 | e 1 e 3 e 5 ··· e n−1 ] .
n

The decomposition (5.8.15) says that a discrete Fourier transform of order
r
n =2 can be accomplished by two Fourier transforms of order n/2=2 r−1 , and
this leads to the FFT algorithm. To get a feel for how the FFT works, consider
the case when n =8, and proceed to “divide and conquer.” If
 
  x 0
x 0
 x 2 
 x 1 
 
 
 x 4   
 x 2  (0)
 
  x 4
 x 6 
 x 3 
x 8 =   , then P 8 x 8 =   =   ,
 
 x 4  (1)
 x 1  x
  4
 
 x 5 
 x 3 
 
x 6  
x 5
x 7
x 7
so
   
(0) (0) (1)
F 4 D 4 F 4 x 4 F 4 x 4 + D 4 F 4 x 4
F 8 x 8 =   =   . (5.8.16)
(1) (0) (1)
F 4 −D 4 F 4 x 4 F 4 x 4 − D 4 F 4 x 4
But
   
x 0  (0)  x 1  (2) 
x x
(0)  x 4  2 (1)  x 5  2
P 4 x 4 =   =   and P 4 x 4 =   =   ,
  (1)   (3)
x 2 x 3
x x
2 2
x 6 x 7