anEvery time I thought “Now I understand Fourier Transform,” I was 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.

*Please let me know in the comments if you find any error or confusion.*

**Roots of Unity.** Let be the the multiplicative group of th roots of unity. That is, . is a primitive th root if the smallest natural exponent that makes is . The root is principal if . In what follows, we assume that is a principal and primitive th root of unity.

Let be a field containing . For example, can be the set of complex numbers and where is the imaginary unit. It is easy to check that the roots appear on the unit circle of radius 1 around the origin.

**Representing Functions as Polynomials or Vectors.** Let be the set of integers . To identify a function , it suffices to write down its evaluations on all . Thus we can treat as a -dimensional vector, whose th entry is just for . This shows that .

We can also represent the function (from the preceding paragraph) as a polynomial of degree at most , the representation being . This shows , where is the ring of polynomials with coefficients in and indeterminate , and the ring contains polynomials with degree at most . Why? Because when we take , we set every in , turning every into . Neat. (Why is a ring?)

**The Chinese Remainder Theorem.** The good news is, factors completely in because by assumption, contains all th roots of unity. This means, . Since the factors are relatively prime to each other, by the Chinese Remainder Theorem (CRT), there is a bijection which maps to a -tuple whose th entry is .

Essentially, the CRT says that “anything” expressed “with resptct to” can be equivalently expressed “with respect to” all individual factors , where

- “anything” is a polynomial
- expressing “with respect to” means computing .

**From Coefficients to Evaluations.** Let us write

.

By Euclid’s division algorithm, we can express

for some and where the degree of the remainder, , is strictly less than the degree of the divisor which means is just a scalar. It is easy to check that (by our definition of ) and (by substituting into the expression for ), giving us

.

*To me, the above feels like magic.*

Therefore, the transformed polynomial can be completely described by the evaluations of over the roots of unity , the evaluations being equal to for each .

**Connections with Polynomial Interpolation.** This way, the transformed polynomial can be completely described by the evaluations of over the roots of unity . Notice how it sounds like an interpolation problem: every polynomial of degree at most can be reconstructed from evaluations in any field. Indeed, the Lagrange interpolation theorem is a restatement of the Chinese Remainder Theorem.

**Enter DFT.** The transform is the Discrete Fourier Transform. The th coefficient of the transformed polynomial is called the th Fourier coefficient of . A root of unity , when treated as a function from defined as for any , is called a character of . The Fourier Transform maps a function from the standard (monomial) basis to the (Fourier) basis of characters.

**The Matrix of the Transform.** So, how does the transform look like? Let , where both are tread as dimensional vectors over , where the th coordinate of is . Recall that in polynomial representation, . We want to force every coordinate to be equal to . Notice that this equals where is the vector mentioned above, is the vector whose th entry is , and is the usual inner product. Then we can readily see that $\hat{f} = Tf$ makes sense as a matrix-vector multiplication, when the th row of the matrix is the transpose of the vector . All told, the matrix , containing at its row and column , is the Discrete Fourier Transform matrix. The above construction works even when is not a prime. (Notice that we have abused the notation and used to denote both a linear transform and its matrix.)

*Actually, I think I missed a scale-factor. The coefficients of the Discrete Fourier Transform of a function are actually scaled by a factor . I will correct my derivation later. The above discussion at least gives the structural insight behind the Fourier Transform.*

**Afterthoughts.** The transform is discrete because of the multiplicative group of the roots of unity, , is a finite group. It is isomorphic to under a map which sends the generator of (which is when is a prime) to the generator of , which is . The transform is also linear, because the inner product formulation is linear in both the coefficients of and entries of the matrix .

**A Glimpse of the Uncertainty Principle. **The weight of a polynomial is the number of its nonzero coefficients. Loosely speaking, the uncertainty principle says that the weight of and cannot both be sparse. An extreme example is that if has only one nonzero coefficient, none of its Fourier coefficients is zero. Similarly, if has no nonzero coefficient, then its Fourier transform has weight one. Let’s examine below why that is true.

A (Dirac) delta function can be represented as a vector with all zero entries except at coordinate , which contains . A uniform function for all will be the vector , where is the all-ones vector.

Everyone tells us that the Fourier transform of is , and the Fourier transform of is . If we see the Fourier Transform as multiplying a vector by the matrix , it is easy to see why.

All entries in the first row and column of the matrix are , becasue their values are where either or is zero. Multiplying with gives us the th column of , which is when . Otherwise, all Fourier coefficients of are nonzero. In particular, .

In contrast, multiplying with the vector adds up all columns of (times the scale factor ). This makes each Fourier coefficient (except the th coefficient) equal to the sum of all roots of unity, and this sum is zero. To see this, note that where . Since satisfies , this implies . Since , it follows that , which is the sum of all th root of unity, must be zero. On the other hand, the th coefficient is just the sum of ones. Hence, .

## One thought on “An Intuitive Explanation of the Discrete Fourier Transform”