Permutation Induces Equivalence Relation

Theorem

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

Let $\pi \in S_n$.

Let $\mathcal R_\pi$ be the relation defined by:

$i \mathcal R_\pi j \iff \exists k \in \Z: \pi^k \left({i}\right) = j$

Then $\mathcal R_\pi$ is an equivalence relation.

Corollary

It follows that $i \mathcal R_\pi j$ if $i$ and $j$ are in the same cycle of $\pi$.

Proof

Let $\pi \in S_n$.

First we note that, from Finite Group Elements of Finite Order, every element of a finite group has finite order.

Thus $\pi$ has finite order, so $\exists r \in \Z: \pi^r = e$

Checking in turn each of the critera for equivalence:

Reflexive

From above, $\exists r \in \Z: \pi^r = e$.

Therefore $\exists k \in \Z: \pi^k \left({i}\right) = i$.

So $\mathcal R_\pi$ is reflexive.

$\Box$

Symmetric

Let $\pi^k \left({i}\right) = j$.

Because $\pi^r = e$, we have $\pi^r \left({i}\right) = i$ (from above).

Thus $\pi^{r-k} \left({j}\right) = i$.

So $\mathcal R_\pi$ is symmetric.

$\Box$

Transitive

Let $\pi^{s_1} \left({i}\right) = j, \pi^{s_2} \left({j}\right) = k$.

Then $\pi^{s_1 + s_2} \left({i}\right) = k$.

So $\mathcal R_\pi$ is transitive.

$\Box$

All criteria are met, and so $\mathcal R_\pi$ is an equivalence relation.

$\blacksquare$