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:
(1)
\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:
(2)
\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 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.
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)$.
(3)
\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:
(4)
\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:
(5)
\begin{align} \quad \mathrm{order} (\sigma) = \mathrm{lcm} \{ m_1, m_2, ..., m_k \} \end{align}