3
$\begingroup$

I was curious if anyone knew of any proofs or knew of how one might go about proving problems involving restoring permutations. An example of the type of proof I am interested in is:

Prove that any $\sigma \in S_4$ can be restored to the identity permutation, $\varepsilon$, in at most 4 moves, where a move is defined as switching two adjacent elements of $\sigma$.

I have a very basic knowledge of permutations, just what I have read from an abstract algebra book, basically consisting of cycle notation and transpositions and the like. So I know that the worst case scenario, the only case requiring 4 moves, is $\sigma = (3,4,1,2)$. I mean I know that you could do a proof by exhaustion for this example, but if you were dealing with a larger set that would not be a fun undertaking. So what I was wondering is the general method of tackling a proof like this.

I know that you could define each move as a transposition, $(1 2), (2 3), (3 4), (4 1)$, but beyond that I am just lost. Would this require some research into groups on my part?

Thanks!

$\endgroup$
  • $\begingroup$ If you are moving adjacent elements, doesn't $(4321)$ take six moves? Each move only moves one element one space to the right, $4$ needs three moves and $3$ takes one. But we have to move $3$ to the left of $4$, then compensate for the left move with another right one. That makes $5$, and flipping $1,2$ adds a sixth. Then to show we can do it in six, $(4321), (3421),(3241),(3214),(2314),(2134),(1234)$ $\endgroup$ – Ross Millikan Nov 12 '13 at 0:01
  • $\begingroup$ No that would take 2 moves. First move would be $(41)$ thus leaving you with $(1,3,2,4)$. Next move would be $(2,3)$. Thus arriving at $(1,2,3,4)$. $\endgroup$ – Ebearr Nov 12 '13 at 1:31
  • $\begingroup$ I did't think of going around the end $\endgroup$ – Ross Millikan Nov 12 '13 at 2:50
0
$\begingroup$

Any permutation $\sigma \in S_1$ is $0$ moves away from $\rm id$. I.e. it requires multiplication by at most $0$ of $(1,2), (2,3), (3,4), (4,1)$. Now if $\sigma \in S_2$ there's at most $1$ needed. If $\sigma \in S_3$ we could have $\sigma = (1324): 1234 \to 3421$ which requires at least $3$ of those moves. Prove that. Now let it be true that if $\sigma \in S_{n-1}$ then it takes $n-1$ of those moves to restore $\sigma$ back to $\rm id$. Then notice that for any permutation result $\tau_1 \tau_2\tau_3 \dots\tau_{n-1}$ it also takes at most $n-1$ permutations to restore it back to that. Prove that.

Then let the result of $\sigma$ be $\sigma_1 \sigma_2 \dots \sigma_n$. Then it takes at most $n-1$ permutations to restore $\sigma_2 \dots \sigma_n$ back to a sequence that's ordered except where $\sigma(1)$ is supposed to be, let there be a $1$.

Provide the last swap needed to restore to $\rm id$.

Do you catch my drift?

$\endgroup$
  • $\begingroup$ The only problem is that it actually takes $k^2$ moves where $n = 2k$. So for $S_n$ if $n = 4$ then $k = 2$ thus at most 4 moves are required. If you look at $n = 6$ then at most 9 moves are required. I would like to prove this for any $n$, but I thought it might be best to start with a specified $n$ in order to get the hang of the proof and then try to apply it to any $n$. I chose $n = 4$ because I thought it was easy. Also, I am only concerned with cases where $n$ is even. $\endgroup$ – Ebearr Nov 11 '13 at 21:40

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.