7
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ Are you assuming the permutations are chosen randomly and independently from $S_n$ with equal probabilities? $\endgroup$ Sep 21, 2018 at 0:38
  • $\begingroup$ 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. $\endgroup$
    – Turbo
    Sep 21, 2018 at 0:40
  • $\begingroup$ @RobertIsrael I guess that means "yes". $\endgroup$
    – Igor Rivin
    Sep 21, 2018 at 1:49
  • $\begingroup$ 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. $\endgroup$
    – MTyson
    Sep 21, 2018 at 2:18

3 Answers 3

5
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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$. $\endgroup$ Sep 21, 2018 at 2:57
  • $\begingroup$ @GjergjiZaimi What exactly is the exponential formula? $\endgroup$
    – Turbo
    Sep 22, 2018 at 9:39
  • $\begingroup$ @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. $\endgroup$ Sep 22, 2018 at 17:34
  • $\begingroup$ 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. $\endgroup$ Sep 22, 2018 at 17:36
  • 1
    $\begingroup$ @Freeman. I expanded the answer to contain the generating functions in all cases and how they are derived. Hope this helps. $\endgroup$ Sep 22, 2018 at 23:19
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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