every permutation has a cycle decomposition
In this entry, we shall show that every permutation of a
finite set
can be factored into a product
of disjoint cycles.
To accomplish this, we shall proceed in two steps.
We begin by showing that, if is a non-trivial permutation of a set , then there exists a cycle where
and a permutation of such that and .
Since the permutation is not trivial, there exists such that . Define a sequence inductively as follows:
Note that we cannot have for any .
This follows from a simple induction argument. By
definition . Suppose
that but that .
By definition, . Since is a
permutation, and
imply that , so , which
contradicts a hypothesis
. Hence, if ,
then so, by induction,
for all .
By the pigeonhole principle, there must exist and
such that but . Let be the
least integer such that but
when . Set .
Then we have that is a cycle.
Since is a permutation and
is closed under , it follows that
is also closed under . Define as follows:
Then it is easily verified that .
We are now in a position to finish the proof that
every permutation can be decomposed into cycles.
Trivially, a permutation of a set with one element
can be decomposed into cycles because the only
permutation of a set with one element is the
identity permutation, which requires no cycles
to decompose. Next, suppose that any set with less
than elements can be decomposed into cycles.
Let be a permutation on a set with elements.
Then, by what we have shown, can be written as
the product of a cycle and a permutation which
fixes the elements of the cycle. The restriction
of
to those elements such that
is a permutation on less than elements and
hence, by our supposition, can be decomposed into
cycles. Thus, can also be decomposed into
cycles. By induction, we conclude that any
permutation of a finite set can be decomposed into cycles.
Title | every permutation has a cycle decomposition |
---|---|
Canonical name | EveryPermutationHasACycleDecomposition |
Date of creation | 2013-03-22 16:48:39 |
Last modified on | 2013-03-22 16:48:39 |
Owner | rspuzio (6075) |
Last modified by | rspuzio (6075) |
Numerical id | 10 |
Author | rspuzio (6075) |
Entry type | Proof |
Classification | msc 03-00 |
Classification | msc 05A05 |
Classification | msc 20F55 |