Cycles, Transpositions, and Alternating Groups Review

# Cycles, Transpositions, and Alternating Groups Review

We will now review some of the recent material regarding cycles in permutations.

- Recall from the
**Cycles in Permutations**page that if $\sigma$ is a permutation in $\{ 1, 2, ..., n \}$ then a**Cycle of Length $s$**in $\sigma$ is denoted $(a_1a_2...a_s)$ if $\sigma(a_1) = a_2$, $\sigma(a_2) = a_3$, …, $\sigma(a_{s-1}) = a_s$, and $\sigma(a_s) = a_1$ and all other elements are mapped to themselves. For example, consider the following permutation:

\begin{align} \quad \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 5 & 6 & 1 & 2 & 4 \end{pmatrix} \end{align}

- Then this permutation contains two cycles, namely the cycles $(1364)$ and $(25)$ and hence $\sigma = (1364)(25)$.

*It is important to note that only the relative order in the notation $(a_1a_2...a_s)$ is important. That is, $(a_1a_2...a_s) = (a_2a_3...a_sa_1)$ for example.*

- On the
**Disjoint Cycles**page we said that two cycles $(a_1a_2...a_s)$ and $(b_1b_2...b_t)$ of $\{1, 2, ..., n \}$ are**Disjoint**if $a_j \neq b_k$ for all $j \in \{1, 2, ... s \}$ and for all $k \in \{1, 2, ..., t \}$. For example, the cycles $(123)$ and $(456)$ are disjoint. However, the cycles $(123)$ and $(34)$ are NOT disjoint.

- We then proved a nice theorem which said that if $\alpha$ and $\beta$ are two disjoint cycles then they commute. That is:

\begin{align} \quad \alpha \circ \beta = \beta \circ \alpha \end{align}

- This is because these cycles act independently on one another.

- We then looked at some basic theorems regarding disjoint cycles on the
**Basic Theorems Regarding Disjoint Cycles**page which are summarized below. Let $\alpha = (a_1a_2...a_s)$ and $\beta = (b_1b_2...b_t)$ be disjoint cycles of $\{ 1, 2, ..., n \}$. Then:

Theorem |
---|

For all positive integers $m$ we have that $(\alpha \circ \beta)^m = \alpha^m \circ \beta^m$. |

If $\epsilon$ is the identity permutation and if $\alpha \circ \beta = \epsilon$ then $\alpha = \beta$. |

- On the
**Decomposition of Permutations as Products of Disjoint Cycles**we proved a very nice theorem which says that if $\sigma$ is a permutation of $\{ 1, 2, ..., n \}$ then $\sigma$ can be expressed as a product of disjoint cycles.

- On the
**Transposition Permutations**page we defined a special type of permutation/cycle. We said that**Transposition**is simply a cycle of length $2$. For example, if we consider the set $\{ 1, 2, 3, 4, 5 \}$ then $(12)$ is a transposition.

- On the
**Basic Theorems Regarding Transpositions**we looked at some basic theorems regarding transpositions which are summarized below.

Theorem |
---|

For every transposition $(ab)$ we have that $(ab) \circ (ab) = \epsilon$. |

For all transpositions $(ab)$ and $(bc)$ we have that $(ab) \circ (bc) = (abc)$. |

- We then noted a very nice result on the
**Decomposition of Permutations as Products of Transpositions**page. With the following formula, we saw that every cycle could be written as a product of transpositions:

\begin{align} (a_1a_2...a_s) = (a_sa_{s-1}) \circ (a_sa_{s-2}) \circ ... \circ ( a_sa_1) \end{align}

- We know that every permutation can be written as a product of disjoint cycles and as a consequence, every permutation can be written as a product of transpositions, though, not necessarily unique.

- On the
**Even and Odd Permutations as Products of Transpositions**page we began to classify permutations in terms of transpositions. We said that a permutation $\sigma$ is an**Even Permutation**if it can be expressed as a product of an even number of transpositions, and we said that $\sigma$ is an**Odd Permutation**if it can be expressed as a product of an odd number of transpositions.

- On
**The Identity Permutation**page we proved an important result which is that the identity permutation $\epsilon$ on $\{ 1, 2, ..., n \}$ is an even permutation.

- On the
**Even and Odd Cycles**page we looked at some simple results regarding products of even/odd cycles which are summarized below.

Theorem |
---|

If $\alpha = (a_1a_2...a_s)$ is an even cycle then $s$ is odd. |

If $\alpha = (a_1a_2...a_s)$ is an odd cycle then $s$ is even. |

If $\alpha$ and $\beta$ are both even cycles then $\alpha \circ \beta$ is even. |

If $\alpha$ and $\beta$ are both odd cycles then $\alpha \circ \beta$ is even. |

If one of $\alpha$ or $\beta$ is an even cycle and the other is an odd cycle then $\alpha \circ \beta$ is odd. |

- On the
**Conjugate Cycles**page we said that if $\sigma$ is a permutation of $\{ 1, 2, ... n \}$ and $\alpha = (a_1a_2...a_s)$ is a cycle then the**Conjugate of the Cycle $\alpha$**with respect to the permutation $\sigma$ is defined as:

\begin{align} \quad \rho = \sigma \alpha \sigma^{-1} \end{align}

- On
**The Order of a Permutation**page we defined the**Order of a Permutation**$\sigma$ denoted $\mathrm{order} (\sigma) = m$ to be the least positive integer $m$ such that $\sigma^m = \epsilon$. We noted that $\mathrm{order} (\sigma) = 1$ if and only if $\sigma = \epsilon$. We also noted that if $\alpha$ is a transposition then $\mathrm{order} (\alpha) = 2$, and if $\alpha$ is a cycle of length $s$ then $\mathrm{order} (\alpha) = s$.

- Lastly, on
**The Order Theorem for Permutations**page we proved that if $\sigma$ is any permutation with decomposition $t_1t_2....t_k$ of disjoint cycles with lengths $m_1, m_2, ..., m_k$ respectively, then:

\begin{align} \quad \mathrm{order} (\sigma) = \mathrm{lcm} \{ m_1, m_2, ..., m_k \} \end{align}