Math 120A HW 5 Solutions

1. In this problem we consider permutations in $S_7$.
   1. The orbits are $\{1,2,5\}$, $\{3,4,7\}$, and $\{6\}$.
   2. One such permutation is $(1\;3)(2\;4\;5\;7)$.
   3. Another such permutation is $(1\;3)(2\;4\;7\;5)$.
2. Let $n \in \mathbb{Z}^+$ and consider an arbitrary permutation $\sigma \in S_n$.
   1. No, for example if $\sigma = (1\;2)$ then $\sigma^2$ is the identity, and the set $\{1,2\}$ is an orbit of $\sigma$ but not of $\sigma^2$. (For a less trivial example, let $\sigma$ be a cycle of length 4.)
   2. Yes, every orbit of $\sigma^{-1}$ is an orbit of $\sigma$ and conversely. More specifically, for every $x \in \{1,2,\ldots,n\}$ the orbit of $x$ under $\sigma^{-1}$ is equal to the orbit of $x$ under $\sigma$. This is because $$\{(\sigma^{-1})^k(x) : k \in \mathbb{Z}\} = \{\sigma^{-k}(x) : k \in \mathbb{Z}\} = \{\sigma^k(x) : k \in \mathbb{Z}\}.$$ (Here we are using the fact that $k \in \mathbb{Z} \iff -k \in \mathbb{Z}$.)
3. The non-cycles in $S_4$ are $(1\;2)(3\;4)$, $(1\;3)(2\;4)$, and $(1\;4)(2\;3)$. To see this, note that the only way to partition the set $\{1,2,3,4\}$ into orbits such that more than one orbit has more than one element is to partition it into two orbits with two elements each. There are three ways to do this (corresponding to the three elements $2$, $3$, and $4$ that we can pair with $1$, for example.) Each of these partitions determines a unique permutation. (In general, any partition into orbits each of which has 1 or 2 elements determines a unique permuation.) We have written these three non-cyclic permutations in a way that makes it clear that each of them is a product of disjoint cycles.
4. Consider the permutation $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 6 & 2 & 5 & 3 & 4 & 1 \end{pmatrix}.$
   1. $\sigma = (1\;6)(3\;5\;4)$.
   2. $\sigma = (1\;6)(3\;5)(5\;4)$ (for example.)
5. Consider the permutation $\sigma = (1\;4)(3\;4)(1\;2)(1\;3)$ in $S_5$.
   1. We have $$\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5\\ 1 & 4 & 2 & 3 & 5 \end{pmatrix} = (2\;4\;3) = (2\;4)(4\;3)$$ (for example.)
   2. $\sigma$ cannot be equal to a product of three transpositions because it is even, and no permutation can be both even and odd (see below.)
6. Suppose toward a contradiction that some permutation $\sigma \in S_n$ is both even and odd. Then $\sigma^{-1}$ is even because $\sigma$ is even. This implies that the identity permutation of $S_n$ is odd because it is the product of an even permutation (namely $\sigma^{-1}$) with an odd permutation (namely $\sigma$.) This contradicts a lemma from class that said the identity permutation of $S_n$ is not odd.