Page 362 - Matrix Analysis & Applied Linear Algebra

358 Chapter 5 Norms, Inner Products, and Orthogonality

and consequently every column of F n can be normalized by multiplying by the
√ √
same scalar—namely, 1/ n. This means that (1/ n )F n is a unitary matrix.
T
Since it is also true that F = F n , we have
n
−1 ∗
1 1 1
√ F n = √ F n = √ F n ,
n n n
k
k
and therefore F −1 = F n /n. But (5.8.1) says that ξ = ω , so it must be the
n
case that
 
11 1 ··· 1
 1 ω ω 2 ··· ω n−1 
1 1  2 4 n−2 
−1
F n = F n =  1 ω ω ··· ω  .
n n  . . . . . . . . . 
 .
. . . . . 
1 ω n−1 ω n−2 ··· ω n×n
Example 5.8.1
The Fourier matrices of orders 2 and 4 are given by
1 1 1 1
 

1 1  1 −i −1 i 
F 2 = and F 4 =   ,
1 −1 1 −1 1 −1
1 i −1 −i
and their inverses are

 
1 1 1 1

1 1 1 1 −1 1 1  1 i −1 −i 
−1
F = F 2 = and F = F 4 =  .
2 4 
2 2 1 −1 4 4 1 −1 1 −1
1 −i −1 i
Discrete Fourier Transform

Given a vector x n×1 , the product F n x is called the discrete Fourier
transform of x, and F −1 x is called the inverse transform of x.
n
The k th entries in F n x and F −1 x are given by
n
n−1 n−1
jk −1 1 jk
[F n x] k = x j ξ and [F x] k = x j ω . (5.8.3)
n n
j=0 j=0