Hw7 Problem 3

Return to Homework 7, Glossary, Theorems

Problem 3

(a) (+) Prove that the order of a cycle of length $k$ is $k$.
(b) (+) Prove that the order of the product of two disjoint cycles in $S_n$ ($n\geq 2$) is the least common multiple of the lengths of the cycles. Deduce that the order of a product of $m$ disjoint cycles is the least common multiple of their lengths.
(c)(*) Write out the possible disjoint cycle structures of $S_{7}$. (For ease of notation, let ($\underline{n}$) denote a cycle of length $n$, so for example, ($\underline{4}$)($\underline{2}$)($\underline{1}$) is one possible structure, which will have order $4$.) Determine the possible orders of $S_{7}$.
(d) (+) Find the orders of the following elements of $S_7$:
(a) $(135)$ (b) $(24)(163)$ (d) $(124)(3576)$ (e) $(1234)(175)$

Solution
(a) Let $\sigma \in S_n$ be a cycle of length $k$; say, $\sigma = (a_1 a_2 \cdots a_k)$. Then note $\sigma^2(a_i) = a_{i+1}$ for $i=1, \dots, k-1$ and $\sigma^2(a_k) = a_1 = a_{k+_k 1}$. In general, we can see that $\sigma^n(a_i) = a_{i+_kn}$. So, for $0<i<k$, $\sigma^i(a_j) \neq a_j$, and $\sigma^k(a_j)=a_j$ for $j=1, \dots, k$. Thus, $\sigma^k =(1)$ and $|\sigma| = k$.

(b) Let $\sigma, \tau \in S_n$ be disjoint cycles of length $k$ and $l$, respectively. Let $m = \textrm{lcm}(k,l)$ and note that $(\sigma\tau)^m=(1)$. Indeed, since $\sigma$ and $\tau$ are disjoint, they commute, so $(\sigma\tau)^m=\sigma^m\tau^m=(1)(1)=(1)$, as $k$ and $l$ both divide $m$. Now, for $0<n<m$, we can use the division algorithm to write $n=q_1k+r_1$ and $n=q_2l+r_2$, where $0\leq r_1<k$ and $0 \leq r_2<l$. So,

(1)
\begin{align} (\sigma\tau)^n=\sigma^n\tau^n=\sigma^{q_1k+r_1}\tau^{q_2l+r_2}=\sigma^{r_1}\tau^{r_2} \end{align}

Now, since $n<\textrm{lcm}(k,l)$, either $r_1\neq 0$, or $r_2\neq 0$. In particular, by part (a), we have $\sigma^{r_1}\tau^{r_2}\neq (1)$. So $m$ is the smallest positive integer such that $(\sigma\tau)^m = (1)$, i.e. $m=\textrm{lcm}(k,l)=|\sigma\tau|$. A similar argument will show that the order of a disjoint product of $m$ cycles is the LCM of their lengths.

(c)(*)First let's list the possible disjoint cycles:

(2)
\begin{align} (\underline{7}) \end{align}
(3)
\begin{align} (\underline{6})(\underline{1}) \end{align}
(4)
\begin{align} (\underline{5})(\underline{2}) \end{align}
(5)
\begin{align} (\underline{5})(\underline{1})(\underline{1}) \end{align}
(6)
\begin{align} (\underline{4})(\underline{3}) \end{align}
(7)
\begin{align} (\underline{4})(\underline{2})(\underline{1}) \end{align}
(8)
\begin{align} (\underline{4})(\underline{1})(\underline{1})(\underline{1}) \end{align}
(9)
\begin{align} (\underline{3})(\underline{3})(\underline{1}) \end{align}
(10)
\begin{align} (\underline{3})(\underline{2})(\underline{2}) \end{align}
(11)
\begin{align} (\underline{3})(\underline{2})(\underline{1})(\underline{1}) \end{align}
(12)
\begin{align} (\underline{3})(\underline{1})(\underline{1})(\underline{1})(\underline{1}) \end{align}
(13)
\begin{align} (\underline{2})(\underline{2})(\underline{2})(\underline{1}) \end{align}
(14)
\begin{align} (\underline{2})(\underline{2})(\underline{1})(\underline{1})(\underline{1}) \end{align}
(15)
\begin{align} (\underline{2})(\underline{1})(\underline{1})(\underline{1})(\underline{1})(\underline{1}) \end{align}
(16)
\begin{align} (\underline{1})(\underline{1})(\underline{1})(\underline{1})(\underline{1})(\underline{1})(\underline{1}) \end{align}

Now the possible orders of $S_{7}$ will be the least common multiples of the lengths of the cycles in the possible disjoint cycles. Then the possible orders are $7, 6, 10, 5, 12, 4, 3, 2, 1$.

(d) (+) Find the orders of the following elements of $S_7$:
(a) $|(135)|=3$ (b) $|(24)(163)|=6$ (d) $|(124)(3576)|=12$ (e) $|(1234)(175)|=|(175234)|=6$

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License