On the Eigenstructure of DFT Matrices [DSP Education]

The discrete Fourier transform (DFT) not only enables fast implementation of the discrete convolution operation, which is critical for the efficient processing of analog signals through digital means, but it also represents a rich and beautiful analytical structure that is interesting on its own. A typical senior-level digital signal processing (DSP) course involves a fairly detailed treatment of DFT and a list of related topics, such as circular shift, correlation, convolution operations, and the connection of circular operations with the linear operations. Despite having detailed expositions on DFT, most DSP textbooks (including advanced ones) lack discussions on the eigenstructure of the DFT matrix. Here, we present a self-contained exposition on such.