3
$\begingroup$

Given a permutation matrix, I want to compute the minimum number of pairwise row swaps I need to make so that I end up with the identity.

An example:

$$\begin{pmatrix}0 & 0 & 1 & 0\\1 & 0& 0 & 0\\ 0&0&0 & 1\\0&1&0&0\end{pmatrix}\rightarrow\begin{pmatrix}1 & 0 & 0 & 0\\0 & 0& 1 & 0\\ 0&0&0 & 1\\0&1&0&0\end{pmatrix}\rightarrow\begin{pmatrix}1 & 0 & 0 & 0\\0 & 0& 1 & 0\\ 0&1&0 & 0\\0&0&0&1\end{pmatrix}\rightarrow\begin{pmatrix}1 & 0 & 0 & 0\\0 & 1& 0 & 0\\ 0&0&1 & 0\\0&0&0&1\end{pmatrix}$$

This permutation needed 3 swaps to return to identity. Note that it does not have to be adjacent rows for a swap to be allowed, even though this example only had those.

My reason for wanting to compute this is really because I want to know how many permutations require an even number of swaps, out of all the $n!$ possibilities. I was thinking that if I had a formula I might be able to derive this, or at worst brute force count all permutations for reasonable values of $n$.

Any help would be much appreciated!

Edit: I seem to have stumbled across a much harder (though interesting) problem while trying to show something that seems to be a known thing - that there are exactly $n!/2$ permutations requiring an even number of swaps. While I really appreciate the answer given to my original question (accepted as it does what I asked for), I would really like a proof/explanation of why there are equal amounts of even/odd permutations?

$\endgroup$
  • $\begingroup$ Exactly half of the $n!$ permutation matrices require an even number of swaps. These are the even permutations. $\endgroup$ – Mike Earnest Feb 23 at 18:38
  • $\begingroup$ Your first question amounts to the computation of the number of inversions in your permetation. Please take a look at stackoverflow.com/questions/6523712/… $\endgroup$ – Jean Marie Feb 23 at 20:06
  • 1
    $\begingroup$ @Jean That's not right, the OP is allowing arbitrary transpositions. That's a more difficult number to compute than inversions. Much more difficult than how many require an even number. $\endgroup$ – Matt Samuel Feb 23 at 20:44
  • $\begingroup$ @MikeEarnest Do you have/know a proof for this? It seems very correct (and is I guess), but both on Wikipedia and Wolfram Mathworld it's simply stated as fact. I'll be basing some results on this fact, and I would at the very least like to read a proof before continuing... It might be obvious, but then it should be easy to point out why, right? $\endgroup$ – Bendik Feb 23 at 21:00
  • $\begingroup$ @Matt Samuel : I don't understand but I am ready to accept it : for example in the given matrix, there are 3 inversions and 3 operations are used. Could you give me a counterexample ? $\endgroup$ – Jean Marie Feb 23 at 21:08
3
$\begingroup$

To compute the number of swaps needed to make the identity, compute the number of cycles the permutation has. If the permutation has $k$ cycles, then the required number of swaps is $n-k$.

To see this, examine how swapping affects the cycle structure of a permutation. You can show that if you swap to elements in the same cycle, then that cycle will split into two, while if you swap two elements in different cycles, they will merge into one. Therefore, if you start with $k$ cycles and want to reach the identity which has $n$ cycles, it will takes $n-k$ swaps.

In your example, you permutation was a single cycle $1\to 3\to 2\to 4\to 1$, so the required number of swaps was $4-1=3$.


For example, consider the permutation \begin{matrix} 3&4&5&1&6&2 \end{matrix} This is a single cycle, which in cycle notation is $(1\;\;4\;\;2\;\;6\;\;5\;\;3)$, because $1$ is placed in spot $4$, $4$ is placed in spot $2$, etc. Now, switch any two elements in this permutation, say, $4$ and $6$. The result is now \begin{matrix} 3&6&5&1&4&2 \end{matrix} Now the new cycle notation is $(1\;\;4\;\;5\;\;3)(2\;\;6)$, since $2$ and $6$ are switched, while $1$ is in spot $4$, $4$ is in spot $5$, etc. In other words, one cycle became two. If there were other disjoint cycles in this permutation, they would be unaffected.

Going in reverse, that is starting with the second permutation and switching $4$ and $6$ to get the first, we see two cycles merge into one.

$\endgroup$
  • $\begingroup$ This doesn't make sense. What about a transposition, which only requires $1$ but has a single cycle? $\endgroup$ – Matt Samuel Feb 23 at 21:33
  • $\begingroup$ Are you counting fixed points as trivial cycles? $\endgroup$ – Matt Samuel Feb 23 at 21:34
  • $\begingroup$ @MattSamuel Yes, fixed points are cycles of length $1$. $\endgroup$ – Mike Earnest Feb 23 at 21:34
  • $\begingroup$ Thank you for this, this makes sense. Could you add an explanation for why there are an equal amount of even and odd permutations? Or a link to such a thing? $\endgroup$ – Bendik Feb 23 at 22:54
  • 1
    $\begingroup$ So because any swap from an even perm gives a unique odd perm, and because the same holds for odd perms, the only way for both to be true is if there are an equal amount of even/odd perms in total? Alright, I think I've convinced myself suitably. Thanks! $\endgroup$ – Bendik Feb 23 at 23:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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