# A matrix w/integer eigenvalues and trigonometric identity

Any intuition and/or rigorous arguments on the proofs of the following statements would be appreciated:

Let $n$ be a natural number. (a) Consider the following Toeplitz/circulant symmetric matrix:

$$\Lambda_{kl} = \begin{cases}\frac{2n(n+1)}{3}, & k = l, \\[6pt] \frac{-1}{1-\cos\frac{2\pi(k-l)}{2n+1}}, & k \ne l,\end{cases}$$

where $k,l = 1,2, \ldots, 2n+1$.

Prove that its eigenvalues are natural numbers(!)

$$2n, 4n-2, 6n-6, \ldots, n(n+1)$$

with multiplicity $2$ and $0$ w/multiplicity $1$.

(b) Find a formula for the right signs in the following trigonometric identity

$$\tan\left(\frac{l\pi}{2n+1}\right) = 2\sum_{k=1}^n (\pm)\sin\left(\frac{k\pi}{2n+1}\right),\qquad l = 1,2,\ldots, n.$$

and show that the signs are uniquely determined in the case of prime $2n+1$.

The problems (that are formulated to be self-contained) arise from discrete approximation of continuous inverse boundary problem (see http://en.wikibooks.org/wiki/On_2D_Inverse_Problems for background) and the statements were formulated w/computer help.

-
A tip for (b): Multiply through by $\cos(l\pi/(2n+1))$, and invoke the identity $2\sin A \cos B = \sin(A+B)+\sin(A-B)$, so that the right-hand side becomes $$\sum_k \; \pm \left(\;\sin\frac{(k+l)\pi}{2n+1}+\sin\frac{(k-l)\pi}{2n+1}\;\right)$$ Somewhere amid all those sines, you'll get an instance equivalent to $\sin(l\pi/(2n+1))$. Make that pair's "$\pm$" a "$+$"; then, ignore the $\sin(l\pi/(2n+1))$ part of that pair (as it matches the left-hand side), and set about getting the remaining sines to cancel. – Blue May 16 '13 at 7:26
Seems like a good step, but how can we cancel the remaining sines? Also, can we see that $2n+1$ being a prime plays a role? – DVD May 16 '13 at 7:34
I've just played with a few small examples. If the "other" sine in that initial "$+$" pair isn't itself zero, I've been able to find a matching sine in another pair to cancel it (with an appropriate "$\pm$" choice), and then the other sine from that pair leads me to a matching sine in another pair, and so forth. (Primality may help show that that path from that initial sine is unique.) When that other sine in the initial pair is itself zero, matching sines don't seem to cancel each other; the cancellation is more subtle. But, again, I've just played with a few small examples. – Blue May 16 '13 at 7:49
The ways in which people use TeX on this site are sometimes quite baffling. Daved: Why use a "\displaystyle" in your piecewise definition of $\Lambda_{k\ell}$ instead of an actual display, and why use the \mbox{} construction in "cases" instead of alignment tabs? (I altered both and did some other TeX improvements.) – Michael Hardy May 16 '13 at 17:55
Was not sure how these work and just used a template. Thank you for your help. – DVD May 16 '13 at 22:46

Since (b) has been largely answered in the comments, I'll deal with (a) here. It is the case here that there is a very simple (and otherwise useful and well-known) basis of eigenvectors. Let $\zeta$ be a primitive $2n+1$-th root of unity. Our eigenvectors for $\Lambda$ will be the “cyclic” vectors, whose coordinates are successive powers of a root of unity :

$$C_s=(\zeta^s,\zeta^{2s},\zeta^{3s}, \ldots ,\zeta^{(2n)s},1) \ (0 \leq s \leq 2n) \tag{1}$$

Let us compute all the coordinates of $\Lambda C_s$ ; in other words, we must compute the sum

$$f(i,s)=\sum_{j=1}^{2n+1} \Lambda_{ij} \zeta^{sj} \tag{2}$$

We have $f(i,s)=\frac{2}{3}n(n+1)\zeta^{si}+g(i,s)$, where

$$g(i,s)=\sum_{j\neq i} \frac{\zeta^{sj}}{\frac{\zeta^{i-j}+\zeta^{j-i}}{2}-1}= \sum_{t\neq 0} \frac{\zeta^{s(i+t)}}{\frac{\zeta^{-t}+\zeta^{t}}{2}-1}= 2\zeta^{si}\sum_{t=1}^{2n} \frac{(\zeta^t)^{s+1}}{(\zeta^{t}-1)^2}= 2\zeta^{si}\sum_{\eta\in U, \eta\neq 1} \frac{\eta^{s+1}}{(\eta-1)^2} \tag{3}$$

where $U$ is the set of all $(2n+1)$-th roots of unity. There are classical techniques to compute the RHS of (3) above ; see the answer to this question, where the final formula obtained is

$$\sum_{\eta\in U, \eta\neq 1} \frac{\eta^{s+1}}{(\eta-1)^2} =\frac{6(2n+1-s)s-((2n+1)^2-1)}{12}= \frac{s(2n+1-s)}{2}-\frac{n^2+n}{3} \tag{4}$$

Combining (3) with (4), the terms in $\frac{n^2+n}{3}$ cancel out and we thus obtain

$$\sum_{j=1}^{2n+1} \Lambda_{ij} \zeta^{sj}=s(2n+1-s)\zeta^{si} \tag{5}$$

Or, to express things vectorially,

$$\Lambda C_s=s(2n+1-s) C_s \tag{6}$$

So $C_s$ is an eigenvector associated to the eigenvalue $s(2n+1-s)$ as wished.

-

This is not a complete answer to (a), but it may be a start. It also explains the repeated eigenvalues.

It is known that a circulant matrix is diagonalized by the Fourier matrix and the eigenvalues of a circulant matrix are given by the discrete Fourier transform of its first row. See chapter 3 of here for a detailed explanation.

Let $c_j$ be the first row your matrix. Given the definition of $\Lambda$, we have

$$c_j = \begin{cases} 2n(n+1)/3, & j = 0 \\[6pt] \frac{-1}{1-\cos(\frac{2\pi j}{2n+1})}, & j = 1, \dots, 2n \\ \end{cases}$$

Let $\lambda_m$ be the eigenvalues of $\Lambda$. Then

\begin{align} \lambda_m &= \sum_{j=0}^{2n}c_j \exp \left( -\frac{2\pi imj}{2n+1} \right) \\ &= \frac{2n(n+1)}{3} + \sum_{j=1}^{2n} c_j \exp \left( -\frac{2\pi imj}{2n+1} \right), \qquad m = 0, \dots, 2n \end{align}

The imaginary part of this sum will vanish, so we're left with

$$\lambda_m = \frac{2n(n+1)}{3} + \sum_{j=1}^{2n} \frac{\cos(\frac{2\pi jm}{2n+1})}{\cos(\frac{2\pi j}{2n+1})-1}$$

A closed form evaluation for this sum will solve the problem. I don't have any headway on this, but here are two observations.

Observation 1 $\qquad \lambda_0 = 0$

Proof

\begin{align} \lambda_0 &= \frac{2n(n+1)}{3} + \sum_{j=1}^{2n} \frac{1}{\cos(\frac{2\pi j}{2n+1}) - 1}\\ &= \frac{2n(n+1)}{3} -\frac{1}{2} \sum_{j=1}^{2n} \csc^2(\frac{\pi j}{2n+1}) \\ &= \frac{2n(n+1)}{3} -\frac{1}{2} \frac{1}{3} ((2n+1)^2 -1) \\ &= \frac{2n(n+1)}{3} - \frac{1}{6} (4n^2 + 4n) \\ &= 0 \end{align}

In the first equality above, I've used the double angle identity, $sin^2(\theta) = \frac{1}{2}(1-cos(2\theta))$, and in the second the identity $\sum_{k=1}^{n-1} csc^2(\frac{k\pi}{n}) = \frac{1}{3}(n^2 - 1)$, see proof below.

Observation 2 $\qquad \lambda_m = \lambda_{2n + 1 - m}$

Proof

$$\lambda_m = \frac{2n(n+1)}{3} + \sum_{j=1}^{2n} \frac{\cos(\frac{2\pi jm}{2n+1})}{\cos(\frac{2\pi j}{2n+1})-1}$$

$$\lambda_{2n + 1 - m} = \frac{2n(n+1)}{3} + \sum_{j=1}^{2n} \frac{\cos(\frac{2\pi j(2n + 1 - m)}{2n+1})}{\cos(\frac{2\pi j}{2n+1})-1}$$

The denominators in the fractions are the same. The result then follows by noticing that

\begin{align} \cos \left( \frac{2\pi j (2n + 1 -m )}{2n+1} \right) &= \cos \left( 2\pi j - \frac{2\pi j m}{2n+1} \right) \\ &= \cos \left( \frac{2\pi jm}{2n+1} \right) \end{align}

Proof of $\sum_{k=1}^{n-1} csc^2(\frac{k\pi}{n}) = \frac{1}{3}(n^2 - 1)$

This proof follows exercise 8 in chapter 5 of Stromberg, An Introduction to Classical Real Analysis.

Begin with De Moivre's formula: $$\cos(nx) + i\sin(nx) = (\cos(x) + i\sin(x))^n$$

Expanding the RHS via the Binomial Theorem gives $$\cos(nx) + i\sin(nx) = \sum_{k=0}^{n}\binom{n}{k}\cos ^{n-k}(x) (i\sin(x))^k$$

Equate imaginary parts, the RHS is imaginary for $k$ odd, so set $k = 2j+1$

$$\sin(nx) = \sum_{j=0}^{\lfloor{\frac{n-1}{2}} \rfloor}(-1)^j\binom{n}{2j+1}\cos ^{n-2j-1}(x)\sin ^{2j+1}(x)$$

Setting $n = 2m+1$ and multiplying outside the sum by $\sin ^{2m}(x)$ and dividing on the inside gives

\begin{align} \sin((2m+1)x) =& \sin ^{2m+1}(x)\sum_{j=0}^{m} (-1)^j\binom{2m+1}{2j+1}\cos ^{2(m-j)}(x)\sin ^{2(j-m)}(x) \\ =& \sin ^{2m+1}(x)\sum_{j=0}^{m} (-1)^j\binom{2m+1}{2j+1}(\cot ^2(x))^{m-j} \end{align}

Now $\sin((2m+1)x)$ has roots $x = \frac{k\pi}{{2m+1}}, k = 1, \dots, m$. This implies that the polynomial

$$\sum_{j=0}^{m} (-1)^j\binom{2m+1}{2j+1}t^{m-j}$$ has roots $t = \cot ^2(\frac{k\pi}{2m+1}), k = 1 \dots m$. The sum of the roots of a polynomial of degree $m$ is equal to the negative of the coefficient of the $(m-1)$ degree term divided by the coefficient of the leading term. The leading term has coefficient $2m+1$, the $m-1$ degree term has coefficient $-\binom{2m+1}{3}$, thus the sum of the roots is $m(2m-1)/3$ and we have the identity

$$\sum_{k=1}^{m}\cot^2 \left( \frac{k\pi}{2m+1} \right) = \frac{m(2m-1)}{3}$$

Making the substitution $\csc^2 \theta = 1 + \cot ^2 \theta$ gives

$$\sum_{k=1}^{m} \csc^2 \left(\frac{k\pi}{2m+1} \right) = \frac{2}{3}m(m+1) \tag{1}$$

The statement to prove is $$\sum_{k=1}^{n-1} \csc^2 \left(\frac{k\pi}{n} \right) = \frac{1}{3}(n^2 - 1) \tag{2}$$

Making the substitution $n \rightarrow 2n + 1$, (2) is equivalent to $$\sum_{k=1}^{2n} \csc^2 \left(\frac{k\pi}{2n + 1} \right) = \frac{4}{3}n(n+1) \tag{3}$$

Noticing that $\csc\left(\frac{k\pi}{2n+1}\right) = \csc\left(\frac{(2n+1-k)\pi}{2n+1}\right)$, we have that the sum over the first $n$ indices in $(3)$ equals the sum over last $n$ indices and thus that $(1)$ is equivalent to $(3)$. $\Box$

-
Observation 1: There is only a statement but no proof at the link. Observation 2: Does it follow from the fact that $\Lambda$ is symmetric? – DVD May 20 '13 at 2:32
@Daved: In general a symmetric circulant matrix will not obey Observation 2. The symmetry implies that the imaginary part of the Fourier transform vanishes (eigenvalues are real). I have edited the original post to include a proof of the identity. There are more powerful techniques available to handle generalizations of this identity, see here – mathforfun May 20 '13 at 21:57