Distribution of sum of two permutation matrices

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?

• Are you assuming the permutations are chosen randomly and independently from $S_n$ with equal probabilities? – Robert Israel Sep 21 at 0:38
• Take $n$ and run the statistics for all possible pairs of permutations. Change $n$ and repeat. How does the histogram change as $n$ increases? That is the problem. – Freeman. Sep 21 at 0:40
• @RobertIsrael I guess that means "yes". – Igor Rivin Sep 21 at 1:49
• Factoring the determinant reduces problem 1 to the distributions of $\det(\alpha)$ and $\det(\alpha^{-1}\beta\pm 1)$. When $\pi:=\alpha^{-1}\beta$ has cycle type $1^{e_1}\cdots n^{e_n}$, it has characteristic polynomial $(x-1)^{e_1}\cdots(x^n-1)^{e_n}$. Therefore $\det(\pi\pm 1)=(-1)^n((\mp1)-1)^{e_1}\cdots((\mp 1)^n-1)^{e_n}$. In particular for differences of permutations it is always $0$. For sums of permutations it is $\pm 2^{e_1+e_3+\cdots}$ assuming it has no even cycles and is $0$ otherwise. – MTyson Sep 21 at 2:18

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

• Accordingly, $f(2n+1,k)=0$ and $f(2n,k)=\frac1{n!}e_{n-k}(1,2,\dots,n-1)$ where $e_j$ is the elementary symmetric function of $1,2,\dots,n-1$. – T. Amdeberhan Sep 21 at 2:57
• @GjergjiZaimi What exactly is the exponential formula? – Freeman. Sep 22 at 9:39
• @Freeman. It is a fundamental theorem in combinatorics. It roughly says that if $F(x)$ is the exponential generating function of some structures, then $e^F$ is the exponential generating function of disjoint unions of such structures. For the example above, I can find the exponential generating function of even cycles to be $F(x)=\frac{x^2}{2}+\frac{x^4}{4}+\cdots$ since there are exactly $(2n-1)!$ cycles of size $2n$. Therefore $e^{tF}$ is the exponential generating function of disjoint unions of even cycles, together with a statistic $t$ that keeps track of the number of cycles. – Gjergji Zaimi Sep 22 at 17:34
• The general technique is outlined here en.wikipedia.org/wiki/Symbolic_method_(combinatorics) A great place to learn about it is Flajolet and Sedgewick's book Analytic Combinatorics. – Gjergji Zaimi Sep 22 at 17:36
• @Freeman. I expanded the answer to contain the generating functions in all cases and how they are derived. Hope this helps. – Gjergji Zaimi Sep 22 at 23:19

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.

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).

• I sensed that for difference but the distribution seems subtle. – Freeman. Sep 21 at 1:59
• It also seems dyadicity is involved. – Freeman. Sep 21 at 2:01
• @Freeman dyadicity? – Igor Rivin Sep 21 at 2:02
• Powers of $2$ because $1+1=2$. – Freeman. Sep 21 at 2:03