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

Question

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}\}$?

Answer 1

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}\}$.