# Discrete Fourier Transform: the Intuition

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 $\{e_1, \cdots, e_n\}$. For example, $f$ can be seen as a vector (in the basis given by the elements in the domain) whose coordinates are the evaluations of $f$ 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 $u$.

The same function can also be seen from the “Fourier basis”, which is just another orthogonal basis, formed by the basis vectors $\{v_t\}, t$. The $t$th coordinate in the new basis will be given by inner product between $u$ and the $t$th basis vector $v_t$. 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.