Eigenvectors of the DFT matrix

When is the discrete Fourier transform of a vector proportional to the original vector? And when that happens, what is the proportionality constant?

In more formal language, what can we say about the eigenvectors and eigenvalues of the DFT matrix?

Setup

I mentioned in the previous post that Mathematica's default convention for defining the DFT has mathematical advantages. One of these is that it makes the DFT an isometry, that is, taking the DFT of a vector does not change its norm. We will use Mathematica's convention here because that will simplify the discussion. Under this convention, the DFT matrix of size N is the square matrix whose (j, k) entry is

^jk / N

where = exp(-2 i/N) and the indices j and k run from 0 to N - 1.

Eigenvalues

Using the definition above, if you take the discrete Fourier transform of a vector four times, you end up back where you started. With other conventions, taking the DFT four times takes you to a vector that is proportional to the original vector, but not the same.

It's easy to see what the eigenvalues of the DFT are. If transforming a vector multiplies it by , then ⁴ = 1. So = 1 or i. This answers the second question at the top of the post: if the DFT of a vector is proportional to the original vector, the proportionality constant must be a fourth root of 1.

Eigenvectors

The eigenvectors of the DFT, however, are not nearly so simple.

Suppose N = 4k for some k > 1 (which it nearly always is in practice). I would expect by symmetry that the eigenspaces of 1, -1, i and -i would each have dimension k, but that's not quite right.

In [1] the authors proved that the eigenspaces associated with 1, -1, i and -i have dimension k+1, k, k-1, and k respectively.

This seems strange to me in two ways. First, I'd expect all the spaces to have the same dimension. Second, if the spaces did not have the same dimension, I'd expect 1 and -1 to differ, not i and -i. Usually when you see i and -i together like this, they're symmetric. But the span of the eigenvectors associated with i has dimension one less than the dimension of the span of the eigenvectors associated with -i. I don't see why this should be. I've downloaded [1] but haven't read it yet.

[1] J. H. McClellan; T. W. Parks (1972). Eigenvalues and eigenvectors of the discrete Fourier transformation". IEEE Transactions on Audio and Electroacoustics. 20 (1): 66-74.

The post Eigenvectors of the DFT matrix first appeared on John D. Cook.