Problem Set 1: Warm Up

In this problem we review doing calculations in symmetric groups. You do not need to show any work, just the final answers.

1. Below are compositions of permutations expressed in cycle notation. Express each permutation as a collection of disjoint cycles; that is, calculate the cycle notation for the composite permutation.

   1. $(134)(241)(1234)$
   2. $(15)(14)(13)(12)$
   3. $(15342)(43512)$
   Solution

   1. $(24)$
   2. $(12345)$
   3. $\ve$

2. Calculate the order of the following permutations. Beware, I may be trying to trick you!

   1. $(123)(45)(67)$
   2. $(325)(146)(27)$
   Solution

   1. Since the cycles are disjoint, the order is the least common multiple of the lengths, which is $\lcm(3,2,2) = 6$.
   2. First we express the permutation as a product of disjoint cycles, \[ (325)(146)(27) = (146)(2753). \] Thus, the order of this permutation is $\lcm(3,4) = 12$.

3. For each of the following permutations $\sigma$, determine the inverse permutation $\sigma^{-1}$.

   1. $(12345)$
   2. $(123)(456)$
   3. $(12)(345)(6789)$

   Can you see a general recipe for finding the inverse of a permutation expressed in cycle notation?

   Solution

   The general trick is to write each cycle in reverse order.

   1. $(54321)$
   2. $(321)(654)$
   3. $(21)(543)(9876)$

1. Give an example of an abelian group that is not cyclic (and prove it).

   Solution

   There are many examples, but the simplest is $G := C_2 \times C_2$. Every cyclic group is abelian, and direct products of abelian groups are abelian. Hence $G$ is abelian. Every element in $G$ has order dividing 2 while the group has order 4, hence $G$ is not cyclic.

2. Find two non-isomorphic groups of order 6 and prove they are not isomorphic.

   Solution

   Let $G_1 = C_6$ be the cyclic group of order 6 and let $G_2 = S_3$ be the 3rd symmetric group. Both groups have order 6 but $G_1$ is abelian while $G_2$ is not. Thus $G_1 \not\cong G_2$.

3. What are the possible orders of elements in the symmetric group $S_5$? For each possible order, find an element in $S_5$ with that order.

   Solution

   The possible orders are $1, 2, 3, 4, 5, 6$. Orders 1 through 5 may be achieved by cycles. Recall that every permutation $\sigma$ may be expressed as a product of disjoint cycles $\sigma = \sigma_1\sigma_2\cdots \sigma_k$ and that $\ord(\sigma) = \lcm\{\ord(\sigma_i) : 1\leq i \leq k\}$. Cycles in $S_5$ can have any length between 1 and 5 and disjoint cycles must have lengths adding up to at most 5. Thus an example of an element of order 6 is $(12)(345)$. The only other type of non-cycle permutation is a product of two disjoint 2-cycles $(12)(34)$, but these have order 2.

4. If $H \subseteq G$ is a subgroup with index 2, prove that $H$ is a normal subgroup of $G$.

   Solution

   The assumption that $H$ has index 2 implies that for all $g \in G\setminus H$,

   Since $H$ is disjoint from $gH$ and $Hg$, it then follows that $gH = Hg$ for all $g \in G\setminus H$. This identity also holds for all $g \in H$. Therefore $gHg\inv = H$ for all $g \in G$, which implies that $H$ is a normal subgroup.

5. Let $D_6$ be the 6th dihedral group (with order 12). Determine all the conjugacy classes of elements of $D_6$.

   Solution

   Observe that

   \[ s r s\inv = r\inv. \tag{1.0.2}\]

   Hence $(r^js) r^k (r^js)\inv = r^{-k}$ for any $k$. Thus $\{r^k, r^{-k}\}$ is a conjugacy class for each $0 \leq k < 6$. Two of these pairs degenerate to singletons, \[ \{1\}, \{r, r^5\}, \{r^2, r^4\}, \{r^3\}. \]

   The relation (1.0.2) implies that $sr = r\inv s$. In other words, moving an $s$ past an $r$ inverts it. Thus

   Hence $r^k s \sim r^{2j - k}s$ for all $0 \leq j < 6$. This gives us two conjugacy classes, \[ \{s, r^2s, r^4s\} \text{ and } \{rs, r^3s, r^5s\}. \] Conjugacy classes of elements and subgroups tend to have some qualitative description. For example, the group $D_6$ may be thought of as the group of linear symmetries of a regular hexagon. If we draw the hexagon inscribed in the unit circle with two vertices on the $x$-axis, then the conjugacy class $\{s, r^2s, r^4s\}$ corresponds to the reflections across vertex axes while the conjugacy class $\{rs, r^3s, r^5s\}$ corresponds to reflection across edge axes.

The table below gives the partial description of a mystery group $G$ of order 8. \[ \begin{array}{|c||c | c | c | c | c | c | c | c |} %CLEAR \hline G & 1 & a & b & c & d & e & f & g \\ \hline \hline 1 & 1 & a & b & c & d & e & f & g \\ \hline a & a & \keep{\blue{1}} & c & b & e & \keep{\blue{d}} & g & f \\ \hline b & b & c & \keep{\blue{a}} & 1 & \keep{\blue{f}} & g & e & d \\ \hline c & c & \keep{\blue{b}} & 1 & a & g & f & d & e \\ \hline d & d & e & \keep{\blue{g}} & f & a & 1 & b & c \\ \hline e & e & \keep{\blue{d}} & f & g & 1 & a & c & b \\ \hline f & f & g & d & e & c & b & a & 1 \\ \hline g & g & f & e & d & b & c & 1 & \keep{\blue{a}} \\ \hline \end{array} \]

1. Using the axioms of a group and information provided, fill in the missing entries of the multiplication table for $G$. There is only one solution!

2. Is $G$ isomorphic to $D_4$? Either find an isomorphism or prove that no such isomorphism exists.

   Solution

   The group $G$ is not isomorphic to $D_4$. Isomorphisms preserve the order of elements, hence isomorphic groups must have the same number of elements of order 4. The multiplication table for $G$ implies that $b, c, d, e, f, g$ all have order 4, whereas $D_4$ only has two elements of order 4 (namely rotation by 90 degrees in both directions.) Thus $G$ and $D_4$ cannot be isomorphic.

Let $G$ be a group and suppose that $H_1, H_2 \subseteq G$ are subgroups such that $H_i \neq G$.

1. Prove that $G \neq H_1 \cup H_2$.

   Solution

   Suppose that $G = H_1 \cup H_2$. Since both $H_i$ are proper, they must each contain an element $h_i \in H_i$ not contained in the other subgroup. But then $h_3 := h_1h_2 \in G$, hence $h_3$ must belong to either $H_1$ or $H_2$. Without loss of generality suppose that $h_3 \in H_1$. Then $h_1\inv \in H_1$ hence $h_2 = h_1\inv h_3 \in H_1$, which contradicts our assumption that $h_2 \notin H_1$. This contradiction implies that $G \neq H_1 \cup H_2$.

2. Find an example of a group $G$ which can be expressed as a union of three proper subgroups $G = H_1 \cup H_2 \cup H_3$.

   Solution

   Let $G = \ZZ/2\ZZ \times \ZZ/2\ZZ$ and define

   \[\begin{aligned} H_1 &:= \langle (1,0)\rangle\\ H_2 &:= \langle (0,1)\rangle\\ H_3 &:= \langle (1,1)\rangle. \end{aligned}\]

   Then each $H_i$ has order 2, hence is proper, and $G = H_1 \cup H_2 \cup H_3$.

3. (Challenge) Let $G$ be a group. Prove that there are three proper subgroups $H_1, H_2, H_3 \subseteq G$ such that $G = H_1 \cup H_2 \cup H_3$ if and only if there is a surjective homomorphism $\rho : G \to \ZZ/2\ZZ \times \ZZ/2\ZZ$.

   Solution

   First, the easy direction. Suppose there exists a surjective homomorphism $\rho : G \to \ZZ/2\ZZ \times \ZZ/2\ZZ$. Let

   \[\begin{aligned} K_1 &:= \langle (1,0)\rangle\\ K_2 &:= \langle (0,1)\rangle\\ K_3 &:= \langle (1,1)\rangle, \end{aligned}\]

   and define $H_i := \rho\inv(K_i)$. Our assumption that $\rho$ is surjective implies that each $H_i$ is proper. Since $\ZZ/2\ZZ \times \ZZ/2\ZZ = K_1 \cup K_2 \cup K_3$, it follows that $G = H_1 \cup H_2 \cup H_3$. That completes the proof of the $\Leftarrow$ direction.

   Now suppose that $G$ has three proper subgroups $H_1, H_2, H_3 \subseteq G$ such that $G = H_1 \cup H_2 \cup H_3$. Throughout the rest of this solution, we will use $i, j, k$ to denote three distinct elements of $\{1,2,3\}$. Let $N := H_1 \cap H_2 \cap H_3$. We prove several claims.
   

   Claim 1: If $h_i \in H_i \setminus H_j$ and $h_j \in H_j \setminus H_i$, then $h_i h_j \in H_k$.
   

   Proof. Let $g := h_i h_j$. Then $g \in G = H_1 \cup H_2 \cup H_3$. Suppose $g \in H_i$. Then $h_j = h_i\inv g \in H_i$, a contradiction. Hence $g \notin H_i$. A similar argument implies that $g \notin H_j$. Thus $g \in H_k$.
   

   Claim 2: $H_i \cap H_j = N$.
   

   Proof. Let $H := H_i \cap H_j$. Since $G \neq H_i \cup H_j$ by part 1, it follows that $H_k \not\subseteq H$. Suppose that $H \not\subseteq H_k$. Let $h \in H \setminus H_k$ and let $h_k \in H_k \setminus H$. Consider $g := h h_k \in G$. Then Claim 1 implies that $g \in H_1 \cap H_2 = H$. But then $h_k = h\inv g \in H$, a contradiction. Thus $H \subseteq H_k$. Hence

   On the other hand, $N \subseteq H$ by definition. Thus $H = N$.
   

   Claim 3: $[H_i : N] = 2$ for each $i$.
   

   Proof. It suffices to show that for all $g_1, g_2 \in H_i \setminus N$ we have $g_1g_2 \in N$. Suppose this were not the case; then $g_1g_2 \in H_i \setminus N$. Problem 1.4.1.4 implies there is an element $h \in H_j \setminus N$. Then Claim 1 implies that $g_2 h$ and $g_1g_2h$ both belong to $H_k$. But then

   Hence $g_1 \in H_i \cap H_k = N$ by Claim 2. This contradicts our assumption that $g_1 \notin N$. Thus $g_1g_2 \in N$.
   

   Claim 4: $[G : H_i] = 2$ for each $i$.
   

   Proof. As in the previous claim, it suffices to prove that for all $g_1, g_2 \in G \setminus H_i$ we have $g_1g_2 \in H_i$. There are essentially two cases: If $g_1, g_2 \in H_j \setminus N$, then Claim 3 implies that $g_1g_2 \in N \subseteq H_i$. Otherwise $g_1 \in H_j \setminus N$ and $g_2 \in H_k \setminus N$. Then Claim 1 implies $g_1g_2 \in H_i$. Thus $[G : H_i] = 2$.
   

   Now we put it altogether. Since each $H_i$ has index 2, Problem 1.2.1.2 implies $H_i$ is a normal subgroup. The intersection of normal subgroups is normal, thus $N$ is a normal subgroup of $G$. Claims 3 and 4 together imply that

   Thus $G/N$ is a group of order 4, hence must be isomorphic to either $\ZZ/4\ZZ$ or $\ZZ/2\ZZ \times \ZZ/2\ZZ$. Every $g \in G$ belongs to some $H_i$ and Claim 3 implies that $g^2 \in N$. Hence every element of $G/N$ has order dividing 2, which eliminates the cyclic case. Therefore $G/N \cong \ZZ/2\ZZ \times \ZZ/2\ZZ$ and the composition of the natural quotient map and this isomorphism gives the desired surjection, \[ \rho : G \to G/N \cong \ZZ/2\ZZ \times \ZZ/2\ZZ. \]

Let $p$ be an odd prime and suppose that $G$ is a finite group of order $2p$. Prove that $G$ is either cyclic or $G \cong D_p$, the $p$th dihedral group.