Theoretical Justification for Cycle Notation
Jump to navigation
Jump to search
Theorem
Let $\N_k$ be used to denote the initial segment of natural numbers:
- $\N_k = \closedint 1 k = \set {1, 2, 3, \ldots, k}$
Let $\rho: \N_n \to \N_n$ be a permutation of $n$ letters.
Let $i \in \N_n$.
Let $k$ be the smallest (strictly) positive integer for which $\map {\rho^k} i$ is in the set:
- $\set {i, \map \rho i, \map {\rho^2} i, \ldots, \map {\rho^{k - 1} } i}$
Then:
- $\map {\rho^k} i = i$
Proof
Aiming for a contradiction, suppose $\map {\rho^k} i = \map {\rho^r} i$ for some $r > 0$.
As $\rho$ has an inverse in $S_n$:
- $\map {\rho^{k - r} } i = i$
This contradicts the definition of $k$, because $k - r < k$
Thus:
- $r = 0$
The result follows.
$\blacksquare$
Sources
- 1996: John F. Humphreys: A Course in Group Theory ... (previous) ... (next): Chapter $9$: Permutations: Proposition $9.1$