# Conceptual question about Discrete Fourier Transform

On the wikipedia page for the discrete Fourier transform, the first sentence says:

In mathematics, the discrete Fourier transform (DFT) converts a finite list of equally spaced samples of a function into the list of coefficients of a finite combination of complex sinusoids, ordered by their frequencies, that has those same sample values.

But as I learned it, the Fourier matrix $\mathcal{F}$ takes as its inputs vectors of coefficients $(c_0, c_1, \dotsc, c_{n-1})$ and produces a vector $(f(0), f(2\pi/n), f(2\cdot 2\pi/n), \dotsc, f((n-1)\cdot 2\pi/n))$, where $$f(x) = c_0 + c_1 e^{ix} + c_2 e^{2ix} + \dotsb + c_{n-1}e^{(n-1)ix}.$$

So the above description seems to be describing what the inverse Fourier matrix does. Why is this?

• The description you quoted is horribly worded but accurate. You are using $f$ for both domains rather than just frequency. I think what you meant is $f(x)=\hat{f}(0) + \hat{f}(2\pi/n) e^{jx} + \cdots$, where $\hat{f}$ is the DFT of $f$. The clearest way to think about the DFT is as a simple change of basis from whatever the input uses to a set of orthonormal complex sinusoids. – AnonSubmitter85 Aug 13 '13 at 22:53

It's little bit more than just convention and comes down to how you identify the characters of the underlying group. Of course once you make a choice, everything works out similarly.

In the case of DFT, the group is the finite cyclic group $\mathbb{Z}_n$. When talking about characters, i.e. group homomorphims from $\mathbb{Z}_n$ to the unit circle, you can go around the circle either counter-clockwise or clockwise. If the former, $+i$ appears in your formula. If the latter, $-i$.

Same thing applies to the Fourier transform on $\mathbb{R}$. Do you wind the line around the circle counter-clockwise or clockwise, i.e. $i$ or $-i$? Do you wind it with period $1$ or $2 \pi$?...etc.

• Is there a correspondence (I think I am missing it) between which way you go around the circle, and considering $$\mathcal{F}: \mathcal{P}_{n-1} \to \mathbb{C}^n,$$ rather than $$\mathcal{F}: \mathbb{C}^n \to \mathcal{P}_{n-1}?$$ (Here $\mathcal{P_{n-1}}$ is trigonometric polynomials of frequency $<n$.) My question was: why does Wikipedia seem to suggest the latter interpretation, when every (?) presentation of the Fourier matrix suggests the former? – Eric Auld Aug 22 '13 at 15:37
• One is not better than the other. Once you fix a direction (say clockwise), to take the inverse transform would be going the opposite direction. That's probably the issue with wikipedia convention. As you pointed out, their DFT goes the wrong way. Yes, it's a little weird, since the group algebra in this case is $\mathbb{C}^n$, but equivalent nevertheless. – Michael Aug 22 '13 at 15:51
• I'm aware that one way to invert $\mathcal{F}$ is to apply $\mathcal{F}$ to $\vec{c}'$, and then multiply by $1/n$ (here $\vec{c}'$ is just reversing the entries, except for the first). Is this equivalent to what you're saying? Are you suggesting that the phenomenon is more general than just the DFT? Thanks for your help! – Eric Auld Aug 22 '13 at 15:58
• Well, when you're reversing the entries, effectively you're going in the opposite direction, are you not? Same thing happens if you look at Fourier transform and its inverse (when inversion makes sense) on the real line, $-i$ becomes $i$. Flipping the group about the zero element is the same as switching direction on the circle, geometrically speaking. – Michael Aug 22 '13 at 19:13
• Yes, I agree, thanks. Right now the "inverse by changing directions" property seems incidental to the Fourier matrix, but since the same principle applies to the continuous Fourier transform, it must be an aspect of a more general phenomenon. – Eric Auld Aug 22 '13 at 19:18

The definition of Fourier matrix is inconsistent in the literature. Wolfram says $\mathcal F_{j,k}=\exp(2\pi i jk/n)$, consistent with your notion of $\mathcal F$. Wikipedia puts $-i$ there, consistent with its description of DFT.

At some level, this is a moot point. I have a concept of $i$ in my head, and so do you. But there is no way to know if my concept of $i$ corresponds to your $i$ or to your $-i$. Between two roots of $-1$, one is chosen as $i$, but the choice is completely arbitrary.