Fix a
permutation σ, and take two
2-cycle decompositions
σ=α1⋯αn=β1⋯βk
We will show that
2∣n iff 2∣k and so conclude that
n≡k (mod 2)
To do this, assume for contradiction that
2∣n but
2∤k. Now note that:
e=σσ−1=(α1⋯αn)(β1⋯βk)−1=(α1⋯αn)(βk−1⋯β1−1)=(α1⋯αn)(βk⋯β1)=α1⋯αn⋅βk⋯β1since 2-cycles are their own inverse
Thus we have written
e as a
product of
n+k 2-cycles. Since by assumption
n and
k have different parities, then
n+k is odd, so we have written
e as a
product of an odd number of
2-cycles. This contradicts that every 2-
cycle decomposition of
e has an even number of
terms, proven below.
Lemma. Every 2-
cycle decomposition of the identity
permutation e has an even number of
terms.
Assume that
e is decomposed into
2-cycles as follows:
e=β1⋯βr
and let
(a b)=βr. Then the
product βr−1βr is in one of the following forms:
(a b)(a b)(a c)(a b)(b c)(a b)(c d)(a b)
These
products are respectively equal to the following:
e(a b)(b c)(a c)(c b)(a b)(c d)
In the case
(1), we are able to remove the final two
terms off ther
product, thus expressing
e as a
product of
r−2 2-cycles.
In the cases
(2)−(4), note that the second
term in the
product does not contain an
a. As such, cases
(2)−(4) allow us to express
e in a form with the rightmost
a moved to the left.
We repeat this movement until case
(1) is reached. This
must happen because, if it does not, then
a will be in the leftmost
term of the
product, meaning that
e does not
fix a, which is a contradiction.
As such, eventually case
(1) will be reached, allowing us to
re-express
e as a
product of
r−2 2-cycles. Repeating this process, we will terminate either with an empty
product or a
product of a single
2-cycle. The latter is impossible, because it would not be equal to
e. Thus, we will terminate on the empty
product, meaning that
r was originally even.
This is called a