# Relabelling a permutation

I'm trying to understand the proof of lemma 3.2 of this article by Keith Conrad on proofs of the simplicity of $A_n$. There is a step I don't follow.

When he says "Relabelling, we may write $\sigma=(1 2 \dots r) \pi$", I don't see why we could do that. Relabelling what?

As I tried to understand the statement, I thought of this: if $(i_1 \dots i_r)$ is a cycle appearing in $\sigma$, then we can conjugate $\sigma$ to $\sigma'=(1 \dots r) \pi$. If we show that $\sigma'$ coincides with $\sigma$ at some index, then we're fine. But why would it coincide, and where?

-

Two explanations:

Informal one. You are thinking of the elements of $A_n$ as acting on the set $\{x_1,x_2,\ldots,x_n\}$, by letting $\sigma$ map $x_i$ to $x_{\sigma(i)}$.

So say that $\sigma$ maps $x_3$ to $x_5$, and $x_5$ to $x_2$, and $x_2$ to $x_3$. Stick new labels on your elements, so that what you used to call "$x_3$" is now called $x_{1_{\mathrm{new}}}$, what you used to call $x_5$ is now called $x_{2_{\mathrm{new}}}$, and what you used to call $x_2$ is now called $x_{3_{\mathrm{new}}}$. Of course, you'll also need a new identity for $x_1$, say $x_{5_{\mathrm{new}}}$, since $5$ is no longer being used; and keep the other elements with their old names, so that $x_{i_{\mathrm{new}}} = x_i$ if $i\notin\{1,2,3,5\}$. Then $\sigma$ now acts on $\{x_{1_{\mathrm{new}}},x_{2_{\mathrm{new}}},\ldots,x_{n_{\mathrm{new}}}\}$ by looking at their "old" identities and acting as before.

But now $\sigma$ maps $x_{1_{\mathrm{new}}}\mapsto x_{2_{\mathrm{new}}}\mapsto x_{3_{\mathrm{new}}}\mapsto x_{1_{\mathrm{new}}}$, so if we write its cycle decomposition in terms of the "new" labels, we have that $$\sigma = (1_{\mathrm{new}},2_{\mathrm{new}},3_{\mathrm{new}})\pi$$ for some $\pi$.

Formal one. Suppose the longest cycle of $\sigma$ is $(i_1,i_2,\ldots,i_r)$. Consider a permutation $\tau\in S_n$ with $1\mapsto i_1$, $2\mapsto i_2,\ldots,r\mapsto i_r$, and which acts in some (unspecified but irrelevant) way on the remaining elements of $\{1,\ldots,n\}$. Then consider the automorphism of $S_n$ given by conjugation by $\tau$, $\psi\mapsto \tau\psi\tau^{-1}$. You've probably seen already that if $\psi$ sends $k$ to $\ell$, then $\tau\psi\tau^{-1}$ sends $\tau(k)$ to $\tau(\ell)$. So we can look at $\tau A_n\tau^{-1}$ and $\tau\sigma\tau^{-1}$ instead of $A_n$ and $\sigma$ (they are isomorphic copies, after all, so we can just "translate back" to $A_n$ by using the inverse automorphism when needed).

But in $\tau A_n\tau^{-1}$, the longest cycle of $\tau\sigma\tau^{-1}$ is just $(\tau(i_1),\tau(i_2),\ldots,\tau(i_r)) = (1,2,\ldots,r)$. So, by switching to this isomorphic copy of $A_n$, we may assume that the longest cycle of $\sigma$ is in fact $(1,2,\ldots,r)$.

-
Outstanding, as usual. What an excellent answer, thank you, Arturo, your contributions to this site are of the utmost quality! Now I'm fully convinced. I had the informal idea as to what is 'relabelling', but I wasn't sure it was 'legal' to do that, so I started thinking about conjugation, but not in the correct way, which is your formal explanation and which completely satisfies my skepticism. – Bruno Stonek Feb 26 '11 at 21:50