| | | **Generators of the symmetric group** |

### Generators of the symmetric group

Since

*
(i*_{1} ...i_{r})=(i_{1}i_{2})(i_{2}i_{3}) ...(i_{r-1}i_{r})

each cycle, and hence every element of * S*_{n} , can be written as a product
of transpositions. Thus * S*_{n} is generated by its subset of transpositions
(if this is empty, then *n <= 1*, and both *S*_{ 1}=
S_{ 0}= {1 } are generated by the empty set
* Æ*). But, except for the case when *n=2*, we do not need every
transposition in order to generate the symmetric group, since, for
*1 <= j<k<n*, we derive from the conjugation formula that

*(j,k+1)=(k,k+1)(j,k)(k,k+1).
*

Thus the transposition *(j,k+1)* can be obtained from *(j,k)* by
conjugation with the transposition *(k,k+1)* of adjacent points. Therefore
the subset

* S*_{ n}
:= { s_{i}:=(i,i+1) | 1 <= i<n }= {(12),(23), ...,(n-1,n) },

consisting of the *elementary transpositions*
* s*_{i}, generates
* S*_{n} . A further system of generators of * S*_{n} is obtained from

*
(1 ...n)*^{i}(12)(1 ...n)^{-i}=(i+1,i+2),1 <= i <= n-2,

so that we have proved

**Corollary: **
*
** S*_{n} = á(12),(23), ...,(n-1,n) ñ= á(12),(1 ...n) ñ.

last changed: January 19, 2005

| | | **Generators of the symmetric group** |