Generating the symmetric group

It’s a fairly well-known fact that the symmetric group S_n can be generated by the transposition (1\ 2) and the ncycle (1\ \cdots\ n). One way to prove it is as follows.

  1. Show that the transpositions (a\ b) for a,b\in\{1,\dots,n\} generate S_n.
  2. Show that any transposition (a\ b) can be obtained from (1\ 2) and (1\ \cdots\ n).

We also need the following key lemma the proof of which is routine.

Lemma. \rho (a\ b)\rho^{-1}=(\rho(a)\ \rho(b)) for any \rho\in S_n and a,b\in\{1,\dots,n\}.

(1) is easily proven by the observation that any permutation of 1,\dots,n can be obtained by swapping two elements at a time. (2) is a bit more interesting.

We first use the lemma to observe that any transposition of the form (a\ a+1) can be obtained from (1\ 2) upon repeated conjugation by (1\ \cdots\ n). Now, since (a\ b)=(b\ a), WLOG let a<b. Using the lemma, conjugating (a\ a+1) by (a+1\ a+2) gives (a\ a+2), conjugating (a\ a+2) by (a+2\ a+3) gives (a\ a+3), etc. In this way we can eventually get (a\ b). So we are done by (1).

This argument shows that S_n can in fact be generated by (a\ a+1) and (1\ \cdots\ n) for any a.

Now let’s consider an arbitrary transposition \tau and an n-cycle \sigma in S_n. By relabeling 1,\dots,n, we can assume that \sigma=(1\ \cdots\ n) and \tau=(a\ b) for a<b. Note that \sigma^{-a+1}\tau\sigma^{a-1}=(1\ c) where c=b-a+1, so WLOG \tau=(1\ c). Then \sigma^k\tau\sigma^{-k}=(1+k\ c+k) for each k. In particular, taking k=c-1 gives \sigma^{c-1}\tau\sigma^{-c+1}=(c\ 2c-1)=:\rho. Then \rho\tau\rho^{-1}=(1\ 2c-1). Repeating this procedure produces (1\ c+k(c-1)) for k=0,1,2,\dots. Now \{c+k(c-1):k=0,1,\dots,n-1\} is a complete set of residues mod n if and only if \gcd(c-1,n)=1, i.e., \gcd(b-a,n)=1. So we’ve shown that

Theorem. Let \tau=(a\ b) be a transposition and \sigma=(c_1\ \cdots\ c_n) be an n-cycle in S_n. Then \tau and \sigma generate S_n if and only if \gcd(c_b-c_a,n)=1.

In particular, (a\ b) and (1\ \cdots\ n) generate S_n if and only if \gcd(b-a,n)=1.

Corollary. S_p is generated by any transposition and any p-cycle for p prime.


1 Comment

Filed under Algebra

One response to “Generating the symmetric group

  1. Pingback: A nice group theory result | Samin Riasat's Blog

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