Even Permutation is Product of 3-Cycles

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \N$ such that $n \ge 3$.

Let $\pi: \N_n \to \N_n$ be a permutation on $n$ letters.

Let $\pi$ be an even permutation.


Then $\pi$ can be expressed as the composition of cyclic permutations of length $3$.


Proof

Let $A_n$ denote the alternating group on $n$ letters.

By Alternating Group is Set of Even Permutations, $A_n$ is the set of all even permutations of $S_n$.

$\pi$ can therefore be analysed in the context of elements of $A_n$.


The proof proceeds by induction.

For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:

$\pi \in A_n$ can be expressed as the composition of cyclic permutations of length $3$


From Identity Mapping on Symmetric Group is Even Permutation, the identity permutation $e$ on $S_n$ is even.

But there are no cyclic permutations of length $3$ in $S_1$ or $S_2$.

So $\map P 1$ and $\map P 2$ are false.


Basis for the Induction

$\map P 3$ is the case:

$\pi \in A_3$ can be expressed as the composition of cyclic permutations of length $3$.

The even permutations of $A_3$ are $e$, $\tuple {1, 2, 3}$ and $\tuple {1, 3, 2}$.

Thus $\map P 3$ is seen to hold trivially.


This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that if $\map P {k - 1}$ is true, where $k > 3$, then it logically follows that $\map P k$ is true.


So this is the induction hypothesis:

$\pi \in A_{k - 1}$ can be expressed as the composition of cyclic permutations of length $3$.


from which it is to be shown that:

$\pi \in A_k$ can be expressed as the composition of cyclic permutations of length $3$.


Induction Step

This is the induction step:

Let $\pi \in A_n$.

Consider the permutation:

$\sigma := \tuple {\pi_n, n, i} \circ \pi$

where $\pi_i = n$.

We have:

\(\ds \map \sigma n\) \(=\) \(\ds \tuple {\pi_n, n, i} \circ \map \pi n\)
\(\ds \) \(=\) \(\ds \map {\tuple {\pi_n, n, i} } {\pi_n}\)
\(\ds \) \(=\) \(\ds n\)

and is even.

Because $\sigma$ fixes $n$ and is even, $\sigma$ is an even permutation of $\set {1, 2, \ldots, n - 1}$.

By the |inductive hypothesis, $\sigma$ is the composition of $3$-cycles, say:

$\sigma = \alpha_1 \alpha_2 \dotsm \alpha s$

Setting $\alpha_0 := \tuple {\pi_n, i, n}$, we have:

\(\ds \alpha_0 \alpha_1 \alpha_2 \dotsm \alpha_s\) \(=\) \(\ds \alpha_0 \sigma\)
\(\ds \) \(=\) \(\ds \tuple {\pi_n, i, n} \tuple {\pi_n, n, i} \circ \pi\)
\(\ds \) \(=\) \(\ds \pi\)

and we have expressed $\pi$ as the composition of $3$-cycles

So $\map P {k - 1} \implies \map P k$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\forall n \in \Z_{\ge 0}: \pi \in A_n$ can be expressed as the composition of cyclic permutations of length $3$.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Even_Permutation_is_Product_of_3-Cycles&oldid=520453"