| | | Generators of the symmetric group |
(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) ñ.
| | | Generators of the symmetric group |