Brian Bi

Section 6.11. Permutation Representations

Exercise 6.11.1 An action of $$S_3$$ on a set of four elements is a homomorphism $$\varphi : S_3 \to S_4$$. The kernel of this homomorphism is a normal subgroup of $$S_3$$. There are three cases:

1. $$\ker\varphi = S_3$$. The action $$\varphi$$ is therefore trivial.
2. $$\ker\varphi = A_3$$. The image of $$\varphi$$ has order 2, so it consists of the identity plus some element of $$S_4$$ that has order 2, of which there are 9 in total (6 transpositions and 3 elements consisting of the product of a pair of disjoint transpositions). The even permutations in $$S_3$$ therefore act trivially on the set, whereas the odd permutations all permute the set in the same way, acting as the other element of the image. There are therefore 9 such actions.
3. $$\ker\varphi$$ is trivial. Then $$\varphi(x)$$ must have order 3 in $$S_4$$; call it $$x'$$. Likewise $$y' = \varphi(y)$$ must have order 2, and we must have $$y'x' = x'^2 y'$$ in order for $$\varphi$$ to be a valid homomorphism. $$x'$$ can only be a 3-cycle; without loss of generality, say $$x' = (1\ 2\ 3)$$. We know there is one valid choice $$y' = (1\ 2)$$ and if $$y'$$ transposes two of the three elements 1, 2, 3 then we can always relabel 1, 2, 3 so that $$y' = (1\ 2)$$. Now suppose $$y'$$ is a transposition involving the index 4; without loss of generality, say $$y = (1\ 4)$$ (we can simply relabel 1, 2, 3 to make this true). Then $$y'x' = (1\ 2\ 3\ 4)$$ and $$x'^2y' = (1\ 4\ 3\ 2)$$, so this choice of $$y'$$ is not valid. Or suppose $$y'$$ is a product of two transpositions; one of these must involve two of the three elements 1, 2, 3, so again we can simply relabel 1, 2, 3 so that $$y' = (1\ 2)(3\ 4)$$. Then $$y'x' = (2\ 4\ 3)$$ and $$x'^2y' = (2\ 3\ 4)$$, so again this choice of $$y'$$ is not valid. Therefore for any faithful action of $$S_3$$ on a set of four elements there is some way of labelling the elements so that $$x$$ acts as $$(1\ 2\ 3)$$ and $$y$$ as $$(1\ 2)$$, $$S_3$$ fixes one of the elements of the set and $$\sigma \in S_3$$ acts on the other three elements by permuting them according to $$\sigma$$.

Exercise 6.11.2 Suppose $$T$$ acts on the set of two elements nontrivially. Then the action is a surjective homomorphism $$\varphi : T \to S_2$$. But we argued in Exercise 6.9.4 that $$T$$ is isomorphic to $$A_4$$. We can now apply a similar argument to that used in Exercise 6.7.11: the image of a 3-cycle under $$\varphi$$ must be the identity, but the 3-cycles generate $$A_4$$, so $$\varphi$$ is trivial, contradicting the assumption that $$\varphi$$ is surjective. Therefore the only possible action of $$T$$ on a set of 2 elements is trivial.

Exercise 6.11.3 Let $$\varphi : G \to \operatorname{Perm}(S)$$ be the action of $$G$$ on $$S$$. Then, $$H$$ is the subset of $$G$$ consisting of elements mapped to the identity permutation; that is, $$H$$ is the kernel of $$\varphi$$. Therefore $$H$$ is a normal subgroup of $$G$$.

Exercise 6.11.4 $$D_4$$ consists of the identity, three rotations, and four reflections. The three rotations each have no fixed points, each reflection across a diagonal has two fixed points, and the other two reflections, across lines parallel to two sides of the square, have no fixed point. That is, only the identity of $$D_4$$ acts as the identity on the set of four vertices; this action is faithful. On the other hand, $$D_4$$ does not act faithfully on the diagonals; for example, the 180 degree rotation fixes both diagonals.

Exercise 6.11.5 Denote the two orbits by $$\{a, b, c\}, \{d, e\}$$. The image of the action $$\varphi : G \to \operatorname{Perm}(S)$$ therefore consists only of those permutations that leave these two subsets invariant, that is, $$\im \varphi \subseteq S_3 \times S_2$$. This restricts the possible actions to injective homomorphisms $$\varphi : G \to S_3 \times S_2$$; in other words, $$G$$ must be isomorphic to a subgroup of $$S_3 \times S_2$$ (which will be its image under $$\varphi$$). We will identify $$G$$ with this subgroup from now on, and represent its elements in the form $$(g_1, g_2)$$, where $$g_1 \in S_3$$ and $$g_2 \in S_2$$, and $$g_1$$ acts on $$\{a, b, c\}$$ while $$g_2$$ acts on $$\{d, e\}$$. Since $$G$$ must act transitively on $$\{a, b, c\}$$ and $$\{d, e\}$$, the projections $$G_1 = \{g_1 \mid (g_1, g_2) \in G\}$$ and $$G_2 = \{g_2 \mid (g_1, g_2) \in G\}$$ must respectively act transitively on $$\{a, b, c\}$$ and $$\{d, e\}$$. This allows us to break down the possibilities into the following cases:

1. $$G$$ contains the element $$(1, -1)$$ where $$-1$$ denotes the non-identity element of $$S_2$$. This implies that $$G$$ has the structure $$G_1 \times S_2$$, where $$G_1$$ is some subgroup of $$S_3$$, and (as stated above) $$G_1$$ acts transitively on $$\{a, b, c\}$$. This implies that $$G_1$$ is either $$S_3$$ or $$C_3$$, so $$G$$ may be $$S_3 \times S_2$$ or $$C_3 \times S_2$$.
2. $$G$$ doesn't contain the element $$(1, -1)$$ and there is only one element $$\sigma \in S_3$$ such that $$(\sigma, -1) \in G$$. Then there can't be any $$\tau \in S_3 \setminus \{1\}$$ such that $$(\tau, 1) \in G$$, because the product would be $$(\sigma', -1)$$ where $$\sigma' \neq \sigma$$. So $$G$$ can only be $$\{(1, 1), (\sigma, -1)\}$$, where $$\sigma$$ has order 2. But this fails to satisfy the requirement that $$G_1$$ acts transitively.
3. $$G$$ doesn't contain the element $$(1, -1)$$ and there are at least two elements, $$\sigma \neq \sigma'$$, such that $$(\sigma, -1) \in S_3$$ and $$(\sigma', -1) \in S_3$$. Both $$\sigma$$ and $$\sigma'$$ must be transpositions; if $$\sigma$$ were a 3-cycle, then $$(\sigma, -1)^3$$ would be $$(1, -1)$$, which contradicts our assumption. But any two distinct transpositions generate $$S_3$$, so $$G$$ must contain an element of the form $$(g_1, g_2)$$ for every possible $$g_1$$, and $$g_2$$ will be $$+1$$ if $$g_1$$ is even, $$-1$$ otherwise. So $$G$$ is just $$S_3$$ together with an extraneous sign bit.

We see that the possibilities for $$G$$ are $$S_3 \times S_2$$, $$C_3 \times S_2$$ (i.e., $$C_6$$), and $$S_3$$, where the latter acts on $$\{a, b, c\}$$ in the usual way and according to its sign on $$\{d, e\}$$. It is easy to see that these groups yield the orbits $$\{a, b, c\}$$ and $$\{d, e\}$$ as required.

Exercise 6.11.6 The subspaces are generated by (0, 1), (1, 0), (1, 1), and (1, 2). An invertible matrix will always map a one-dimensional subspace to a one-dimensional subspace and this mapping is injective. Therefore there exists a homomorphism $$\varphi : GL_2(F) \to S_4$$ where each invertible matrix is mapped to the permutation it induces on these four subspaces. The kernel of this homomorphism consists only of diagonal matrices since only a diagonal matrix can both map (0, 1) to a multiple itself and also do likewise for (1, 0). Furthermore, such a diagonal matrix has to be $$\diag(1, 1)$$ or $$\diag(2, 2)$$ and not $$\diag(1, 2)$$ or $$\diag(2, 1)$$ as these would exchange the (1, 1) and (1, 2) subspaces. Since the kernel has order 2, the image of $$\varphi$$ must have order $$|GL_2(F)|/2$$. But $$|GL_2(F)| = (3^2 - 1)(3^2 - 3) = 48$$, which can be determined by observing that an invertible matrix can have an arbitrary nonzero vector for its first column and then the second column can be anything except a multiple of the first column. So $$|\im \varphi| = 24$$, which implies that the image is the entire group $$S_4$$.

Exercise 6.11.7

1. Suppose $$\varphi : D_4 \to S_n$$ is injective. Then $$|S_n| \geq |D_4|$$. This implies $$n \geq 4$$. It was previously established in Exercise 6.11.3 that $$D_4$$ acts faithfully on the vertices of a square, so $$n = 4$$.
2. Suppose $$\varphi : D_6 \to S_n$$ is injective. Since $$D_6$$ contains elements of order 6, $$S_n$$ must as well. This implies that $$n$$ is at least 5 (all elements of $$S_4$$ have order 1, 2, 3, or 4). Now consider the action of $$D_6$$ on the set $$\{E_1, E_2, E_3, F_1, F_2\}$$ where the $$E$$'s are the three long diagonals of a hexagon, $$F_1$$ is a set of three alternating sides of the hexagon, and $$F_2$$ is the set of the other three sides. Any reflection in $$D_6$$ acts as a transposition on $$E_1, E_2, E_3$$, so no subsequent rotation, which acts as a 3-cycle on this set, can restore all three diagonals to their original positions. Among proper rotations, only the 180 degree rotation fixes the three diagonals, but it exchanges $$F_1$$ and $$F_2$$. Therefore the action we have defined is faithful, establishing that $$n = 5$$.
3. If $$\varphi : H \to S_n$$ is injective, then $$\varphi(i)$$ must have order 4, therefore it must contain a 4-cycle. Thus far we know $$n \geq 4$$. Without loss of generality, say $$\varphi(i)$$ contains the 4-cycle $$(1\ 2\ 3\ 4)$$. Then $$\varphi(-1)$$ contains the transpositions $$(1\ 3)$$ and $$(2\ 4)$$. Now $$j^2 = -1$$ also, so if $$j$$ maps $$1$$ to $$a$$, then it must map $$a$$ to 3, and if it maps 3 to $$b$$, then it must map $$b$$ to 1; that is, $$j$$ must contain a 4-cycle $$(1\ a\ 3\ b)$$. It must also contain a 4-cycle $$(2\ c\ 4\ d)$$ by similar reasoning. If these were the same cycle, then the product of $$\varphi(i)$$ and $$\varphi(j)$$ would contain the transpositions $$(1\ 3)$$ and $$(2\ 4)$$. But this product is $$\varphi(k)$$, and its square $$\varphi(-1)$$ would then fix 1, 2, 3, and 4, which contradicts our earlier assumptions. Likewise if they were inverse cycles to each other then $$\varphi(k)$$ would fix 1, 2, 3, and 4 and so would $$\varphi(-1)$$. Therefore, we know that the two 4-cycles in $$j$$ must be different, which requires $$n \geq 8$$. The action of $$H$$ on itself by left-multiplication is a faithful action on a set of size 8. Therefore $$n = 8$$.

Exercise 6.11.8 We previously argued (see Exercise 2.4.6 and Exercise 2.6.10) that the automorphisms of $$C_n$$ are precisely the functions $$\varphi_k$$ defined by $$\varphi_k(x) = kx$$ for $$k$$ relatively prime to $$n$$. In the case where $$n$$ is a prime $$p$$ there are therefore exactly $$p-1$$ automorphisms, each sending 1 to a different nonzero value. $$\varphi_k$$ are in bijective correspondence with the multiplicative group $$\mathbb{F}_p^\times$$ which also contains exactly the elements $$1, 2, \ldots, p-1$$. In fact, the set of automorphisms and the multiplicative group are isomorphic as groups, where the isomorphism sends $$k \in \mathbb{F}_p^\times$$ to $$\varphi_k$$. It is easy to verify that this is indeed a group isomorphism.