  Fast Fourier transform was included in the Top 10 Algorithms of 20th Century
by Computing in Science & Engineering. In this paper, we provide a new simple
derivation of both the discrete Fourier transform and fast Fourier transform by
means of elementary linear algebra. We start the exposition by introducing the
convolution product of vectors, represented by a circulant matrix, and derive
the discrete Fourier transform as the change of basis matrix that diagonalizes
the circulant matrix. We also generalize our approach to derive the Fourier
transform on any finite abelian group, where the case of Fourier transform on
the Boolean cube is especially important for many applications in theoretical
computer science.

Data Structures and Algorithms;Discrete Mathematics;Combinatorics;History and Overview