A Fourier matrix:

A large Fourier matrix:

The real and imaginary parts of the Fourier's basis sequences of length 128:

Construct a structured Fourier matrix using the option setting TargetStructure"Structured":

The structured representation saves a significant amount of memory for larger matrices:

The efficiency of the fast Fourier transform (FFT) relies on being able to form a larger Fourier matrix from two smaller ones. Generate two small Fourier matrices of sizes p and q:

The Fourier matrix of size p q can be expressed as a product of four simpler matrices:

Show that the resulting matrix is equivalent to the result of FourierMatrix:

The discrete Fourier transform of a vector can be computed by successively multiplying the factors of the Fourier matrix to the vector:

The result is equivalent to applying Fourier to the vector:

Define a function for constructing a circulant matrix from a vector:

Circulant matrices can be diagonalized by the Fourier matrix:

The diagonal elements of the resulting diagonal matrix are the same as the product of the Fourier matrix and the starting vector, up to a constant scaling factor:

A Fourier matrix with unit normalization:

For even dimensions, the permanent of the matrix is zero:

For odd dimensions, the permanent of the matrix is always an integer:

For an odd prime p>3, the permanent of the p×p matrix is congruent to p!, modulo p³:

FourierMatrix can be represented as a scaled VandermondeMatrix:

The Fourier transform of a vector is equivalent to the vector multiplied by a Fourier matrix:

The inverse Fourier transform is equivalent to multiplying by the conjugate transpose:

Fourier is much faster than the matrix-based computation: