TOPICS
Search

Fourier Matrix


The n×n square matrix F_n with entries given by

 F_(jk)=e^(2piijk/n)=omega^(jk)
(1)

for j,k=0, 1, 2, ..., n-1, where i is the imaginary number i=sqrt(-1), and normalized by 1/sqrt(n) to make it a unitary. The Fourier matrix F_2 is given by

 F_2=1/(sqrt(2))[1 1; 1 i^2],
(2)

and the F_4 matrix by

F_4=1/(sqrt(4))[1 1 1 1; 1 i i^2 i^3; 1 i^2 i^4 i^6; 1 i^3 i^6 i^9]
(3)
=1/2[1  1 ;  1  i; 1  -1 ;  1  -i][1 1  ; 1 i^2  ;   1 1;   1 i^2][1   ;   1 ;  1  ;    1].
(4)

In general,

 F_(2n)=[I_n D_n; I_n -D_n][F_n ;  F_n][ even-odd ;  shuffle ],
(5)

with

 [F_n ;  F_n]=[I_(n/2) D_(n/2)  ; I_(n/2) -D_(n/2)  ;   I_(n/2) D_(n/2);   I_(n/2) -D_(n/2)] 
 ×[F_(n/2)   ;  F_(n/2)  ;   F_(n/2) ;    F_(n/2)][even-odd; 0,2 (mod 4); even-odd; 1,3 (mod 4)],
(6)

where I_n is the n×n identity matrix and D_n is the diagonal matrix with entries 1, omega, ..., omega^(n-1). Note that the factorization (which is the basis of the fast Fourier transform) has two copies of F_2 in the center factor matrix.


See also

Fast Fourier Transform, Fourier Transform

Explore with Wolfram|Alpha

References

Strang, G. "Wavelet Transforms Versus Fourier Transforms." Bull. Amer. Math. Soc. 28, 288-305, 1993.

Referenced on Wolfram|Alpha

Fourier Matrix

Cite this as:

Weisstein, Eric W. "Fourier Matrix." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FourierMatrix.html

Subject classifications