# Discrete Fourier Transform: Prove that only N distinct values of {X(k)} can be computed

The Discrete Fourier Transform (DFT) is a sequence of $X(k)$ in frequency domain of the time sequence {$x(n)$} of $N$ terms. The periodic property of the DFT is often used to reduce its computational time. Prove that only $N$ distinct values of {$X(k)$} can be computed.

• The assertion The periodic property of the DFT is often be used to reduce computation time is highly suspect and the factoid to be proved only $N$ distinct values of $\{X(k)\}$ can be computed is somewhat tautological: the very definition of the DFT as $$X(k)=\sum_{i=0}^{N-1}x(n)e^{-j2\pi nk/N},k=0,1,\ldots,N-1$$ says that there are only $N$ values. Now, if one wants to insist that $k\in\mathbb Z$, then it is the periodicity of $e^{-j2\pi nk/N}$ that tells us that $X(k+N)=X(k)$ and so there are only $N$ distinct values of $K$ that we need to look at, but no reduction in time occurs. Jan 2 '15 at 19:31
• @DilipSarwate, i think Aneesa might be trying to say that the periodic characteristics of the DFT can be used to create the "FFT" which does reduce computation time (as in the first "F"). i dunno. Jan 2 '15 at 19:46
• @robertbristow-johnson I am not aware of any derivation of an FFT algorithm which explicitly needs the periodicity of the DFT to prove that it works or of an FFT program that, during its operation, needs to reference any datum $X(k)$ for which $k<0$ or $k>N-1$. Jan 2 '15 at 19:52
• gee, i thought that's how Tukey and Cooley did it. expecially with the radix-2, you just split it in half and show that, point-by-point, there are coefficients the two halves have in common and that wouldn't be the case if there wasn't periodicity. what am i missing @DilipSarwate? Jan 2 '15 at 20:11
• BTW, i don't wanna (yet) get into the periodicity battles that i had at comp.dsp. not at the moment. but i just want to say for the record that, while you don't need to reach beyond $0 \le k \le N-1$ to actually run the FFT, but when using the DFT and its theorems (any that cause shifting), the periodicity is either there explicitly (with the modulo indexing) or implicitly (by saying that $X[k+N]=X[k] \quad \forall k$ and $x[n+N]=x[n] \quad \forall n$). the inherent periodicity is inescapable. Jan 2 '15 at 20:16

It's not quite clear what you are supposed to consider as starting point for your proof. You have to make some assumptions of what is known before you can prove something else. So unless you give a more detailed description of what you want to prove from what, I will give you a proof that uses a sensible set of assumptions.

Let's characterise the discrete Fourier transform as a map between two complex vector spaces $$\mathcal{F}:\mathbb{C}^N\to\mathbb{C}^M$$ of dimension $N$ and $M$ respectively. The map is supposed to preserve the structure of the vector space, so it must be linear.

A linear map between finite dimensional vector spaces can be completely described using a matrix, which in this case is $M\times N$. The rank of this matrix $F_+$ is less or equal to the smaller dimension, i.e. $\mathrm{rank}(F_+)\le\min(N,M)$.

We also require the map to be a transform, meaning that it can be inverted. So $$\mathcal{F}^{-1}:\mathbb{C}^M\to\mathbb{C}^N$$ must exist and $$\mathcal{F}^{-1}\circ\mathcal{F}=\mathrm{id}_N$$ as well as $$\mathcal{F}\circ\mathcal{F}^{-1}=\mathrm{id}_M$$ and the matrix $F_-$ of the inverse transform is also less or equal to the smaller dimension, i.e. $\mathrm{rank}(F_-)\le\min(N,M)$.

We can write the inversion conditions as a matrix equation $$F^{-1}\cdot F = E_N$$ $$F\cdot F^{-1} = E_M$$ where $E$ is the identity matrix of the size specified in the subscript. The matrix multiplication can be translated to a rank inequality:

$$\min\left(\mathrm{rank}(F_-),\mathrm{rank}(F_+)\right)\geq\mathrm{rank}(E_N)=N$$ and $$\min\left(\mathrm{rank}(F_+),\mathrm{rank}(F_-)\right)\geq\mathrm{rank}(E_M)=M$$ because the product of two matrices has at most the rank of the matrix with the lesser rank. From above we also had $$\mathrm{rank}(F_-)\le\min(N,M)$$ and $$\mathrm{rank}(F_+)\le\min(N,M)$$

These four inequalities only allow for one solution, which is $M=N$. To see this, assume that for example $N<M$, then it follows that $\mathrm{rank}(F_-)=\mathrm{rank}(F_+)\leq N$ but also $\mathrm{rank}(F_+)\geq M$, from which $N\geq M$ would follow, making the assumption inconsistent. The same goes for assuming $N>M$.

That means the discrete Fourier transform must be between complex vector spaces of equal dimensions. Or in other words, the number of frequency bins must be equal to the number of time samples.

The proof above can of course be a single line if you already know that vector space isomorphisms require matching dimensions. Of course, some linear algebra is still necessary, but the rank formulas should be rather intuitive.