Fourier Matrix

The $n\times n$ Square Matrix ${\hbox{\sf F}}_n$ with entries given by

$$F_{jk}=e^{2\pi i jk/n}$$ (1)

for $j,k=0$, 1, 2, ..., $n-1$, and normalized by $1/\sqrt{n}$ to make it a Unitary. The Fourier matrix ${\hbox{\sf F}}_2$ is given by

$${\hbox{\sf F}}_2={1\over\sqrt{2}}\left[{\matrix{1 & 1\cr 1 & i^2\cr}}\right],$$ (2)

and the ${\hbox{\sf F}}_4$ matrix by

$${\hbox{\sf F}}_4={1\over\sqrt{4}}\left[{\matrix{1 & 1 & 1 & ... ...atrix{1 & & & \cr & & 1 & \cr & 1 & & \cr & & & 1\cr}}\right].$$ (3)

In general,

$${\hbox{\sf F}}_{2n}=\left[{\matrix{{\hbox{\sf I}}_n & {\hbox... ...l\hbox{even-odd}\hfil\cr \hfil\hbox{shuffle}\hfil\cr}}\right],$$ (4)

with

$\left[{\matrix{{\hbox{\sf F}}_n & \cr & {\hbox{\sf F}}_n}}\right]=\left[{\matri... ...x{\sf D}}_{n/2}\cr & & {\hbox{\sf I}}_{n/2} & -{\hbox{\sf D}}_{n/2}\cr}}\right]$
$\times \left[{\matrix{{\hbox{\sf F}}_{n/2} & & & \cr & {\hbox{\sf F}}_{n/2} & &... ... {\rm\ (mod\ } 4)\cr \hbox{even-odd}\cr 1, 3 {\rm\ (mod\ } 4)\cr}}\right],\quad$	(5)

where ${\hbox{\sf I}}_n$ is the $n\times n$ Identity Matrix. Note that the factorization (which is the basis of the Fast Fourier Transform) has two copies of ${\hbox{\sf F}}_2$ in the center factor Matrix.

See also Fast Fourier Transform, Fourier Transform

References

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