Orthogonality in Discrete Fourier Transforms

[bdforbes]

My professor stated that the following orthogonality condition holds:

$$\sum_{n=0}^N cos(2\pi mn/N)cos(2\pi kn/N)=0$$

where m != k, and 0<= m,k < N.

I couldn't prove this, so I plugged in specific values: N=4, m=1, k=3. I found that the sum equals 2. Likewise for other situations where m+k=N, it comes out non-zero.

Is the condition incorrect?

 

[bdforbes]

I'm absolutely sure that my calculations are correct. This seems similar to resonance; at a particular frequency the components resonate and reinforce each other, whereas for other frequencies there is no resonance and they cancel to zero. It seems like this then implies there are only N/2 mutually orthogonal cos() basis functions and N/2 mutually orthogonal sin() basis functions. This is strange though because there are 2N mutually orthogonal complex exponentials which have the following orthogonality condition:

$$\sum_{n=0}^{N-1} \left(e^{ \frac{2\pi i}{N} kn}\right) \left(e^{-\frac{2\pi i}{N} k'n}\right) =N~\delta_{kk'}$$

where k,k' range between -(N-1) and +(N-1)

 

[matt grime]

There are only N linearly independent exponentials:

exp(2ki\pi/N)

as k goes from 0 to N-1 (or 1 to N).

Notice that there are actually 2N-1 integers in the range -N+1 to N-1, anyway.

 

[bdforbes]

Hmm. So DFTs only have positive exponentials but FTs have positive AND negative?

In any case, it still appears that the given orthogonality condition for the cosines is incorrect, right?

 

[matt grime]

Well, the DFT is explained as being over the complex numbers, and FT over the reals, usually. So a 2N dimensional real space is N complex dimensional, and you see everything is consistent.

If you think about attempting to extract cos or sin from the exponential version using only *real* coefficients, then you need both the +ve and -ve exponents. I'm being reticent on the original question, not because you're wrong, but because I haven't figured out what your professor was attempting to say: you should speak to him, it would be better all round.

 

[bdforbes]

That makes sense now. In FTs we have the time domain and frequency domain, both of which are in the reals, whereas in DFTs, we pull coefficients from the complex numbers. So that part is solved, we still have the same number of mutually orthogonal basis functions.

I'll ask my professor today about the original problem. The bottom line is that we need a condition that allows us to pull the coefficients a_m and b_m out of this sum:

$$\frac{a_0}{2}+\sum_{m=1}^{N-1}\left[a_m cos(2\pi mn/N)+b_m sin(2\pi mn/N)\right]$$

With continuous time we would just multiply by a cos or sin, and integrate over all time, but in the discrete case, we have to sum with respect to the N samples in time we are taking.
The sum above really appears to have non-orthogonal components. Wouldn't it be equivalent to just have the sum

$$\sum_{m=1}^{\left\lfloor \frac{N+1}{2}\right\rfloor$$

since this sums over a maximal set of mutually orthogonal functions?