Equality of Cycles

From ProofWiki
Jump to: navigation, search


Let $S_n$ denote the symmetric group on $n$ letters, realised as the permutations of $\left\{{1, \ldots, n}\right\}$.

Let $\rho = \begin{bmatrix} a_0 & \cdots & a_{k-1} \end{bmatrix}$, $\sigma = \begin{bmatrix} b_0 & \cdots & b_{k-1} \end{bmatrix} \in S_n$ be $k$-cycles of $S_n$.

For any $d \in \Z$, by Integer is Congruent to Integer less than Modulus we can associate to $d$ a unique integer $\tilde d \in \left\{{0, \ldots, k-1}\right\}$ such that $d \equiv \tilde d \pmod k$.

Define $a_d$ and $b_d$ for any $d \in \Z$ by $a_d = a_{\tilde d}$ and $b_d = b_{\tilde d}$

Choose $i, j \in \left\{{1, \ldots, k}\right\}$ such that:

$\displaystyle a_i = \min\left\{ {a_0, \ldots, a_{k-1} }\right\}$
$\displaystyle b_j = \min\left\{ {b_0, \ldots, b_{k-1} }\right\}$

Then $\rho = \sigma$ if and only if for all $d \in \Z$, $a_{i + d} = b_{j + d}$.

That is, $\rho = \sigma$ if and only if they are identical when written with the lowest element first.