# Is group theory useful for understanding the FFT?

The Fast Fourier Transform problem is to evaluate the matrix-vector product $$X = W x$$ quickly, where $x$ is the input signal and $W$ is the DFT matrix, $$W = \frac{1}{\sqrt{N}} \pmatrix{ 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{N-1} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(N-1)} \\ \vdots & \vdots & \vdots & \cdots & \vdots \\ 1 & \omega^{N-1} & \omega^{2(N-1)} & \cdots & \omega^{(N-1)(N-1)} }$$ with $\omega = e^{-2\pi i / N}$. The FFT works by using the symmetry of the matrix $W$ to factor it into a product of sparse matrices, i.e. $$W = S_1 S_2 \cdots S_n$$ if $N = 2^n$. Computing $n$ sparse matrix-vector products is much faster than computing the original dense matrix-vector product.

Since symmetry plays such an important role in the FFT, I was wondering if there is a nice derivation of the FFT using group theory. In other words can group theory be used to find the sparse factors of the $W$ matrix? I would appreciate a nice reference on this topic if anyone knows of one.

• Group representation theory is useful and there exist DFT / FFT over abelian groups. Over non-abelian groups it is a bit more involved. Consider the work of Rockmore et al.: arxiv.org/pdf/1609.02634.pdf – Wuestenfux Jun 8 '17 at 12:20
• Group theory (representation theory of abelian grapes in particular) gives us all kinds of DFTs. See e.g. this – Jyrki Lahtonen Jun 8 '17 at 12:34