Every time I think “Now I understand the Fourier Transform,” I am wrong.
Doing the Fourier Transform of a function is just seeing it from “another” point of view. The “usual” view of a function is in the standard basis . For example, can be seen as a vector (in the basis given by the elements in the domain) whose coordinates are the evaluations of on the elements in the domain. It can also be seen as a polynomial (in the monomial basis) whose coefficients are these evaluations. Let us call this vector .
The same function can also be seen from the “Fourier basis”, which is just another orthogonal basis, formed by the basis vectors . The th coordinate in the new basis will be given by inner product between and the th basis vector . We call these inner products the Fourier coefficients. The Discrete Fourier Transform matrix (the DFT matrix) “projects” a function from the standard basis to the Fourier basis in the usual sense of projection: taking the inner product along a given direction.
In this post, I am going to use elementary group theoretic notions, polynomials, matrices, and vectors. The ideas in this post will be similar to this Wikipedia article on Discrete Fourier Transform.