Discrete Orthogonality Relations for Cosines

[madness]

TL;DR

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 j=0...N-1. Then a sum of an exponential function can be evaluated with the geometric series \sum_{j=0}^{N-1} a^j = \frac{1 - a^N}{1-a} such that
\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
since \exp(\pm 2\pi i k) = 1 for k \in \mathbb{Z}\setminus\{0\}. For the case k = 0 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 \cos(x) = (e^{ix}+e^{-ix})/2 we immediatly see that
\sum_{j=0}^{N-1} \cos(2\pi j k/N) = \begin{cases}0, & k \neq 0 \\ N, & k = 0\end{cases}
If we now remember \cos(x)\cos(y) = (\cos(x-y) + \cos(x+y))/2 we get
\begin{aligned}<br /> \sum_{j=0}^{N-1} \cos(2\pi j k/N) \cos(2\pi j k&#039; /N) &amp;= \frac{1}{2}\sum_{j=0}^{N-1} \cos(2\pi j (k-k&#039;)/N) + \frac{1}{2}\sum_{j=0}^{N-1} \cos(2\pi j (k+k&#039;)/N) \\<br /> &amp;= \frac{N}{2} \delta_{k,k&#039;} + \frac{N}{2} \delta_{k,-k&#039;}<br /> \end{aligned}
but k,k&#039; &gt; 0 so just the former term.
In the case of limits j=1...N subtact the j=0 term which is 1, and add the j = N 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 \exp(\pm 2\pi i k/N) = 1 out of the sum and adjust the limits j \to j+1, to get the limits j=0...N-1 and proceed as described above (This is basically the same as just using the formula \sum_{j=1}^{N} a^j = \frac{a(1 - a^N)}{1-a} where then the bracket in the numerator again is zero).

For the case with the \cos(j \pi) 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 \cos(A)\cos(B)=\frac{1}{2}(\cos(A+B)+\cos(A-B))

 

[madness]

Hello!

We can verify the relations if we assume limits j=0...N-1. Then a sum of an exponential function can be evaluated with the geometric series \sum_{j=0}^{N-1} a^j = \frac{1 - a^N}{1-a} such that
\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
since \exp(\pm 2\pi i k) = 1 for k \in \mathbb{Z}\setminus\{0\}. For the case k = 0 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 \cos(x) = (e^{ix}+e^{-ix})/2 we immediatly see that
\sum_{j=0}^{N-1} \cos(2\pi j k/N) = \begin{cases}0, &amp; k \neq 0 \\ N, &amp; k = 0\end{cases}
If we now remember \cos(x)\cos(y) = (\cos(x-y) + \cos(x+y))/2 we get
\begin{aligned}<br /> \sum_{j=0}^{N-1} \cos(2\pi j k/N) \cos(2\pi j k&#039; /N) &amp;= \frac{1}{2}\sum_{j=0}^{N-1} \cos(2\pi j (k-k&#039;)/N) + \frac{1}{2}\sum_{j=0}^{N-1} \cos(2\pi j (k+k&#039;)/N) \\<br /> &amp;= \frac{N}{2} \delta_{k,k&#039;} + \frac{N}{2} \delta_{k,-k&#039;}<br /> \end{aligned}
but k,k&#039; &gt; 0 so just the former term.
In the case of limits j=1...N subtact the j=0 term which is 1, and add the j = N 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 \exp(\pm 2\pi i k/N) = 1 out of the sum and adjust the limits j \to j+1, to get the limits j=0...N-1 and proceed as described above (This is basically the same as just using the formula \sum_{j=1}^{N} a^j = \frac{a(1 - a^N)}{1-a} where then the bracket in the numerator again is zero).

For the case with the \cos(j \pi) 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!