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.

Solution 1:

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.

Solution 2:

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$