Fourier Matrix

The Fourier matrix, also called the discrete Fourier transform matrix or DFT matrix, is the square matrix with entries given by

(1)

for , 1, 2, ..., , where i is the imaginary number , and normalized by to make it a unitary. The Fourier matrix is given by

(2)

and the matrix by

			(3)
			(4)

In general,

(5)

with

(6)

where is the identity matrix and is the diagonal matrix with entries 1, , ..., . Note that the factorization (which is the basis of the fast Fourier transform) has two copies of in the center factor matrix.