3

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!

Ebearr
  • 866
  • 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)$ – Ross Millikan Nov 12 '13 at 00:01
  • 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)$. – Ebearr Nov 12 '13 at 01:31
  • I did't think of going around the end – Ross Millikan Nov 12 '13 at 02:50

1 Answers1

0

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?

Daniel Donnelly
  • 21,342
  • 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. – Ebearr Nov 11 '13 at 21:40