Generators of the symmetric group

Generators of the symmetric group

Since

  (i₁ ...i_r)=(i₁i₂)(i₂i₃) ...(i_r-1i_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 ₁= S ₀= {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)ⁱ(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) ñ.

Generators of the symmetric group