Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 8 down vote accepted

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)$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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