Symmetric group on a finite set is 2-generated
From Groupprops
Contents
Statement
The Symmetric group (?) on a finite set is a 2-generated group (?): it can be generated by two elements.
Note that when the finite set has 3 or more elements (so the degree is 3 or more), the symmetric group is not cyclic, so we obtain that the Minimum size of generating set (?) is precisely 2.
Related facts
Stronger facts
- Dixon's theorem: This states that two randomly picked elements have a high chance of generating the whole symmetric group.
Also refer presentation theory of symmetric groups to learn about good choices of presentation for symmetric groups.
Facts used
Proof
A transposition and a cycle
Consider the set . We show that the symmetric group on this set is generated by the permutations:
and
.
Proof: Observe that, for :
Thus, all transpositions of adjacent elements are in the subgroup generated by these two permutations. Using fact (1), we see that these two permutations generate the whole group.