# How many automorphisms of $S_n$ take transpositions into transpositions?

I need to show that an automorphism of $S_n$ which takes transpositions to transpositions is an inner automorphism.

I thought it could be done by showing that such automorphisms form a subgroups $H\le Aut(S_n)$, that $Inn(S_n)\subset H$ and that they have the same number of elements. The number of inner automorphisms is $n!$ because $S_n$ has a trivial center (at least when it is not abelian) and therefore is isomorphic to $Inn(S_n)$. However I have no idea how I could count the number of elements in $H$.

Is there a way to do it, or should I change the approach altogether?

Thank you.

• I am not sure if it helps to think of the fact that $n-1$ transpositions ....$(12), (13), (14), (1 n)$ generate $S_n$. – user21436 Apr 21 '12 at 6:12
• One way of showing this is to recall the result that $n=6$ is the only case, when $S_n$ has non-inner automorphisms, and in that case the non-inner automorphisms map transpositions to products of three disjoint transpositions. Admittedly this has the air of swatting flies with cannonballs. – Jyrki Lahtonen Apr 21 '12 at 6:16
• @KannappanSampath, I think that your suggestion can be made to work. It should be possible to show that the images of the transpositions in your list all move the same element, and go from there. – Jyrki Lahtonen Apr 21 '12 at 6:25
• @KannappanSampath I got nowhere thinking about this yesterday. The problem I have is that there is more than one set of generators for $S_n$ and it is not clear that the set of generators you gave is mapped to some other set of generators. – Artem Apr 21 '12 at 6:31
• @KannappanSampath, I'm not sure. I would think that there are other sets of $(n-1)$ generating transpositions. Probably we need to use some extra information such as: no two of the $(n-1)$ transpositions commute. – Jyrki Lahtonen Apr 21 '12 at 6:41

Kannappan Sampath's suggestion can be completed as follows.

Let $f$ be an automorphism of $S_n$ with the property that it maps all transpositions to transpositions. So $f(1k)=(a_kb_k)$ for all $k=2,3,\ldots,n$, where $a_k\neq b_k$ are elements of the set $\{1,2,\ldots,n\}$. As the permutations $(12)$ and $(13)$ don't commute, their images $(a_2b_2)$ and $(a_3b_3)$ don't commute either. This means that the intersection $\{a_3,b_3\}\cap\{a_2,b_2\}$ is a singleton. Without loss of generality we can assume that $a_2=a_3=a$.

Next I claim that for all $k>3$ we also have $a\in\{a_k,b_k\}$. Assume contrariwise that for some $k>3$ we have $a_k\neq a\neq b_k$. Because $(1k)$ does not commute with $(12)$, we must have $b_2\in\{a_k,b_k\}$. Similarly, because $(1k)$ does not commute with $(13)$ either, we must also have $b_3\in\{a_k,b_k\}$, so $(a_kb_k)=(b_2b_3)$. But this is a contradiction, because then $$f(23)=f((13)(12)(13))=(ab_3)(ab_2)(ab_3)=(b_2b_3)=f(1k)$$ violating the fact that $f$ is injective.

Thus all the transpositions $(a_kb_k)$ move the element $a$, and w.l.o.g. we can assume that $a_k=a$ for all $k$. All the integers $b_k\neq a$, and they must also be distinct, so the mapping $\sigma: 1\mapsto a, k\mapsto b_k$ is in $S_n$. We have shown that $f$ agrees with the inner automorphism $x\mapsto \sigma x\sigma^{-1}$ on all the $(n-1)$ generators $x=(1k),k=2,3,\ldots,n,$ of the group $S_n$, so the claim follows.

I think there is an easier way of looking at this (now edited to get the argument correct - and also simpler, thanks to Jyrki's comment). An inner automorphism of $S_n$ is equivalent to a permutation of the underlying set on which $S_n$ acts. Let's choose our generators to be a permutation $a=(1 2)$ and the n-cycle $b=(1 2 3 ... n)$.

Then we know that the automorphism sends $a$ to another transposition $a'$.

Consider the cycle decomposition of $b'$, the image of $b$. The two objects permuted by $a'$ must be adjacent within the same cycle in $b'$ (else $b'^{-1}a'b'$ will be found to be a transposition moving different objects from $a'$ and will commute with it, and this is not true for $a, b$).

Suppose the objects moved by $a'$ are adjacent in a cycle of length $m<n$ in $b'$. Then $b'^m$ will commute with $a'$ (it will not move the objects moved by $a'$). This is not true for $a, b$, so we must have $m=n$ i.e. $b'$ is an $n$-cycle with the elements moved by $a'$ adjacent. Since this is the same cycle pattern as for $a, b$ there will be a permutation of the underlying objects which does the job, and this is the required inner automorphism.

• +1 A nice idea to use the image of $b$ in finding the inner automorphism, together with using the image of $a$ as a 'marker'. But you lost me at the point, where you claimed that $b'$ must be an $n$-cycle. I don't think that the two stated facts 1) $b'$ moves at least $n-1$ objects, 2) $b'$ has order $n$, allow us to deduce that $b'$ is an $n$-cycle. This leaves open possibilities like $b'=(12)(345)\in S_6$. May be centralizer of $a'$ in $\langle b' \rangle$ will serve as a fix? More likely I missed something simpler :-) – Jyrki Lahtonen Apr 22 '12 at 6:38
• @JyrkiLahtonen: Counterexample confirmed for $S_6$ - and there are others too. I'll think about how to correct that. – Mark Bennet Apr 22 '12 at 8:26
• @JyrkiLahtonen - I'll have a go at redrafting - I think the way of getting to an n-cycle is as follows: examine the cycle decomposition of $b'$,the image of $b$. The two objects moved by the transposition $a'$ must be in the same cycle, and adjacent within it, else conjugating by $b'$ gives a transposition which commutes with $a'$. Suppose this cycle has length $m<n$ then $b'^m$ commutes with $a'$, though $a$ and $b^m$ do not commute. – Mark Bennet Apr 22 '12 at 11:08
• That's a nice way of doing it! As a further point, you no longer need to include a separate argument telling that $b'$ must move at least $(n-1)$ objects. – Jyrki Lahtonen Apr 22 '12 at 11:12
• Probably I'm missing something, but I don't get the argument why the "two objects permuted by $a'$ must be adjacent within the same cycle of $b'$". Wouldn't it be possible that one of those two objects is a fixed point of $b'$? I think in this case, the transposition $b'^{-1}a'b'$ doesn't commute with $a'$. – azimut May 16 '13 at 14:08