Visualizing the DFT matrix

The discrete Fourier transform (DFT) of length N multiplies a vector by a matrix whose (j, k) entry is ωjk where ω = exp(-2πi/N), with j and k running from 0 to – 1. Each element of the matrix is a rotation, so if N = 12, we can represent each element by an hour on a clock. The angle between the hour hand and minute hand corresponds to the phase of the matrix entry. We could also view each element as a color around a color wheel. The image below does both.

The matrix representing the inverse of the DFT is the conjugate of the DFT matrix (divided by Nf, but we’re only looking at phase here, so we can ignore this rescaling.) The image below displays the DFT matrix on the left and it’s inverse on the right.

Taking the conjugate amounts to making all the clocks run backward.

The DFT is often called the FFT. Strictly speaking, the FFT is an algorithm for computing the DFT. Nobody computes a DFT by multiplying by the DFT matrix, because the FFT is faster. The DFT matrix has a lot of special structure, which the FFT takes advantage of to compute the product faster than using ordinary matrix multiplication.

By the way, there are Unicode characters for clock times on the hour, U+1F550 through U+1F55B. I created the image above by writing a script that put the right characters in a table. The colors have HSL values where H is proportional to the angle and S = L =0.8.

4 thoughts on “Visualizing the DFT matrix

  1. I got interested in how you defined the color wheel. Can you share this bit of the code? I am a quantum physicist, who often has to deal with density matrices where most of the information is present in the phases of its off-diagonal components.
    Thank you for this post, and the whole blog.

  2. An (N-1)-th degree polynomial f can be determined completely by its values at the N points exp(2 π i n /N), n=0,1,…,N-1. If you feed any N values into the DFT, you get the N coefficients of f (the interpolating polynomial) out. The other direction gives you the values when you feed in the coefficients. I either didn’t know this or didn’t remember it until recently, though I have worked with the DFT many times in the past. Note that it makes the convolution property pretty obvious. I’m surprised this isn’t given more emphasis when the DFT is taught.

Comments are closed.