Page 373 - Matrix Analysis & Applied Linear Algebra

5.8 Discrete Fourier Transform 369

only about 3n log n multiplications to perform a convolution of two n × 1vec-
2
2
tors, and when n is large, this is significantly less than the n factor demanded
by the definition of convolution.
The magic of the fast Fourier transform algorithm emanates from the fact
that if n is a power of 2, then a discrete Fourier transform of order n can be
executed by performing two transforms of order n/2. To appreciate exactly how

r
this comes about, observe that when n =2 we have ξ j n = ξ 2j n/2 , so
2 3 n−1 th
1,ξ,ξ ,ξ ,. .., ξ = the n roots of unity
if and only if
2 4 6 n−2 th
1,ξ ,ξ ,ξ ,. .., ξ = the (n/2) roots of unity.
This means that the (j, k)-entries in the Fourier matrices F n and F n/2 are
2 jk
[F n ] jk = ξ jk and [F n/2 ] jk =(ξ ) = ξ 2jk . (5.8.14)
If the columns of F n are permuted so that columns with even subscripts are
listed before those with odd subscripts, and if P T is the corresponding permu-
n
tation matrix, then we can partition F n P T as
n

A n × n B n × n
T
F n P =[F ∗0 F ∗2 ··· F ∗n−2 | F ∗1 F ∗3 ··· F ∗n−1 ]= 2 2 2 2 .
n
C n × n G n × n
2 2 2 2
By using (5.8.14) together with the facts that
2π(n/2) 2π(n/2)
nk
n/2
ξ =1 and ξ = cos − i sin = −1,
n n
we see that the entries in A, B, C, and G are
A jk = F j,2k = ξ 2jk =[F n/2 ] jk ,
j 2jk
j
B jk = F j,2k+1 = ξ j(2k+1) = ξ ξ = ξ [F n/2 ] jk ,
n
ξ
2
C jk = F n +j, 2k = ξ ( +j)2k = ξ nk 2jk = ξ 2jk =[F n/2 ] jk ,
2
n
j
j 2jt
ξ ξ
ξ
G jk = F n +j, 2k+1 = ξ ( +j)(2k+1) = ξ nk n/2 j 2jk = −ξ ξ = −ξ [F n/2 ] jk .
2
2
In other words, if D n/2 is the diagonal matrix
 
1
ξ
 2 
D n/2 =  ξ  ,
 . . . 
n −1
ξ 2
then

A (n/2)×(n/2) B (n/2)×(n/2) F n/2 D n/2 F n/2
T
F n P = = .
n
C (n/2)×(n/2) G (n/2)×(n/2) F n/2 −D n/2 F n/2
This fundamental feature of the discrete Fourier transform is summarized below.