Discrete Orthogonality Relations for Cosines

[madness]

TL;DR Summary

Sum rather than integral versions of orthogonality relations

Hi all,

I've come across some problem where I have terms such as ##\sum_{j=1}^N \cos(2 \pi j k /N) \cos(2 \pi j k' /N)##, or ##\sum_{j=1}^N \cos(2\pi j k/ N)##, or ## \sum_{j=1}^N \cos(2\pi j k/ N) \cos(\pi j) ##. In all cases we have the extra condition that ##1 \le k,k' \le N/2-1## (and ##k,k'## are integers of course, and ##N## is even.).

If these were integrals rather than sums I would be able to apply standard orthogonality relations. In fact, they seem to obey orthogonality relations when I compute them in Matlab (e.g., ##\sum_{j=1}^N \cos(2 \pi j k /N) \cos(2 \pi j k' /N) = N/2 \delta_{k,k'}##). However, if I plug them into Mathematica I get quite nasty expressions out involving functions like sec, cosec, etc. Does anyone know if there are any simple relations for these things?

 

[Arne]

Hello!

We can verify the relations if we assume limits [itex]j=0...N-1[/itex]. Then a sum of an exponential function can be evaluated with the geometric series [itex]\sum_{j=0}^{N-1} a^j = \frac{1 - a^N}{1-a}[/itex] such that
[tex]\sum_{j=0}^{N-1} \exp(\pm 2\pi i j k/N) = \sum_{j=0}^{N-1} (\exp(\pm 2\pi i k/N) )^j = \frac{1-\exp(\pm 2\pi i k)}{1-\exp(\pm 2\pi i k/N)} = 0[/tex]
since [itex]\exp(\pm 2\pi i k) = 1[/itex] for [itex]k \in \mathbb{Z}\setminus\{0\}[/itex]. For the case [itex]k = 0[/itex] the denominator also is 0, but then in the sum we add 1 N-times, so we get N as a result for the sum. Now remembering [itex]\cos(x) = (e^{ix}+e^{-ix})/2[/itex] we immediatly see that
[tex]\sum_{j=0}^{N-1} \cos(2\pi j k/N) = \begin{cases}0, & k \neq 0 \\ N, & k = 0\end{cases}[/tex]
If we now remember [itex]\cos(x)\cos(y) = (\cos(x-y) + \cos(x+y))/2 [/itex] we get
[tex] \begin{aligned}
\sum_{j=0}^{N-1} \cos(2\pi j k/N) \cos(2\pi j k' /N) &= \frac{1}{2}\sum_{j=0}^{N-1} \cos(2\pi j (k-k')/N) + \frac{1}{2}\sum_{j=0}^{N-1} \cos(2\pi j (k+k')/N) \\
&= \frac{N}{2} \delta_{k,k'} + \frac{N}{2} \delta_{k,-k'}
\end{aligned}[/tex]
but [itex]k,k' > 0[/itex] so just the former term.
In the case of limits [itex]j=1...N[/itex] subtact the [itex]j=0[/itex] term which is 1, and add the [itex]j = N[/itex] term, which is also 1 since k is an integer, so both cancel each other. So the relations still hold. In the case of the exponential in the sum, one can also think about pulling a factor [itex]\exp(\pm 2\pi i k/N) = 1[/itex] out of the sum and adjust the limits [itex]j \to j+1[/itex], to get the limits [itex]j=0...N-1[/itex] and proceed as described above (This is basically the same as just using the formula [itex]\sum_{j=1}^{N} a^j = \frac{a(1 - a^N)}{1-a}[/itex] where then the bracket in the numerator again is zero).

For the case with the [itex]\cos(j \pi)[/itex] you might want to try a similar calculation and see what happens.

I hope this helps. Best wishes,

Arne

 

[Svein]

I would start with the expression [itex]\cos(A)\cos(B)=\frac{1}{2}(\cos(A+B)+\cos(A-B)) [/itex]

 

[madness]

Hello!

We can verify the relations if we assume limits [itex]j=0...N-1[/itex]. Then a sum of an exponential function can be evaluated with the geometric series [itex]\sum_{j=0}^{N-1} a^j = \frac{1 - a^N}{1-a}[/itex] such that
[tex]\sum_{j=0}^{N-1} \exp(\pm 2\pi i j k/N) = \sum_{j=0}^{N-1} (\exp(\pm 2\pi i k/N) )^j = \frac{1-\exp(\pm 2\pi i k)}{1-\exp(\pm 2\pi i k/N)} = 0[/tex]
since [itex]\exp(\pm 2\pi i k) = 1[/itex] for [itex]k \in \mathbb{Z}\setminus\{0\}[/itex]. For the case [itex]k = 0[/itex] the denominator also is 0, but then in the sum we add 1 N-times, so we get N as a result for the sum. Now remembering [itex]\cos(x) = (e^{ix}+e^{-ix})/2[/itex] we immediatly see that
[tex]\sum_{j=0}^{N-1} \cos(2\pi j k/N) = \begin{cases}0, & k \neq 0 \\ N, & k = 0\end{cases}[/tex]
If we now remember [itex]\cos(x)\cos(y) = (\cos(x-y) + \cos(x+y))/2 [/itex] we get
[tex] \begin{aligned}
\sum_{j=0}^{N-1} \cos(2\pi j k/N) \cos(2\pi j k' /N) &= \frac{1}{2}\sum_{j=0}^{N-1} \cos(2\pi j (k-k')/N) + \frac{1}{2}\sum_{j=0}^{N-1} \cos(2\pi j (k+k')/N) \\
&= \frac{N}{2} \delta_{k,k'} + \frac{N}{2} \delta_{k,-k'}
\end{aligned}[/tex]
but [itex]k,k' > 0[/itex] so just the former term.
In the case of limits [itex]j=1...N[/itex] subtact the [itex]j=0[/itex] term which is 1, and add the [itex]j = N[/itex] term, which is also 1 since k is an integer, so both cancel each other. So the relations still hold. In the case of the exponential in the sum, one can also think about pulling a factor [itex]\exp(\pm 2\pi i k/N) = 1[/itex] out of the sum and adjust the limits [itex]j \to j+1[/itex], to get the limits [itex]j=0...N-1[/itex] and proceed as described above (This is basically the same as just using the formula [itex]\sum_{j=1}^{N} a^j = \frac{a(1 - a^N)}{1-a}[/itex] where then the bracket in the numerator again is zero).

For the case with the [itex]\cos(j \pi)[/itex] you might want to try a similar calculation and see what happens.

I hope this helps. Best wishes,

Arne

You're exactly right. For more information I was computing the sum of squared eigenvalues of a circulant matrix. In the equation I was using the eigenvalues are indexed from 0 to N-1 and I hadn't noticed that.

 

[Arne]

You're exactly right. For more information I was computing the sum of squared eigenvalues of a circulant matrix. In the equation I was using the eigenvalues are indexed from 0 to N-1 and I hadn't noticed that.

It doesn't actually matter if we use limits j=0...N-1 or j=1...N since the functions are N-periodic and the j=0 term is exacly the same as the j=N term. But I usually find it conceptually easier to work with j=0...N-1.

 

[madness]

Ok, I've become stuck on another problem now. Is it possible to solve ## \int_{-\pi}^{\pi} y(\theta) y(\theta+ \frac{2\pi k}{N}) d\theta = \frac{1}{N} \sum_{j=0}^{N-1} \lambda_j \cos \left(\frac{2\pi jk}{N}\right) ## to find y? The solution should be hold for all ##0\le k \le N/2## (i.e. it shouldn't vary with k). I'm assuming y is 2pi-periodic, and symmetric about 0. I want to use the convolution theorem but not sure what to do about the circular domain rather than infinite one.

I think the thing to do might be to expand y into a Fourier series, but I would need to find the Fourier coefficients of ##y(\theta) y(\theta+ \frac{2\pi k}{N})## in terms of the Fourier coefficients of y.

 

[Arne]

Ok, I've become stuck on another problem now. Is it possible to solve ## \int_{-\pi}^{\pi} y(\theta) y(\theta+ \frac{2\pi k}{N}) d\theta = \frac{1}{N} \sum_{j=0}^{N-1} \lambda_j \cos \left(\frac{2\pi jk}{N}\right) ## to find y? The solution should be hold for all ##0\le k \le N/2## (i.e. it shouldn't vary with k). I'm assuming y is 2pi-periodic, and symmetric about 0. I want to use the convolution theorem but not sure what to do about the circular domain rather than infinite one.

I think the thing to do might be to expand y into a Fourier series, but I would need to find the Fourier coefficients of ##y(\theta) y(\theta+ \frac{2\pi k}{N})## in terms of the Fourier coefficients of y.

Could you clarify how exactly you would like to use the convolution theorem? There is a version for Fourier coefficients
https://en.wikipedia.org/wiki/Convo...ution_theorem_for_Fourier_series_coefficients
but I don't really see how this might help. Anyway, if you find you find a solution, please make it available, because I would find it very interesting and I have no idea how i would solve this

 

[madness]

How about this? ## y(\theta) = \sqrt{\frac{2}{N}} \sum_{j=0}^{N-1} \sqrt{\lambda_j} \cos\left(j\theta\right) ##. I think ## y(\theta) = \sqrt{\frac{2}{N}} \sum_{j=1}^{N} \sqrt{\lambda_j} \cos\left(j\theta\right) ## with ##\lambda_0 = \lambda_N## also works.

 

[madness]

Sorry to keep coming back to this but I've gotten myself thoroughly confused and was hoping someone could help. Here is the setup:

Consider a set of functions ##y_i(\theta)## with ##i = 1...N## such that ##y_1(-\theta) = y_1(\theta)## and ##y_{i+k}(\theta) = y_i(\theta + \frac{2\pi k}{N})##. Define ##\Sigma_{ij} = (2\pi)^{-1} \int_{-\pi}^{\pi} y_i(\theta) y_j(\theta) d\theta##. My goal is to find out what the functions ##y_i(\theta)## are given that we have chosen in advance the eigenvalues ##\lambda_j## of ##\Sigma##.

The first thing to note is that ##\Sigma_{ij} \equiv \Sigma_{|i-j|}##, i.e. it depends only on the absolute difference between i and j, therefore being a symmetric circulant matrix. Now we know what the eigenvalues of a symmetric circulant matrix are, in particular ##\lambda_j = \Sigma_0 + 2\sum_{k=1}^{N/2-1} \Sigma_k \cos\left(\frac{2\pi j k}{N}\right) + \Sigma_{N/2} \cos(\pi j)##. But using the orthogonality relations kindly pointed out by Arne we can invert that relation to obtain ##\Sigma_k = \frac{1}{N}\sum_{j=0}^{N-1} \lambda_j \cos(\frac{2\pi j k}{N})##. Now assume that ##y_i(\theta)## can be expressed as a Fourier series, ##y_1(\theta) = \frac{a_0}{2} + \sum_{n=0}^\infty a_n \cos(n \theta) ## (there are no ##\sin## terms because ##y_1## is an even function). Then we have that ##\Sigma_k =\frac{1}{2}\sum_{n=0}
^{\infty} a_n^2 \cos\left(\frac{2\pi k n}{N}\right)##. Thus, we have two expressions for ##\Sigma_k##, and we can match the coefficients in the two expressions using the orthogonality relation again. This gives ##a_n = \sqrt{\frac{2}{N}} \sqrt{\lambda_n}##, and ##a_n = 0## for ##n > N-1##.

I don't see how this result can be correct. In particular, I can find functions with infinitely many Fourier components, such as ##y_i(\theta) = e^{\kappa \cos(\theta + 2\pi (i-1)/N)}##, which would satisfy all the conditions of the problem and yet don't conform to the solution I've identified. I've gone through my derivations a few times and I can't identify what the problem is!