📂Abstract Algebra

Orbits, Cycles, and Transpositions in Abstract Algebra

Definition ¹

Let $\sigma$ be a permutation of a group $G$. Then the equivalence relation $\sim$ for $a, b \in G$ is defined by $a \sim b$ when there exists an integer $n \in \mathbb{Z}$ satisfying $b=\sigma^n (a)$.

1. The equivalence classes of $\sim$ are called the orbits of $\sigma$.
2. A permutation that has at most one orbit with more than one element is called a cycle.
3. Among the orbits of a cycle, the cardinality of the orbit with the largest cardinality is called the length of the cycle.
4. A cycle of length $2$ is called a transposition.
5. If the orbits corresponding to cycles share no elements, they are said to be disjoint.

Explanation

It is normal not to understand from the definitions alone, so let us look at some actual examples.

Orbit

Consider the permutation $$ \sigma = \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 8 & 6 & 7 & 4 & 1 & 5 & 2 \end{bmatrix} $$ in $S_{8}$. The above expression represents $$ 1 \to 3 \to 6 \to 1 \\ 2 \to 8 \to 2 \\ 4 \to 7 \to 5 \to 4 $$ Therefore, the equivalence relation $\sim$ determines the following three equivalence classes. $$ \left\{ 1, 3, 6 \right\} \\ \left\{ 2, 8 \right\} \\ \left\{ 4 , 5 , 7 \right\} $$

Cycle

Consider the permutation $$ \mu_{1} = \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 5 & 1 & 4 \end{bmatrix} $$ in $S_{5}$. The above permutation is $1 \to 3 \to 5 \to 4 \to 1$, so excluding the unchanged $2$, it may be written simply as $(1,3,5,4)$. One thing to be careful about is that when using this notation, order matters, so $(1,3,5,4) = (3,5,4,1)$ but $(1,3,5,4) \ne (1,5,3,4)$. Also, consider $$ \mu_{2} = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{bmatrix} $$ Since $(1,2)$ does not even express that $3$ is present, we must clearly state that it is $(1,2)$ in $S_{3}$.

Length

The orbits of the cycle $$ \mu_{1} = \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 5 & 1 & 4 \end{bmatrix} $$ are only the two $$ \left\{ 1,3,4,5 \right\} \\ \left\{ 2 \right\} $$ Here, since $ | \left\{ 1,3,4,5 \right\} | = 4$ and $| \left\{ 2 \right\} | =1 $, the length of $\mu_{1}$ is $4$.

Transposition

The cycle $$ \mu_{2} = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{bmatrix} = (1,2) $$ is a transposition since its length is $2$. Simply put, it is a cycle that exchanges only two elements. In general, it can be written as $$ (1,2, \cdots , n) = (1, n) (1, n-1 ) \cdots (1,3) (1,2) $$ If we want to take $3$ as the reference, we can change it to $$ (1,2, \cdots , n) = (3, 4, \cdots , n , 1, 2 ) = (3 , 2) (3, 1) \cdots (3,4) $$ This is a quite useful property, so be sure to remember it.

Disjoint

Consider $$ \sigma = \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 8 & 6 & 7 & 4 & 1 & 5 & 2 \end{bmatrix} = (1,3,6) (2,8) (4,7,5) $$ The three cycles $(1,3,6)$, $(2,8)$, and $(4,7,5)$ are disjoint since their corresponding orbits share no elements. What we can learn from this expression is that it makes no difference to write it as $$ (1,3,6) (2,8) (4,7,5) = (4,7,5) (2,8) (1,3,6) $$ A permutation may be expressed as a product of cycles, and if we regard such products as the same, then the orbits are uniquely determined.

Theorem

• [1]: Every permutation of a finite symmetric group with more than one element can be expressed as a product of transpositions.
• [2]: Every permutation of a finite symmetric group can be expressed as a product of disjoint cycles.