Order of Cycle is Length of Cycle

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S_n$ denote the symmetric group on $n$ letters.

Let $\pi \in S_n$ be a cyclic permutation of length $k$.

Then:

$\order \pi = k$

where:

$\order \pi$ denotes the order of $\pi$ in $S_n$.


Proof

Let $\pi = \tuple {a_0, a_1, \ldots, a_{k - 1} }$.

Observe that:

\(\ds \paren {\paren {j + n} \pmod k} + 1\) \(=\) \(\ds \paren {j + n + 1} \pmod k\)
\(\ds \leadsto \ \ \) \(\ds \map \pi {a_{\paren {j + n} \pmod k} }\) \(=\) \(\ds a_{\paren {j + n + 1} \pmod k}\)
\(\ds \leadsto \ \ \) \(\ds \forall n \in \N, \forall j \in \Z / k \Z: \, \) \(\ds \map {\pi^n} {a_j}\) \(=\) \(\ds a_{\paren {j + n} \pmod k}\)
\(\ds \leadsto \ \ \) \(\ds \forall j < k: \, \) \(\ds \pi^k\) \(=\) \(\ds I_{S_n}\)
\(\, \ds \land \, \) \(\ds \pi^j\) \(\ne\) \(\ds I_{S_n}\) where $I_{S_n}$ denotes the identity mapping on $S_n$

Hence the result, by definition of order of group element.

$\blacksquare$


Sources