2
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ Did you try to guess the eigenvectors using numerical evidence? $\endgroup$ Jun 7 at 13:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – KLiu
    Jun 8 at 1:49

1 Answer 1

5
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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! $\endgroup$
    – KLiu
    Jun 8 at 10:17
  • 2
    $\begingroup$ An extension of Lemma 1 appeared as Lemma 2.1 in the preprint of Wang and Sun, see arxiv.org/abs/2206.02589 $\endgroup$ Jun 8 at 11:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.