Page 383 - Matrix Analysis & Applied Linear Algebra

5.8 Discrete Fourier Transform 379

5.8.12. A circulant matrix is defined to be a square matrix that has the form

 
c 0 c n−1 c n−2 ··· c 1
 c 1 c 0 c n−1 ··· c 2 
 
C =  c 2 c 1 c 0 ··· c 3  .
 . . . . . 
 . . . .
. . . . . . 
c n−1 c n−2 c n−3 ··· c 0
n×n
In other words, the entries in each column are the same as the previous
column, but they are shifted one position downward and wrapped around
at the top—the (j, k)-entry in C can be described as c jk = c j−k (mod n) .
(Some authors use C T rather than C as the definition—it doesn’t
matter.)
(a) If Q is the circulant matrix defined by
 
00 ··· 01
 10 ··· 00 
 
Q =  01 ··· 00  ,
 . . . . . 
 . . . . . 
. . . . .
00 ··· 10
n×n
and if p(x)= c 0 + c 1 x + ··· + c n−1 x n−1 , verify that
C = p(Q)= c 0 I + c 1 Q + ··· + c n−1 Q n−1 .

(b) Explain why the Fourier matrix of order n diagonalizes Q in
the sense that
 
10 ··· 0
 0 ξ ··· 0 
FQF −1 = D =  . . . .  ,
 . . . . 
. . . .
00 ··· ξ n−1
k
where the ξ ’s are the n th roots of unity.
(c) Prove that the Fourier matrix of order n diagonalizes every
n × n circulant in the sense that
p(1) 0 ··· 0
 
 0 p(ξ) ··· 0 
FCF −1 =  . . . .  ,
 . . . . 
. . . .
0 0 ··· p(ξ n−1 )
where p(x)= c 0 + c 1 x + ··· + c n−1 x n−1 .
(d) If C 1 and C 2 are any pair of n × n circulants, explain why
C 1 C 2 = C 2 C 1 —i.e., all circulants commute with each other.