Theoretical Justification for Cycle Notation

From ProofWiki
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