It’s a fairly well-known fact that the symmetric group can be generated by the transposition and the –cycle . One way to prove it is as follows.

- Show that the transpositions for generate .
- Show that any transposition can be obtained from and .

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

**Lemma. ** for any and .

(1) is easily proven by the observation that any permutation of 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 can be obtained from upon repeated conjugation by . Now, since , WLOG let . Using the lemma, conjugating by gives , conjugating by gives , etc. In this way we can eventually get . So we are done by (1).

This argument shows that can in fact be generated by and for any .

Now let’s consider an arbitrary transposition and an -cycle in . By relabeling , we can assume that and for . Note that where , so WLOG . Then for each . In particular, taking gives . Then . Repeating this procedure produces for . Now is a complete set of residues mod if and only if , i.e., . So we’ve shown that

**Theorem.** Let be a transposition and be an -cycle in . Then and generate if and only if .

In particular, and generate if and only if .

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

### Like this:

Like Loading...

*Related*

Filed under Algebra

Tagged as group, permutation

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