symmetric group is generated by adjacent transpositions
Theorem 1.
The symmetric group on is generated by the permutations
Proof.
We proceed by induction on . If , the theorem
is trivially true
because the the group only consists of the identity
and a single transposition
.
Suppose, then, that we know permutations of numbers are generated
by transpositions of successive numbers. Let be a permutation of
. If , then the restriction of
to is a permutation of numbers, hence,
by hypothesis
, it can be expressed as a product
of transpositions.
Suppose that, in addition, with . Consider the following product of transpositions:
It is easy to see that acting upon with this product of transpositions produces . Therefore, acting upon with the permutation
produces . Hence, the restriction of this permutation to
is a permutation of numbers, so,
by hypothesis, it can be expressed as a product of transpositions.
Since a transposition is its own inverse, it follows that
may also be expressed as a product of transpositions.
∎
Title | symmetric group is generated by adjacent transpositions |
---|---|
Canonical name | SymmetricGroupIsGeneratedByAdjacentTranspositions |
Date of creation | 2013-03-22 16:49:02 |
Last modified on | 2013-03-22 16:49:02 |
Owner | rspuzio (6075) |
Last modified by | rspuzio (6075) |
Numerical id | 11 |
Author | rspuzio (6075) |
Entry type | Theorem |
Classification | msc 20B30 |