# Integer eigenvalues of a class of matrices inspired by Prof. Zhi-Wei Sun's conjecture

Theorem: Let $$n>1$$ be an odd number and $$\zeta$$ a primitive $$n$$-th root of unity. Then $$\begin{eqnarray} &&\sum_{\tau\in D(n-1)}\mathrm{sign}(\tau)\prod_{j=1}^{n-1}\frac{1}{1-\zeta^{j-\tau(j)}}= \frac{(-1)^{\frac{n-1}{2}}}{n}\left(\frac{n-1}{2}!\right)^2. ~~~~~~~(1) \end{eqnarray}$$ Here $$D(n)$$ denotes the set of all derangements $$\tau$$ of indices $$j=1,\ldots,n$$ such that $$\tau(j)\neq j$$ for all $$j=1,\ldots,n$$.

The above theorem was conjectured by my colleague Prof. Zhi-Wei Sun and proved by my other colleague Prof. Xuejun Guo. For more details, see here and here.

Let $$A$$ denote the Hermitian matrix with diagonal elements equal to zero and off-diagonal elements $$(a_{ij})_{i\neq j}$$ given by $$\begin{eqnarray} \frac{1}{1-x_{i-j}}, \quad\quad 1\leq i\neq j\le n-1, \end{eqnarray}$$ where $$\begin{eqnarray} x_k=\zeta^k, \quad \forall~k. \end{eqnarray}$$ Clearly the left-hand side of (1) is equal to $$\det(A)$$. It is more convenient to multiply $$A$$ from right with the following diagonal matrix $$B_s$$ whose diagonal entries are given as $$\begin{eqnarray} 1-x_{is}, \quad\quad 1\leq i\le n-1, \end{eqnarray}$$ by fixing any $$s\in\{-\frac{n-1}{2},-\frac{n-3}{2},\cdots,-1,1,2,\cdots,\frac{n-1}{2}\}$$. Define $$C_s:= AB_s$$. If $$n$$ is prime or $$s=1$$, we have $$\begin{eqnarray}\label{eqn:keyEq} \det(C_s)=\det(AB_s)=\det(A)\det(B_s)=n\det(A). \end{eqnarray}$$ The observation that $$\det(B_s)=n$$ when $$n$$ is prime or $$s=1$$ can be easily proved by comparing the coefficient of the constant term in the following polynomial equation after cancelling $$1$$ and the trivial term $$x$$ from both sides: $$\begin{eqnarray} (1-x)^n=1. \end{eqnarray}$$ Note that if $$n$$ is prime, then $$(x_{js})$$ is a permutation of $$(x_j)$$ for any fixed $$s\in\{-\frac{n-1}{2},\cdots,-1,1,\cdots,\frac{n-1}{2}\}$$. In this case $$js_1\not\equiv js_2~\pmod{n}$$ if $$s_1\not\equiv s_2~\pmod{n}$$.

For general odd $$n>1$$, Equation (1) is equivalent to the following identity: $$\begin{eqnarray}\label{eqn:keyEq1} \det(C_1)=\det(AB_1)=\det(A)\det(B_1)=(-1)^{\frac{n-1}{2}}\left(\frac{n-1}{2}!\right)^2. \end{eqnarray}$$

To analyze (1), we use the following lemma to obtain the following identity for any fixed $$s\in\{0,1,2,\cdots,\frac{n-3}{2},\frac{n+1}{2},\cdots,n-1\}$$ and $$k\in\{1,2,\ldots,n-1\}$$: $$\begin{eqnarray} \sum^{n-1}_{j=1,j\neq k}\frac{1-x_{j(\frac{n-1}{2}-s)}}{1-x_{k-j}}x_{js}&=&\sum^{n-1}_{j=1,j\neq k}\frac{x_{js}-x_{j\frac{n-1}{2}}}{1-x_{k-j}}\\ &=&\left(\frac{n-1}{2}-s\right)x_{ks}. \end{eqnarray}$$ Note that the above equality also holds for $$s=\frac{n-1}{2}$$, but we do not need this fact. It shows that $$s$$ is an eigenvalue of $$C_{s}$$ for each $$s\in\{-\frac{n-1}{2},\cdots,-1,1,\cdots,\frac{n-1}{2}\}$$. If we can show that $$s$$ is also an eigenvalue of $$C_{1}$$ (numerically verified), then $$\begin{eqnarray} \det(C_1)=\prod_{-\frac{n-1}{2}\le s\le \frac{n-1}{2},s\neq0} = (-1)^{\frac{n-1}{2}}\left(\frac{n-1}{2}!\right)^2. \end{eqnarray}$$

Lemma: For any integers $$s\in\{0,1,\ldots,n-1\}$$ and $$k\in\{1,2,\ldots,n-1\}$$, we have $$\begin{eqnarray} \sum^{n-1}_{j=1,j\neq k}\frac{x_{js}}{1-x_{k-j}}=\left(\frac{n-1}{2}-s\right)x_{ks}-\frac{1}{1-x_k}. \end{eqnarray}$$

Proof of the lemma: $$\begin{eqnarray} \sum^{n-1}_{j=1,j\neq k}\frac{x_{js}}{1-x_{k-j}}&=&x_{ks}\sum^{n-1}_{j=1,j\neq k}\frac{x_{(j-k)s}}{1-x_{k-j}}\\ &=&x_{ks}\left[\sum^{n-1}_{j=1}\frac{x_{js}}{1-x_{-j}}-\frac{x_{-ks}}{1-x_k}\right]. \end{eqnarray}$$ Note that $$\begin{eqnarray} \sum^{n-1}_{j=1}\frac{x_{js}}{1-x_{-j}}&=&\sum^{n-1}_{j=1}\left[\frac{x_{j(s-1)}}{1-x_{-j}}+x_{js}\right]\\ &=&-1+\sum^{n-1}_{j=1}\frac{x_{j(s-1)}}{1-x_{-j}}\\ &=&\cdots\\ &=&-s+\sum^{n-1}_{j=1}\frac{1}{1-x_{-j}}\\ &=& \frac{n-1}{2}-s. \end{eqnarray}$$ The last equality is obtained by comparing the coefficient of $$x^{n-2}$$ in the following polynomial equation after cancelling the trivial term $$x^n$$ and dividing by $$n$$ on both sides: $$\begin{eqnarray} \left(1-\frac{1}{x}\right)^n=1. \end{eqnarray}$$

Remark: Numerical experiments showed that $$s$$ is indeed an eigenvalue of $$C_1$$ for every $$s\in\{-\frac{n-1}{2},\cdots,-1,1,\cdots,\frac{n-1}{2}\}$$ and the eigenvalues of $$C_s$$ are just a permutation of those of $$C_{s'}$$ as long as both $$(x_{js})$$ and $$(x_{js'})$$ are permutations of $$(x_{j})$$.

Question: How do we prove that $$s$$ is an eigenvalue of $$C_1$$ for every $$s\in\{-\frac{n-1}{2},\cdots,-1,1,\cdots,\frac{n-1}{2}\}$$?

• Did you try to guess the eigenvectors using numerical evidence? Jun 7 at 13:58
• Yes, but I have not found any pattern yet. Even the simplest case n=3 or 5 does not offer much useful information about the general pattern.
– KLiu
Jun 8 at 1:49

Fourier transform does it.

Denote by $$u_j$$ $$(j=0,1,\ldots,n-1$$) the column-vector with coordinates $$(x_{ji})_{1\leqslant i\leqslant n-1}$$. Note that $$u_0+u_1+\ldots+u_{n-1}=0$$ and any $$n-1$$ vectors $$u_i$$'s are linearly independent. The idea is to write the matrix $$C_1=AB_1$$ in the basis $$\{u_0,u_1,\ldots,u_{n-1}\}\setminus \{u_{(n-1)/2}\}$$. It has a form $$\pmatrix{X&Y\\0&Z}$$, where $$X,Z$$ are lower-triangular, thus its eigenvalues are diagonal elements of $$X$$ and $$Z$$, and these are exactly $$-\frac{n-1}{2},\cdots,-1,1,\cdots,\frac{n-1}{2}$$. See details below.

Lemma 1. For $$\ell\in \{1,2,\ldots,n\}$$ we have $$\sum_{j=1}^{n-1}\frac{x_{j\ell}}{x_j-1}=\frac{n-1}2-\ell+1.$$

Proof. For $$1\leqslant j\leqslant n-1$$ we have $$(x_j-1)((n-1)+(n-2)x_j+(n-3)x_{2j}+\ldots+x_{(n-2)j})\\=(1+x_j+x_{2j}+\ldots+x_{(n-1)j})-n=-n.$$ Therefore $$\sum_{j=1}^{n-1}\frac{x_{j\ell}}{x_j-1}=-\frac1n\sum_{j=1}^{n-1}x_{j\ell} \sum_{s=1}^{n}(s-1)x_{j(n-s)}=\frac{n-1}2-\frac1n\sum_{j=0}^{n-1}x_{j\ell} \sum_{s=1}^{n}(s-1)x_{j(n-s)}\\ =\frac{n-1}2-\frac1n\sum_{s=1}^{n} \sum_{j=0}^{n-1}(s-1)x_{j(n-s+\ell)}=\frac{n-1}2-\ell+1,$$ since $$\sum_{j=0}^{n-1}x_{j(n-s+\ell)}=n\cdot \delta_{s-\ell}$$. $$\square$$

Lemma 2. For $$p=0,1,\ldots,n-2$$ we have $$C_1u_p=\left(\frac{n-1}2-p\right)u_p-\left(\frac{n-1}2-p-1\right)u_{p+1}.$$ Also, for $$p=n-1$$ we get $$C_1u_{n-1}=-\frac{n-1}2u_{n-1}-\frac{n-1}2 u_0.$$

Proof. For $$p=0,1,\ldots,n-2$$ we have $$\left[C_1u_p\right]_i=\sum_{1\leqslant j\leqslant n-1,j\ne i} \frac{1-x_j}{1-x_{i-j}}x^{pj}=\sum_{1\leqslant j\leqslant n-1,j\ne i} \frac{x_{(p+1)j}-x_{(p+2)j}}{x_j-x_{i}}\\ =\sum_{0\leqslant j\leqslant n-1,j\ne i} \frac{x_{(p+1)j}-x_{(p+2)j}}{x_j-x_{i}}=x_{pi} \sum_{0\leqslant j\leqslant n-1,j\ne i} \frac{x_{(p+1)(j-i)}}{x_{j-i}-1} -x_{(p+1)i}\sum_{0\leqslant j\leqslant n-1,j\ne i} \frac{x_{(p+2)(j-i)}}{x_{j-i}-1}\\ =\left(\frac{n-1}2-p\right)x_{pi}-\left(\frac{n-1}2-p-1\right)x_{(p+1)i}$$ by Lemma 1. For $$p=n-1$$ the last coefficient of $$x_{(p+1)i}$$ corresponds to the case $$\ell=1$$ in Lemma 1 and therefore equals $$-(\frac{n-1}2-1+1)=-\frac{n-1}2$$. $$\square$$

So, we proved the aforementioned block representation of $$C_1$$ in the basis $$\{u_0,u_1,\ldots,u_{n-1}\}\setminus \{u_{(n-1)/2}\}$$.

• What a beautiful proof! I have also obtained Lemma 1 before posting the question but never thought about using the $n-1$ vectors as a basis!
– KLiu
Jun 8 at 10:17
• An extension of Lemma 1 appeared as Lemma 2.1 in the preprint of Wang and Sun, see arxiv.org/abs/2206.02589 Jun 8 at 11:10