DFT Matrix

Fourier Analysis · Axiom Academy

Understanding the Discrete Fourier Transform as matrix multiplication The DFT matrix W is an N×N matrix where each entry is a complex exponential. The element in row k and column n is defined by: Each entry represents a complex root of unity raised to a specific power. For an N-point DFT, the matrix contains all combinations of frequency index k and time index n. 2. Matrix-Vector Multiplication Form The DFT transforms a time-domain vector x into a frequency-domain vector X through matrix multiplication: This compact notation shows that computing the DFT is equivalent to multiplying the input vector by the DFT matrix. Each element X[k] is the dot product of row k of W with the input vector x. 3. Properties of the DFT Matrix The DFT matrix has several remarkable mathematical properties that make it particularly useful in signal processing: Symmetry: The matrix has conjugate symmetry: W* kn = W k,N-n Unitary (up to scaling): W H W = NI, where W H is the conjugate transpose The unitary property means the DFT preserves energy (up to scaling), and the inverse is simply the conjugate transpose scaled by 1/N. The fundamental building block of the DFT matrix is the twiddle factor (or primitive N-th root of unity): The entire DFT matrix can be expressed in terms of powers of this single complex number: The twiddle factor rotates points around the unit circle in the complex plane. As k and n increase, we get different rotations that form the basis for frequency decomposition.

This is the written version of the interactive lesson above. See the full Fourier Analysis course.