   Generators of the symmetric group

### Generators of the symmetric group

Since

(i1 ...ir)=(i1i2)(i2i3) ...(ir-1ir)

each cycle, and hence every element of Sn , can be written as a product of transpositions. Thus Sn 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 := { si:=(i,i+1) | 1 <= i<n }= {(12),(23), ...,(n-1,n) },

consisting of the elementary transpositions si, generates Sn . A further system of generators of Sn is obtained from

(1 ...n)i(12)(1 ...n)-i=(i+1,i+2),1 <= i <= n-2,

so that we have proved

Corollary:
Sn = á(12),(23), ...,(n-1,n) ñ= á(12),(1 ...n) ñ.

 harald.fripertinger "at" uni-graz.at http://www-ang.kfunigraz.ac.at/~fripert/ UNI-Graz Institut für Mathematik UNI-Bayreuth Lehrstuhl II für Mathematik
last changed: January 19, 2005   Generators of the symmetric group