1

If two permutations $P_1$ and $P_2$ of $n$ elements have the same parity (i.e. both are even or both are odd) and the same trace of their corresponding permutation matrices (i.e. they leave the same number of elements unchanged), does this mean that there is always a third permutation $P_{12}$ such that $P_{12} P_1 P_{12}^{-1} = P_2$?

This trivially holds for permutations of 2 elements and it is also relatively easy to show that it holds for permutations of 3 elements. Does it hold for arbitrarily large $n$?

If true, is there any known algorithm to find $P_{12}$?

Danijel
  • 1,588

2 Answers2

2

No. Consider $(1)(234)(567)$ and $(1)(23)(4567)$.

ancient mathematician
  • 14,102
  • 2
  • 16
  • 31
2

No. In fact two permutations are equivalent in that sense, (ie conjugate), if and only if they have the same "signature", meaning that the decompositions into disjoint cycles have the same number of cycles of a given length.

So for example in $S_8$ the permutations $P_1=(1,2)(3,4)(5,6,7,8)$ and $P_2=(1,2,3,4)(5,6,7,8)$ are not conjugate, even though they're both even and have "trace" zero (no fixed points). Anything conjugate to $P_2$ must be the product of two disjoint cycles of length four, hence cannot be $P_1$.

Now say $P_1=(a,b)(c,d,e)$ and $P_2=(s,t)(u,v,w)$ are two disjoint-cycle decompositions. Then $P_1$ and $P_2$ are conjugate. $P_{12}$ will be a permutations that maps $a$ to $s$, $b$ to $t$, etc., and maps the fixed points of $P_1$ to the fixed points of $P_2$.

David C. Ullrich
  • 89,985