Transitive subgroups of the symmetric group

Let S_n denote the symmetric group on A=\{1,2,\ldots n\}. A subgroup G\subseteq S_n is said to be a transitive subgroup if the natural action on the set A is transitive.

Q : Find all isomorphism classes of transitive subgroups of size n of S_n.

Answer :

Let us try to find one subgroup .., well, \mathbb{Z}_n generated by the n-cycle (1 2 \ldots n). Clearly it is transitive, and in fact, more is true, namely, the stabilizer of any element is the trivial permutation.

Can we think of more ?

Let us look at S_{2n} and look at p=(1, 2, \ldots n)(n+1, \ldots, 2n) [this is the cycle notation of permutations]. p has order n. Now if we can find a q which somehow can make 1 go to n+1, then the subgroup generated by p,q would be transitive.

In fact, we can find q such that qp=pq or rather qpq^{-1}=p. Just look at q=(1, n+1)(2 , n+2)(3 , n+3)\ldots (n , 2n). Then qpq^{-1} = (1, 2 ,\ldots, n)(n+1, \ldots, 2n)=p

The subgroup generated by p,q is isomorphic to \mathbb{Z}_n\times \mathbb{Z}_2, so we see that \mathbb{Z}_{n}\times \mathbb{Z}_{2} is also a transitive subgroup of size 2n in S_{2n}

In fact, more is true !

Claim : Let G be ANY subgroup of size n. Then it can be embedded as a transitive subgroup of S_n.

Proof : Let G=\{g_1,\ldots,g_n\} and let S_n be the symmetric group on a set of size n, which we can assume to be G ! We have the following (usual) embedding of G into S_n got by the action of G on itself by a modified left translation, namely

f:G\to S_n which sends g\to [g_i\to g^{-1}g_i], where S_n is thought of as set bijections of G and itself.

  1. The map [g_i\to g^{-1}g_i] is a set bijection because g^{-1}g_i=g^{-1}g_j\iff g_i=g_j
  2. f is a group homomorphism – easy check. [This is why we need g_i\to g^{-1}g_i instead of g_i\to gg_i
  3. f is a 1-1 function (or an embedding) because the map [g_i\to g^{-1}g_i] is identity if and only if g^{-1}g_i=g_i\forall g_i which happens if and only if g=e

So G can be identified as a subgroup of S_n via f. Now we check that it is a transitive subgroup !

Any g_i can be moved to g_j by the element a=g_ig_j^{-1} because a\star g_i = a^{-1}g_i = g_jg_i^{-1}g_i=g_j.

Infact, what is the stabilizer of any g_i under this action of G ? It is the identity ! So this action of G  is in fact regular (or transtive+free = simply transitive, namely given g_i and g_j, there is a unique element in G which takes one to the other)


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s