*group*under

*composition*(<$S_n, *$>). E.g. $S=\{1,2,3,4\}$ , $\pi_1 = [3\,4\,2\,1]$ and $\pi_2 = [4\,1\,3\,2]$. To understand composition operation it may be easier to look at a permutation $\pi \in S_n$ as

*bijective function*$\pi : S \rightarrow S$. The composition $\pi_1 * \pi_2$ would be equivalent to $\pi_1(\pi_2(i)), \forall i\in S$ which results in $\pi_1 * \pi_2 = [1\,3\,2\,4] $. We use the notation $\pi^k = \pi*\pi*\pi\ldots *\pi$ to denote a composition applied $k$ times. Since <$S_n,*$> is a group it must have an identity element $e$ which is a permutation such that $e(i) = i, \forall i\in S$.

Now lets focus on the following question:

**Given any permutation $\pi \in S_n$ is there an integer $k \geq 0$ such that $\pi^k = e$ ?**

Lets try few examples with $\pi_1 = [3\, 4\, 2\, 1]$, $\pi_1^2 = [2\, 1\, 4\, 3]$, $\pi_1^3 = [4\, 3\, 1\, 2]$, $\pi_1^4 = [1\, 2\, 3\, 4]$. So for this example $\pi_1$ we were able to find $k=4$ such that $\pi_1^4 = e$. Later we will show that finding such a $k$ is always possible for any permutation $\pi$ and such a $k$ is called the

**of the permutation.**

*order*Recall that every permutation can be decomposed into one or more disjoint cycles. We call a permutation

*cyclic*if it has exactly one cycle in it. E.g. $\pi_c = [3\, 1\, 4\, 2]$ is a cyclic permutation in $S_4$ with cycle being $1 \rightarrow 3 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 1$.

**Lemma:**If $\sigma \in S_n$ is a

*cyclic*permutation then $\sigma^n = e$

**Proof:**Since $\sigma$ is cyclic all elements $S$ form a directed cycle with $n$ nodes. Starting at any node $i$ we need to traverse $n$ edges to get back to $i$. This can be algebraically expressed as $\underbrace{\sigma(\sigma(\ldots \sigma(i))\ldots)}_{n\text{-times}} =i$

$\Box$.

The above lemma states that if a permutation is cyclic on $n$ elements then composing it $n$ times on itself results in an identity permutation. Now we are ready to prove our main theorem:

**Theorem:**$\forall \pi \in S_n$ there exists a $k \geq 0$ such that $\pi^k = e$.

**Proof:**Let $\pi = \sigma_1\sigma_2\ldots \sigma_m$ be the cycle decomposition of $\pi$. Let $|\sigma_i|$ denote size of cycle. Since each of $\sigma_i$ is cyclic permutation in $S_{|\sigma_i|}$ by the previous lemma $\sigma_i^{|\sigma_i|} = e_{|\sigma_i|}$. Where $e_{|\sigma_i|}$ is an identity permutation in $S_{|\sigma_i|}$. Also notice that any multiple of $|\sigma_i|$ is also going to result in an identity permutation (i.e. for any integer $q \geq 1$ , $\sigma_i^{q|\sigma_i|} = e_{|\sigma_i|}$). Let $t = |\sigma_1|\times |\sigma_2|\times \ldots |\sigma_m|$ then $\pi^t = \sigma_1^t\sigma_2^t\ldots \sigma_m^t$ since $t$ is a multiple of $|\sigma_i|, 1\leq i \leq m$ we have $\pi^t = e_{|\sigma_1|}e_{|\sigma_2|}\ldots e_{|\sigma_m|} = e$

$\Box$.

From the above proof its clear that choosing $k = |\sigma_1|\times |\sigma_2|\ldots |\sigma_m|$ which is a multiple of all cycle lengths guarantees that $\pi^k = e$. However from a computational efficiency purpose we are much better if we let that multiple be the

**of $|\sigma_i|,\, 1\leq i\leq m$. Following is an efficient algorithm -- linear time and takes at most $n$ l.c.m computations -- to find the order of any permutation:**

*least common multiple*// Finds the order of a valid permutation ( 1 \leq perm[i] \leq n). size_t FindPermutationOrder(const std::vector< unsigned int > &perm) { size_t n = perm.size(); size_t perm_order = 1; // This overflows if the l.c.m does not fit in 64-bits. std::vector< bool > cycle_mask(n, true); // Find the disjoint cycle lengths in the permutation. size_t cycle_index = 0; while (cycle_index < n) { // Find the start of the next disjoint cycle. if (cycle_mask[cycle_index]) { size_t i = cycle_index; size_t cycle_length = 0; do { cycle_mask[i] = false; i = perm[i] - 1; cycle_length++; } while (i != cycle_index); perm_order = boost::math::lcm(perm_order, cycle_length); } cycle_index++; } return perm_order; }Following are few examples on the algorithm:

Order of [ 5 3 1 2 4 ] is 5 Order of [ 3 4 2 1 ] is 4 Order of [ 1 2 3 4 5 ] is 1 Order of [ 7 8 9 10 1 2 4 3 6 5 ] is 5

## No comments:

Post a Comment