Transpositions generate the finitary symmetric group
This article states and proves a fact about a particular group, or kind of group, (i.e., finitary symmetric group) having a particular generating set (or kind of generating set), i.e., where the generators are elements of the type/form: transposition
View other facts about generating sets for particular groups
Statement
For a finite set
The Symmetric group (?) on a finite set is generated by the Transposition (?)s in it. A transposition is a permutation that interchanges two elements and leaves all the others fixed; in other words, it is a cycle of length two.
For an infinite set
The Finitary symmetric group (?) on any set is generated by the transpositions in it. A transposition is a permutation that interchanges two elements and leaves all the others fixed; in other words, it is a cycle of length two.
Applications
This result proves, for instance, that the symmetric group on a finite set, and more generally, any finitary symmetric group, is a group generated by involutions -- it is generated by elements of order two.
Related facts
More facts about transpositions as generators for the symmetric group
- Transpositions of adjacent elements generate the symmetric group on a finite set
- All transpositions involving one element generate the finitary symmetric group
Related facts about generating sets for the symmetric group and alternating group
- Symmetric group on a finite set is 2-generated
- Dixon's theorem
- 3-cycles generate the alternating group
Related facts about generating sets for permutation groups
For the symmetric group on a set of size , the transpositions form a generating set of size
, the transpositions of adjacent elements form a generating set of size
, and the transpositions involving one particular element also form a generating set of size
. Similar results hold for arbitrary subgroups of the symmetric group:
- Sims filter gives a procedure for starting with any generating set of a subgroup of the symmetric group on
elements, and producing a generating set of size at most
. A generating set obtained by this filter has some special properties, and such a generating set is termed a Sims-reduced generating set.
- Jerrum's filter gives a procedure for starting with any generating set of a subgroup of the symmetric group on
elements, and producing a generating set of size at most
. A generating set obtained by this filter has some special properties, and such a generating set is termed a Jerrum-reduced generating set.
In terms of IAPS theory
In terms of IAPS theory, this translates to saying that the transposition on a two-element set forms a one-element permutatively generating set for the permutation IAPS.
Proof for a finite set
Some of the proofs given here show some of the additional facts mentioned in the Related facts section: that a permutation that moves elements can be expressed as a product of at most
transpositions. Other proofs show that, in fact, we don't even need all the transpositions: we only need all the transpositions involving one specific element. Other proofs show that if we order the elements of a finite set, we do not need all the transpositions: we only need transpositions between adjacent elements in the ordering.
Proof using the cycle decomposition
This proof uses the cycle decomposition theorem for permutations. This theorem states that every finitary permutation of a group can be expressed as a product of disjoint cycles. Thus, it suffices to show that every cycle can be expressed as a product of transpositions.
Consider a cycle:
.
We claim that (using the left action convention) this cycle is a product of transpositions:
.
Let's prove this. For ,
first occurs in the transposition
, where it gets sent to
. Next is the transposition
, sending it to
.
does not get moved any further. Thus,
gets sent to
.
For , the first transposition sends it to
, and
does not get moved any further.
For , the last transposition sends it to
.
Thus, the product of these transpositions has the same effect on every element as the prescribed -cycle.
Note that since we need transpositions for a
-cycle, it is clear that for a permutation that moves
elements, we need at most
transpositions.
Proof using sorting algorithms
This proof works for the symmetric group on finite sets. The result for the finitary symmetric group on an infinite set follows from the fact that any finitary permutation is contained in the symmetric group on a finite subset.
The idea behind these proofs is to show that given any permutation, we can perform multiply it by transpositions, one after the other, to arrive at the identity permutations. Doing the inverses of these operations would thus express the given permutation as the product of transpositions.
These proofs simplify further using induction. Here, we assume that every permutation on a set of size is a product of transpositions, and we show that a permutation on a set of size
can be expressed as a product of transposition, times a permutation on a set of size
.
- The selection sort proof: Here, given a permutation
on a set
, we consider a transposition
. The product permutation
sends
to itself, and is thus a permutation on the subset
. Induction now applies. Note that this algorithm shows that every permutation moving
elements can be expressed as a product of at most
transpositions.
- The bubble sort proof: Here, given a permutation
on a set
, we do the following: traversing the list, right-multiply by the transposition
if the index of
is greater than
. This is effectively the same as left-multiplying by
, or equivalently, it is the same as swapping the values in positions
and
. At the end of one phase of this,
(the largest entry bubbles to the bottom) so
is a permutation on
elements. Note that this proof uses a smaller generating set (the transpositions of adjacent elements only) but may require longer products.