Distribution of sum of two permutation matrices

Question

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?

Answer 1

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

Answer 2

If $A$ is the matrix for a permutation that is a single cycle of size $m$, then the eigenvalues of $A$ are the $m$'th roots of unity, and $\det(I+A)$ is the product of $1+\omega$ over the $m$'th roots of unity, which is $0$ if $m$ is even and $2$ if $m$ is odd. Thus for a permutation that is a product of $r$ disjoint cycles, $\det(I+A) = 0$ if any of the cycles is odd, $2^r$ if they are all even.

For two permutation matrices $A$ and $B$ corresponding to permutations $\sigma$ and $\pi$, we have $\det(A+B) = \det(A) \det(I+A^{-1} B) = 0$ if $\sigma^{-1} \pi$ has any odd cycles, $2^r$ if $\sigma^{-1}\pi$ has only $r$ even cycles and $\sigma$ is even, $-2^r$ if $\sigma^{-1}\pi$ has only $r$ even cycles and $\sigma$ is odd.

Answer 3

Well, not an answer, but with probability $2/e$ the two permutations map some $i$ to the (same) $j,$ which means that both the determinant and the permanent of the difference is $0.$ Also with probability $2/e$ (not independent of the previous) $\sigma_1(i) = j, \sigma_2(j) = i,$ so again, both determinant and permanent are zero. So, the distributions will be highly atomic at $0,$ not sure about the rest of the distribution. In the sum case, in the second case ($\sigma_2^{-1} \sigma_1$ has a fixed point), the determinant is zero).