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}