On the diagonalization of the discrete Fourier transform (Q1026466)

The authors describe a representation theoretic approach to the diagonalization problem of the discrete Fourier transform of length \(p\), where \(p>2\) is a prime number. Starting with the Weil representation of the finite symplectic group, the theory of tori in the one-dimensional Weil representation is discussed. Using a relation between the DFT and the Weil representation, a canonical basis \(\Phi\) of eigenvectors for the DFT is presented. The transition matrix \(\Theta\) from the standard basis to \(\Phi\) defines a novel transform, the so-called discrete oscillator transform. Finally, a fast algorithm for computing \(\Theta\) in certain cases is described.