The discrete Fourier transform matrix

For an element ω of a field and N : ℕ, dft ω N is the N × N matrix (ω ^ (r c)) with rows r (the outputs) and columns c (the inputs), both indexed by 0, …, N - 1. When ω is a primitive N-th root of unity, x ↦ dft ω N x is the N-point discrete Fourier transform: over ℂ with ω = e^{2πi/N} it is the classical DFT (for N = 2^k, the map computed by the fast Fourier transform), and over ZMod q with N ∣ q - 1 it is a number-theoretic transform.

def Algebraic.Cutwidth.MultiOutput.dft {F : Type u_1} [Monoid F] (ω : F) (N : ℕ) : Matrix (Fin N) (Fin N) F

The N × N discrete Fourier transform matrix (ω ^ (r c)): row r, column c.

Equations

• Algebraic.Cutwidth.MultiOutput.dft ω N = Matrix.of fun (r c : Fin N) => ω ^ (↑r * ↑c)