Determinant and permanent of sum of two $n\times n$ permutation matrices can be arbitrarily different.


1. What is the distribution of determinant of sum and difference of two $n\times n$ permutation matrices?
2. What is the distribution of permanent of sum and difference of two $n\times n$ permutation matrices?


How much do the distributions differ?



Distribution of sum of two permutation matrices
I will abuse notation by identifying a permutation and the matrix it represents. We can denote by $E(\sigma), O(\sigma)$ the number of even and odd cycles that $\sigma$ decomposes into. Given two permutations $\sigma\_1,\sigma\_2$ we can compute the following:
$$\det(\sigma\_1+\sigma\_2)=\left\{
 \begin{array}{ll}
 (-1)^{E(\sigma\_1)}2^{O(\sigma\_1\sigma\_2^{-1})} & \mbox{if } E(\sigma\_1\sigma\_2^{-1})=0 \\
 0 & \mbox{otherwise }
 \end{array}
\right. $$
$$\operatorname{per}(\sigma\_1+\sigma\_2)=2^{E(\sigma\_1\sigma\_2^{-1})+O(\sigma\_1\sigma\_2^{-1})}$$
$$\operatorname{per}(\sigma\_1-\sigma\_2)=\left\{
 \begin{array}{ll}
 2^{E(\sigma\_1\sigma\_2^{-1})} & \mbox{if } O(\sigma\_1\sigma\_2^{-1})=0 \\
 0 & \mbox{otherwise }
 \end{array}
\right. $$
and trivially $\det(\sigma\_1-\sigma\_2)=0$ since the vector of all 1's is always in the kernel of $\sigma\_1-\sigma\_2$. These calculations follow from noticing that the matrices decompose as direct sums of smaller matrices corresponding to each cycle of $\sigma\_1\sigma\_2^{-1}$. [Distributions of cycle statistics](https://en.wikipedia.org/wiki/Random_permutation_statistics) like these are easy to obtain with the exponential formula. 




---


From here we can count the number of occurrences of each value. Let's start with $\det(\sigma\_1+\sigma\_2)$. The exponential generating function for odd cycles (or cyclic permutatons of odd size) on $\{1,2,\dots,n\}$ is $x+\frac{x^3}{3}+\cdots=\frac{1}{2}\left(\log(1+x)-\log(1-x)\right)$. This is because there are $(n-1)!$ odd cycles when $n$ is odd, and $0$ otherwise. By the [exponential formula](https://en.wikipedia.org/wiki/Exponential_formula), the generating function of permutations that consist of only odd cycles, together with a statistic $t$ that keeps track of the number of cycles, is
$$e^{\frac{t}{2}\left(\log(1+x)-\log(1-x)\right)}=\left(\frac{1+x}{1-x}\right)^{\frac{t}{2}}$$
By substituting $t=2s$ we get $\left(\frac{1+x}{1-x}\right)^{s}$. The coefficient $a\_{k,n}$ of the monomial $s^kx^n$ is given exactly by $\frac{1}{n!}$ times the number of permutations on $n$ letters that decompose into $k$ odd cycles and no even cycles, times a factor of $2^k$. Therefore the number of permutation pairs $(\sigma\_1,\sigma\_2)$ for which $\det(\sigma\_1+\sigma\_2)=-2^k$ is the same as the number of permutation pairs for which $\det(\sigma\_1+\sigma\_2)=2^k$ and is given by $\frac{(n!)^2a\_{k,n}}{2}$. Here we used the fact that $(-1)^{E(\sigma)}$ is the sign of $\sigma$, and the number of permutations with sign $-1$ is the same as those with sign $+1$.




---


For $\operatorname{per}(\sigma\_1+\sigma\_2)$ we are looking at $2^{\text{number of cycles}}$ over all permutations. So we start with the generating function of cycles which is $x+\frac{x^2}{2}+\cdots=-\log(1-x)$. So the exponential generating function 
$$e^{t(-\log(1-x))}=\frac{1}{(1-x)^t}$$
has as coefficient of $t^kx^n$ the number of permutations on $n$ letters with precisely $k$ cycles, divided by $n!$. Substituting $t=2s$ we get $\frac{1}{(1-x)^{2s}}$, and we denote by $b\_{k,n}$ the coefficient of $s^kx^n$. This coefficient is equal to $\frac{1}{n!}$ times the number of permutations on $n$ letters with precisely $k$ cycles, times $2^k$. Therefore the number of permutation pairs $(\sigma\_1,\sigma\_2)$ with $\operatorname{per}(\sigma\_1+\sigma\_2)=2^k$ is exactly $(n!)^2b\_{k,n}$.




---


Finally for $\operatorname{per}(\sigma\_1-\sigma\_2)$ we want to look at permutations with only even cycles. The exponential generating function of even cycles is given by $\frac{x^2}{2}+\frac{x^4}{4}+\cdots=-\frac{1}{2}\log(1-x^2)$. Similarly to above the generating function
$$e^{2s\left(-\frac{1}{2}\log(1-x^2)\right)}=\frac{1}{(1-x^2)^s}$$
has coefficients $c\_{k,n}$ for monomials $s^kx^n$ which are equal to $\frac{1}{n!}$ times the number of permutations on $n$ letters which decompose into exactly $k$ even cycles, times $2^k$. So the number of permutation pairs $(\sigma\_1,\sigma\_2)$ with $\operatorname{per}(\sigma\_1-\sigma\_2)=2^k$ is exactly $(n!)^2c\_{k,n}$.


