Number of sine and cosine waves in an $N$-point DFT

Question

This is bound to be an embarrassingly simple question, but here it goes...

I was reading the chapter on discrete Fourier transforms (DFT) of this really didactic online book, The Scientist and Engineer's Guide to Digital Signal Processing by Steven W. Smith and I got stuck thinking about the last sentence in the caption to this illustration:

The parameter, $k$, determines the frequency of the wave. In an $N$ point DFT, $k$ takes on values between $0$ and $\color{red}{\frac{N}{2}}.$

He goes on to say with regards to the $32$-point DFT,

For example, Fig. 8-5 [not included here] shows some of the $17$ sine and $17$ cosine waves used in an N = 32 point DFT.

So it seems to indicate $16$ sine waves, or $(N/2)$, plus the constant component, and a parallel split for cosine waves.

However, the DFT is defined as

The DFT is defined as:

$$X(k)\equiv \sum_{n=0}^{N-1} x(n)\; \exp\left(\mathbf-i\frac{2\pi}{N}kn\right), \quad k=0,1,\dots,\color{red}{N-1}$$

which is $\color{red}{N}$ values of $k$, not $\color{red}{\frac{N}{2}}.$

And given Euler's formula:

$$e^{-ix}=\cos x - i \sin x$$

it seems as though there should be an equal number of sine and cosine basis equations: one of each frequency parameter $k$ for a total of $N$ sine and $N$ cosine.

Of course, at some points, the sine or cosine components will be zero (as we move around the complex plane, and depending on $N$), but not necessarily $\frac{N}{2}$. For instance, the $4$-point DFT would indeed either fall on the $x$-axis (real - cosine), or $y$-axis (imaginary - sine), splitting the basis function in half. Yet this seems to be a very sweet and unique example.

What am I missing?

Answer 1

There is no contradiction.

Both cases you have information from $ -\frac{ Fs }{ 2 } $ to $ \frac{ Fs }{ 2 } $.

The representation using Cosine ans Sine functions is using Real Functions.
Those functions are symmetric as Real Valued functions.
Namely if you a coefficient for a Sine in a given frequency it is for sure have energy on the negative frequency as well (See the DFT / Fourier Transform of Sine and Cosine).
Namely using those functions all needed it to go from $ 0 $ to $ \frac{ Fs }{ 2 } $ as the negative value is implicit.

On the other end, for the Complex Exponent the energy is one sided.
Hence you must go from $ -\frac{ Fs }{ 2 } $ to $ \frac{ Fs }{ 2 } $.

Answer 2

I haven't read that book, but I can surmise what the author wants to say. It has to do with the fact that the basis frequencies come in conjugate pairs. Suppose the number of point is $n=8$. By basic trigonometric identities, we have that, for $0 \leq m < 8$,

$$ \cos\Big(2\pi\frac{3}{8}m\Big) = \cos\Big(2\pi\frac{5}{8}m\Big) $$ and $$ \sin\Big(2\pi\frac{3}{8}m\Big) = -\sin\Big(2\pi\frac{5}{8}m\Big) \enspace. $$

This means that the coefficient that multiplies $e^{-i2\pi\frac{3}{8}m}$ is the complex conjugate of the one that multiplies $e^{-i2\pi\frac{5}{8}m}$. It also means that based on 8 samples per second, you cannot really deal with signals at 4 Hz or faster, which is why you need to sample at least twice sa fast as the maximum frequency in your signal, lest there should be aliasing.

Finally, all this means that signals that are sampled at 8 Hz can be seen as the sums of sine and cosine waves up to 4 Hz (and the 4 Hz component better be 0).