Combinatorial Identities – Permanent Identities

co.combinatoricscombinatorial-identitiesnt.number-theorypermanent

The permanent $\mathrm{per}(A)$ of a matrix $A$ of size $n\times n$ is defined to be:

$$\mathrm{per}(A)=\sum_{\tau\in S_n}\prod_{j=1}^na_{j,\tau(j)}.$$

Let
$$A=\left[\tan\pi\frac{j+k}n\right]_{1\le j,k\le n-1},$$
$$B=\left[\sin\pi\frac{j+k}n\right]_{1\le j,k\le n-1},$$
$$C=\left[\cos\pi\frac{j+k}n\right]_{1\le j,k\le n-1},$$
$$D=\left[\sec\pi\frac{j+k}n\right]_{1\le j,k\le n-1}.$$

Motivated by Question 402249, I found the following

Conjecture 1. For any odd integer $n>1,$
$$(-1)^{(n-1)/2}\mathrm{per}(A)=\frac{2(n!!)^2}{n+1}\sum_{k=0}^{\frac{n-1}{2}}\frac{(-1)^k}{2k+1}. \tag{1}$$

Numerical calculations show that this is correct for $3 \leq n \leq 33$. See Question 402249 for details.

Inspired by Question 402572, I also found the following identities

Conjecture 2. For any odd integer $n>1,$

\begin{align}
(-1)^{(n-1)/2}\mathrm{per}(B)&=\frac{n!}{2^{n-2}(n+1)},\tag{2}
\\ \mathrm{per}(C)&={\frac{(n-1)!}{2^{n-1}}}\sum_{k=0}^{n-1}\frac{1}{\binom{n-1}{k}},\tag{3}
\\ \mathrm{per}(D)&= (n-2)!!^2\left( (-1)^{\frac{n+1}{2}}+2n\sum_{k=0}^{\frac{n-1}{2}} {\frac {\left( -1 \right) ^{k}}{2k+1} }
\right) .\tag{4}
\end{align}

Numerical calculations show that it is correct for $3 \leq n \leq 21$.

Question. Are these identities correct? How to prove them?

Best Answer

Let $\zeta$ be a primitive $n$-th root of unity. Then $$\prod_{j=1}^{n-1}(x-\zeta^j)=\frac{x^n-1}{x-1}=1+x+\cdots+x^{n-1}$$ and hence $$\sigma_k=\sum_{1\le i_1<\cdots<i_k\le n-1}\zeta^{i_1+\cdots+i_k}=(-1)^k$$ for all $k=1,\ldots,n-1$.

Observe that \begin{align*}\mathrm{per}[1-\zeta^{j+k}]_{1\le j,k\le n-1}=&\sum_{\tau\in S_{n-1}}\ \prod_{j=1}^{n-1}(1-\zeta^{j+\tau(j)}) \\=&\sum_{\tau\in S_{n-1}}1+\sum_{\tau\in S_{n-1}}\ \sum_{\emptyset\not=J\subseteq\{1,\ldots,n-1\}}(-1)^{|J|}\zeta^{\sum_{j\in J}\ (j+\tau(j))} \\=&(n-1)!+\sum_{\emptyset \not=J\subseteq \{1,\ldots,n-1\}}(-1)^{|J|}\zeta^{\sum_{j\in J}j}\sum_{\tau\in S_{n-1}}\zeta^{\sum_{j\in J}\ \tau(j)}. \end{align*} For $\emptyset \not=J\subseteq\{1,\ldots,n-1\}$, clearly \begin{align*}&\sum_{\tau\in S_{n-1}}\zeta^{\sum_{j\in J}\ \tau(j)} \\=&\sum_{1\le i_1<\cdots<i_{|J|}\le n-1}\zeta^{i_1+\cdots+i_{|J|}}\sum_{\tau\in S_{n-1}\atop\{\tau(j):\ j\in J\} =\{i_1,\ldots,i_{|J|}\}}1 \\=&|J|!(n-1-|J|)!\sigma_{|J|}=(-1)^{|J|}|J|!(n-1-|J|)!. \end{align*} Therefore \begin{align*}\mathrm{per}[1-\zeta^{j+k}]_{1\le j,k\le n-1}=&(n-1)!+\sum_{\emptyset\not=J\subseteq\{1,\ldots,n-1\}}|J|!(n-1-|J|)!\zeta^{\sum_{j\in J}\ j} \\=&(n-1)!\sum_{k=0}^{n-1}\frac{(-1)^k}{\binom{n-1}k}=(1-(-1)^n)\frac{n!}{n+1}. \end{align*} Then the conjectural identity $(2)$ follows from this since $$\sin\pi\frac{j+k}n=\frac{e^{-\pi i(j+k)/n}}{2i}\left(e^{2\pi i(j+k)/n}-1\right).$$

The identities $(3)$ can be proved similarly, in fact we have $$\mathrm{per}[1+\zeta^{j+k}x]_{1\le j,k\le n-1}=(n-1)!\sum_{k=0}^{n-1}\frac{x^k}{\binom{n-1}k}.$$ The idea here is slight modification of my way to establish Theorem 1.1 in my preprint Arithmetic properties of some permanents available from http://arxiv.org/abs/2108.07723.

I admit that the identities $(1)$ and $(4)$ remain open.

Related Question