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?
Best Answer
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.