Monthly Archives: April 2010

Exhibit generators of an isomorphic copy of Q(8) in Sym(8) via the left regular representation

Use the left regular representation of Q_8 to produce two elements of S_8 which generate a subgroup isomorphic to Q_8.


Recall that Q_8 = \langle i,j \rangle.

Now i(1) = i, i(-1) = -i, i(i) = -1, i(-i) = 1, i(j) = k, i(-j) = -k, i(k) = -j, and i(-k) = j. Thus i \mapsto (1\ i\ -1\ -i)(j\ k\ -j\ -k).

Similarly, j(1) = j, j(-1) = -j, j(i) = -k, j(-i) = k, j(j) = -1, j(-j) = -1, j(k) = i, and j(-k) = -i. Thus j \mapsto (1\ j\ -1\ -j)(i\ -k\ -i\ k).

With the labeling

1 \mapsto 1 -1 \mapsto 2 i \mapsto 3 -i \mapsto 4
j \mapsto 5 -j \mapsto 6 k \mapsto 7 -k \mapsto 8

we have Q_8 \cong \langle (1\ 3\ 2\ 4)(5\ 7\ 6\ 8), (1\ 5\ 2\ 6)(3\ 8\ 4\ 7) \rangle.

Exhibit Dih(8) as a subgroup of Sym(8) in two different ways via the left regular representation

Consider D_8 = \langle r,s \rangle.

  1. List the elements of D_8 as 1,r,r^2,r^3,s,sr,sr^2,sr^3 and label these with the integers 1,2,3,4,5,6,7,8, respectively. Compute the image of each element of D_8 under the left regular representation of D_8 into S_8.
  2. Relabel the elements of D_8 with 1,3,5,7,2,4,6,8, respectively, and recompute the image of each element under the left regular representation. Show that the two subgroups of S_8 obtained in parts 1 and 2 are different.

To save effort we will perform this computation in S_{D_8} and then use the labeling bijections D_8 \rightarrow \{1,2,\ldots,8\} to produce subgroups of S_8. Let \lambda : D_8 \rightarrow S_{D_8} be the left regular representation.

  1. Clearly \lambda(1) = 1.
  2. We have \lambda(r)(1) = r, \lambda(r)(r) = r^2, \lambda(r)(r^2) = r^3, \lambda(r)(r^3) = 1, \lambda(r)(s) = rs = sr^3, \lambda(r)(sr^3) = rsr^3 = sr^6 = sr^2, and \lambda(r)(sr^2) = rsr^2 = sr^5 = sr. Thus \lambda(r) = (1\ r\ r^2\ r^3)(s\ sr^3\ sr^2\ sr).
  3. Note that \lambda(r^2) = \lambda(r)^2. Thus \lambda(r^2) = (1\ r^2)(r\ r^3)(s\ sr^2)(sr\ sr^3).
  4. Note that \lambda(r^3) = \lambda(r)^3. Thus \lambda(r^3) = (1\ r^3\ r^2\ r)(s\ sr\ sr^2\ sr^3).
  5. We have \lambda(s)(1) = s, \lambda(s)(s) = 1, \lambda(s)(r) = sr, \lambda(s)(sr) = r, \lambda(s)(r^2) = sr^2, \lambda(s)(sr^2) = r^2, \lambda(s)(r^3) = sr^3, and \lambda(s)(sr^3) = r^3. Thus \lambda(s) = (1\ s)(r\ sr)(r^2\ sr^2)(r^3\ sr^3).
  6. Note that \lambda(sr) = \lambda(s)\lambda(r). Thus \lambda(sr) = (1\ sr)(r\ sr^2)(r^2\ sr^3)(r^3\ s).
  7. Note that \lambda(sr^2) = \lambda(s)\lambda(r^2). Thus \lambda(sr^2) = (1\ sr^2)(r\ sr^3)(r^2\ s)(r^3\ sr).
  8. Note that \lambda(sr^3) = \lambda(s)\lambda(r^3). Thus \lambda(sr^3) = (1\ sr^3)(r\ s)(r^2\ sr)(r^3\ sr^2).

Now via the labelling

1 \mapsto 1 r \mapsto 2 r^2 \mapsto 3 r^3 \mapsto 4
s \mapsto 5 sr \mapsto 6 sr^2 \mapsto 7 sr^3 \mapsto 8

we have the isomorphic image

  • 1 \mapsto 1
  • r \mapsto (1\ 2\ 3\ 4)(5\ 8\ 7\ 6)
  • r^2 \mapsto (1\ 3)(2\ 4)(5\ 7)(6\ 8)
  • r^3 \mapsto (1\ 4\ 3\ 2)(5\ 6\ 7\ 8)
  • s \mapsto (1\ 5)(2\ 6)(3\ 7)(4\ 8)
  • sr \mapsto (1\ 6)(2\ 7)(3\ 8)(4\ 5)
  • sr^2 \mapsto (1\ 7)(2\ 8)(3\ 5)(4\ 6)
  • sr^3 \mapsto (1\ 8)(2\ 5)(3\ 6)(4\ 7).

Similarly, via the labeling

1 \mapsto 1 r \mapsto 3 r^2 \mapsto 5 r^3 \mapsto 7
s \mapsto 2 sr \mapsto 4 sr^2 \mapsto 6 sr^3 \mapsto 8

we have the isomorphic image

  • 1 \mapsto 1
  • r \mapsto (1\ 3\ 5\ 7)(2\ 8\ 6\ 4)
  • r^2 \mapsto (1\ 5)(3\ 7)(2\ 6)(4\ 8)
  • r^3 \mapsto (1\ 7\ 5\ 3)(2\ 4\ 6\ 8)
  • s \mapsto (1\ 2)(3\ 4)(5\ 6)(7\ 8)
  • sr \mapsto (1\ 4)(3\ 6)(5\ 8)(7\ 2)
  • sr^2 \mapsto (1\ 6)(3\ 8)(5\ 2)(7\ 4)
  • sr^3 \mapsto (1\ 8)(3\ 2)(5\ 4)(7\ 6).

It is easy to see that these two subgroups are different.

Exhibit Sym(3) as a subgroup of Sym(6) via the left regular representation

List the elements of S_3 as 1, (1\ 2), (2\ 3), (1\ 3), (1\ 2\ 3), (1\ 3\ 2) and label these with the integers 1,2,3,4,5,6, respectively. Exhibit the image of each element of S_3 under the left regular representation of S_3 into S_6.


We use the notation \sigma(k) = \sigma \cdot k.

  1. 1 \mapsto 1
  2. We have (1\ 2)(1) = (1\ 2) = 2, (1\ 2)(2) = (1\ 2)(1\ 2) = 1, (1\ 2)(3) = (1\ 2)(2\ 3) = (1\ 2\ 3) = 5, (1\ 2)(4) = (1\ 2)(1\ 3) = (1\ 3\ 2) = 6, (1\ 2)(5) = (1\ 2)(1\ 2\ 3) = (2\ 3) = 3, and (1\ 2)(6) = (1\ 2)(1\ 3\ 2) = (1\ 3) = 4. Thus (1\ 2) \mapsto (1\ 2)(3\ 5)(4\ 6).
  3. We have (2\ 3)(1) = (2\ 3) = 3, (2\ 3)(2) = (2\ 3)(1\ 2) = (1\ 3\ 2) = 6, (2\ 3)(3) = (2\ 3)(2\ 3) = 1, (2\ 3)(4) = (2\ 3)(1\ 3) = (1\ 2\ 3) = 5, (2\ 3)(5) = (2\ 3)(1\ 2\ 3) = (1\ 3) = 4, and (2\ 3)(6) = (2\ 3)(1\ 3\ 2) = (1\ 2) = 2. Thus (2\ 3) \mapsto (1\ 3)(2\ 6)(4\ 5).
  4. We have (1\ 3)(1) = (1\ 3) = 4, (1\ 3)(2) = (1\ 3)(1\ 2) = (1\ 2\ 3) = 5, (1\ 3)(3) = (1\ 3)(2\ 3) = (1\ 3\ 2) = 6, (1\ 3)(4) = (1\ 3)(1\ 3) = 1, (1\ 3)(5) = (1\ 3)(1\ 2\ 3) = (1\ 2) = 2, and (1\ 3)(6) = (1\ 3)(1\ 3\ 2) = (2\ 3) = 3. Thus (1\ 3) \mapsto (1\ 4)(2\ 5)(3\ 6).
  5. We have (1\ 2\ 3)(1) = (1\ 2\ 3) = 5, (1\ 2\ 3)(2) = (1\ 2\ 3)(1\ 2) = (1\ 3) = 4, (1\ 2\ 3)(3) = (1\ 2\ 3)(2\ 3) = (1\ 2) = 2, (1\ 2\ 3)(4) = (1\ 2\ 3)(1\ 3) = (2\ 3) = 3, (1\ 2\ 3)(5) = (1\ 2\ 3)(1\ 2\ 3) = (1\ 3\ 2) = 6, and (1\ 2\ 3)(6) = (1\ 2\ 3)(1\ 3\ 2) = 1. Thus (1\ 2\ 3) \mapsto (1\ 5\ 6)(2\ 4\ 3).
  6. We have (1\ 3\ 2)(1) = (1\ 3\ 2) = 6, (1\ 3\ 2)(2) = (1\ 3\ 2)(1\ 2) = (2\ 3) = 3, (1\ 3\ 2)(3) = (1\ 3\ 2)(2\ 3) = (1\ 3) = 4, (1\ 3\ 2)(4) = (1\ 3\ 2)(1\ 3) = (1\ 2) = 2, (1\ 3\ 2)(5) = (1\ 3\ 2)(1\ 2\ 3) = 1, and (1\ 3\ 2)(6) = (1\ 3\ 2)(1\ 3\ 2) = (1\ 2\ 3) = 5. Thus (1\ 3\ 2) \mapsto (1\ 6\ 5)(2\ 3\ 4).

Exhibit the Klein 4-group as a subgroup of Sym(4) using the left regular representation

Let G = \{1,a,b,c\} be the Klein 4-group.

  1. Label the elements 1,a,b,c with the integers 1,2,4,3, respectively, and prove that under the left regular representation of G into S_4 the nonidentity elements are mapped as follows: a \mapsto (1\ 2)(3\ 4), b \mapsto (1\ 4)(2\ 3), and c \mapsto (1\ 3)(2\ 4).
  2. Relabel the elements 1,a,b,c as 1,4,2,3, respectively, and compute the image of each element of G under the left regular representation of G into S_4. Show that the image of G under this labelling is the same subgroup of S_4 (even though the individual elements map differently.)

The multiplication table for G is as follows.

1 a b c
1 1 a b c
a a 1 c b
b b c 1 a
c c b a 1

We can see that with 1,a,b,c labelled as 1,2,4,3, respectively, since a1 = a, aa = 1, ab = c, and ac = b we have a(1) = 2, a(2) = 1, a(3) = 4, and a(4) = 3. Thus a \mapsto (1\ 2)(3\ 4).

Similarly, b1 = b, ba = c, bb = 1, and bc = a, so that b \mapsto (1\ 4)(2\ 3). Likewise c \mapsto (1\ 3)(2\ 4).

Now we relabel the elements 1,a,b,c as 1,4,2,3, respectively. Now a(1) = a1 = a = 4, a(2) = ab = c = 3, a(3) = ac = b = 2, and a(4) = aa = 1. Thus a \mapsto (1\ 4)(2\ 3). Now b(1) = b = 2, b(2) = bb = 1, b(3) = bc = a = 4, and b(4) = ba = c = 3, so that b \mapsto (1\ 2)(3\ 4), and c(1) = c = 3, c(2) = cb = a = 4, c(3) = cc = 1, and c(4) = ca = b = 2, so that c \mapsto (1\ 3)(2\ 4). Clearly this is the same subgroup as the image of G under the first labelling.

Facts about double cosets

Let G be a group and H,K \leq G subgroups. For each x \in G, define the (H,K) double coset of x by HxK = \{ hxk \ |\ h \in H, k \in K \}.

  1. Prove that HxK is the union of the left cosets x_iK where x_iK \in H \cdot xK.
  2. Prove (as above) that HxK is a union of right cosets of H.
  3. Show that the set of (H,K) double cosets partitions G.
  4. Prove that |HxK| = |K| \cdot [H : H \cap xKx^{-1}].
  5. Prove that |HxK| = |H| \cdot [K : K \cap x^{-1}Hx].

  1. (\subseteq) Let hxk \in HxK. Now hxK = h \cdot xK \in H \cdot xK and hxk \in hxK. Thus hxk \in \bigcup_{yK \in H \cdot xK} yK.

    (\supseteq) Let g \in \bigcup_{yK \in H \cdot xK} yK. Then g \in yK for some yK \in H \cdot xK, so that yK = h \cdot xK = hxK for some h \in H. Then g = hxk for some k \in K. So g \in HxK.

  2. (\subseteq) Let hxk \in HxK. Now Hxk = Hx \cdot k \in Hx \cdot K and hxk \in Hxk. Thus hxk \in \bigcup_{Hy \in Hx \cdot K} Hy.

    (\supseteq) Let g \in \bigcup_{Hy \in Hx \cdot K} Hy. Then g \in Hy for some Hy \in Hx \cdot K, so that Hy = Hx \cdot k = Hxk for some k \in K. Then g = hxk for some h \in H. So g \in HxK.

  3. Note that every element is in some double coset- in particular, x \in HxK for all x \in G. So G = \bigcup_{x \in G} HxK.

    Note that if y \in HxK, then HyK \subseteq HxK.

    Now suppose x,y \in G such that HxK \cap HyK \neq \emptyset. Then we have h_1xk_1 = h_2yk_2 for some h_i \in H and k_i \in K. Then x = h_1^{-1}h_2yk_2k_1^{-1} \in HyK, so that HxK \subseteq HyK. Similarly HyK \subseteq HxK. Thus two double cosets are either disjoint or equal. Thus the (H,K) double cosets form a partition of G.

  4. First we prove a lemma.

    Lemma 1: \mathsf{stab}_H(xK) = H \cap xKx^{-1}. Proof: (\subseteq) Suppose h \in \mathsf{stab}_H(xK). Then hxK = h \cdot xK = xK, and we have x^{-1}hx \in K. So h \in xKx^{-1}, hence h \in H \cap xKx^{-1}. (\supseteq) Suppose h \in H \cap xKx^{-1}. Then x^{-1}hx \in K, so that h \cdot xK = hxK = xK, thus h \in \mathsf{stab}_H(xK). \square

    We saw in part 1 above that HxK = \bigcup_{yK \in H \cdot xK} yK; moreover, this union is disjoint because the yK are distinct left cosets of K, each of order |K|. Thus |HxK| = |K| \cdot |H \cdot xK| = |K| \cdot [H : \mathsf{stab}_H(xK)] = |K| \cdot [H : H \cap xKx^{-1}], using Lemma 1.

  5. First we prove a lemma.

    Lemma 2: \mathsf{stab}_K(Hx) = K \cap x^{-1}Hx. Proof: (\subseteq) Suppose k \in \mathsf{stab}_K(Hx). Then Hxk = Hx \cdot k = Hx, and we have xkx^{-1} \in H. So k \in x^{-1}Hx, hence k \in K \cap x^{-1}Hx. (\supseteq) Suppose k \in K \cap x^{-1}Hx. Then xkx^{-1} \in H, so that Hx \cdot k = Hxk = Hx, thus k \in \mathsf{stab}_K(Hx). \square

    We saw in part 2 above that HxK = \bigcup_{Hy \in Hx \cdot K} Hy; moreover, this union is disjoint. Thus |HxK| = |H| \cdot |Hx \cdot K| = |H| \cdot [K : \mathsf{stab}_K(Hx)] = |K| \cdot [K : K \cap x^{-1}Hx].

Transitive group actions induce transitive actions on the orbits of the action of a subgroup

Suppose G \leq S_A acts transitively on A and let H \leq G be normal. Let O_1, O_2, \ldots, O_r be the distinct orbits of H on A.

  1. Prove that G permutes the sets O_k in the sense that for each g \in G and each i \in \{1,2,\ldots,r\} there exists a j such that g \cdot O_i = O_j. Prove that G is transitive on \{ O_1,O_2,\ldots,O_r \}. Deduce that all orbits of H on A have the same cardinality.
  2. Prove that if a \in O_1 then |O_1| = [H : H \cap \mathsf{stab}_G(a)] and that r = [G : H \mathsf{stab}_G(a)]. [Hint: Note that H \cap \mathsf{stab}_G(a) = \mathsf{stab}_H(a) and use the Second Isomorphism Theorem.]

  1. Let g \in G and a \in A. Now H \cdot a is an arbitrary orbit of H on A. Moreover, g \cdot a = b for some b \in A. Then g \cdot (H \cdot a) = gH \cdot a = Hg \cdot a = H \cdot (g \cdot a) = H \cdot b, since H is normal. Thus G permutes the orbits \{ H \cdot a \ |\ a \in A \}.

    Now let a,b \in A be arbitrary; since the action of G on A is transitive, there exists g \in G such that g \cdot a = b. Then g \cdot (H \cdot a) = gH \cdot a = Hg \cdot a = H \cdot (g \cdot a) = H \cdot b; thus the action of G on the orbits \{ H \cdot a \ |\ a \in A \} is transitive.

    Let a,b \in A be arbitrary, and let g \in G such that g \cdot a = b. Because H is normal, for every h \in H there exists a unique k \in H such that gh = kg. We have a mapping \varphi_g : H \cdot a \rightarrow H \cdot b given by \varphi_g(h \cdot a) = k \cdot b. Because gH = Hg, this mapping \varphi_g is bijective, and |H \cdot a| = |H \cdot b|. Because the action of G is transitive on the orbits, all orbits have the same cardinality.

  2. Let a \in A. We can restrict the action of G on the orbits of H to H; with this action we have |H \cdot a| = [H : \mathsf{stab}_H(a)]. Clearly \mathsf{stab}_H(a) = H \cap \mathsf{stab}_G(a); thus |H \cdot a| = [H : H \cap \mathsf{stab}_G(a)]. Considering now the (transitive) action of G on the orbits of H, we have r = |\{ H \cdot a \ |\ a \in A \}| = [G : \mathsf{stab}_G(H \cdot a)].

    We claim that \mathsf{stab}_G(H \cdot a) = H \mathsf{stab}_G(a). Proof of claim: Suppose g \in \mathsf{stab}_G(H \cdot a). Now Hg \cdot a = gH \cdot a = g \cdot (H \cdot a) = H \cdot a, so that in particular g \cdot a = h \cdot a for some h \in H. Then h^{-1}g \cdot a = a, so that h^{-1}g \in \mathsf{stab}_G(a). Thus g \in H \mathsf{stab}_G(a). Now suppose g \in H \mathsf{stab}_G(a). Then g = hx for some h \in H and x \in \mathsf{stab}_G(a). Now g \cdot (H \cdot a) = gH \cdot a = Hg \cdot a = Hhx \cdot a = H \cdot a, so that g \in \mathsf{stab}_G(H \cdot a). Thus r = [G : H \mathsf{stab}_G(a)].

Every doubly transitive group action is primitive

A transitive permutation group G \leq S_A acting on A is called doubly transitive if for all a \in A, the subgroup \mathsf{stab}(a) is transitive on A \setminus \{a\}.

  1. Prove that S_n is doubly transitive on \{1,2,\ldots,n\} for all n \geq 2.
  2. Prove that a doubly transitive group is primitive. Deduce that D_8 is not doubly transitive in its action on the four vertices of a square.

  1. We know that S_n is transitive on A = \{1,2,\ldots,n\}. Now if n \geq 2 and k \in A, we have a natural isomorphism \mathsf{stab}(k) \cong S_{A \setminus \{k\}}; this permutation group is also transitive in its action on A \setminus \{k\}. Thus S_n is doubly transitive.
  2. Let G \leq S_A act transitively on A, and suppose further that the action is doubly transitive. Let B \subseteq A be a proper block; then there exist elements b \in B and a \in A \setminus B. By a previous exercise, we have \mathsf{stab}(b) \leq \mathsf{stab}(B). Thus if \sigma \in \mathsf{stab}(b), we have \sigma[B] = B. Suppose now that there exists an element c \in B with c \neq b. Because G is doubly transitive on A, there exists an element \tau \in \mathsf{stab}(b) such that \tau(c) = a. Thus \tau[B] \neq B, a contradiction. So no such element c exists and we have B = \{b\}. Now every block is trivial, thus the action of G on A is primitive.

    We saw that the action of D_8 on the four vertices of a square is not primitive in the previous exercise. Thus this action is not doubly transitive.

Basic properties of blocks of a group action

Let G \leq S_A act transitively on the set A. A block is a nonempty subset B \subseteq A such that for all \sigma \in G either \sigma[B] = B or \sigma[B] \cap B = \emptyset.

  1. Prove that if B is a block containing a \in A and we define \mathsf{stab}(B) = \{ \sigma \in G \ |\ \sigma[B] = B \} then \mathsf{stab}(a) \leq \mathsf{stab}(B) \leq G.
  2. Prove that if B is a block then \mathcal{B} = \{ \sigma[B] \ |\ \sigma \in G \} is a partition of A.
  3. A (transitive) group G \leq S_A is called primitive if the only blocks in A are the trivial ones- the singletons and A itself. Prove that S_4 is primitive on A = \{1,2,3,4\}. Prove that D_8 is not primitive as a permutation group on the four vertices of a square.
  4. Let G \leq S_A act transitively on A. Prove that G is primitive on A if and only if for all a \in A, \mathsf{stab}(a) is maximal in G.

  1. Note that \mathsf{stab}(B) is not empty since 1[B] = B. Now let \sigma, \tau \in \mathsf{stab}(B). Note that \tau^{-1}[B] = \tau^{-1}\tau [B] = B, so that \sigma\tau^{-1}[B] = B. Thus \sigma\tau^{-1} \in \mathsf{stab}(B). By the subgroup criterion, \mathsf{stab}(B) \leq G.

    Now suppose \sigma \in \mathsf{stab}(a). We have \sigma(a) = a, so that \{a\} \subseteq \sigma[B] \cap B. Hence \sigma[B] \cap B is nonempty, and we have \sigma[B] = B since B is a block. Thus \sigma \in \mathsf{stab}(B). By a previous exercise, \mathsf{stab}(a) \leq \mathsf{stab}(B).

  2. First we show that \bigcup_{\sigma \in G} \sigma[B] = A. The (\subseteq) direction is clear. (\supseteq): Let a \in A and b \in B. Since the action of G is transitive, there exists \sigma \in G such that a = \sigma(b). Then a \in \sigma[B], so that aA \subseteq \bigcup_{\sigma \in G} \sigma[B].

    Now suppose \sigma[B] \cap \tau[B] \neq \emptyset. Then there exist a,b \in B such that \sigma(a) = \tau(b). Now a = \sigma^{-1}\tau \cdot b, so that \sigma^{-1}\tau[B] \cap B is not empty. Thus \sigma^{-1}\tau[B] = B, and we have \sigma[B] = \tau[B]. So elements of \mathcal{B} are pairwise disjoint; hence \mathcal{B} is a partition of A.

    1. Let B \subseteq A = \{1,2,3,4\} be a proper nonempty subset. Then there exist elements x \in B and y \in A \setminus B. Suppose B is a block. Consider \sigma = (x\ y) \in S_4; since \sigma(x) \notin B, we have \sigma[B] \cap B = \emptyset. Let w and z be the remaining elements of A. If w \in B, then w \in \sigma[B] \cap B, a contradiction; similarly for z. Thus B = \{x\}. Now clearly A itself is a block, and any proper block must be a singleton. Thus this action of S_4 is primitive.
    2. We saw previously that D_8 \cong \langle (1\ 3), (1\ 2\ 3\ 4) \rangle, where A = \{1,2,3,4\} are labels on the vertices of a square (written clockwise). Consider the set \{1,3\}. We see that
      1. 1 \cdot \{1,3\} = \{1,3\}
      2. (1\ 2\ 3\ 4) \cdot \{1,3\} = \{2,4\}
      3. (1\ 3)(2\ 4) \cdot \{1,3\} = \{1,3\}
      4. (1\ 4\ 3\ 2) \cdot \{1,3\} = \{2,4\}
      5. (1\ 3) \cdot \{1,3\} = \{1,3\}
      6. (1\ 2)(3\ 4) \cdot \{1,3\} = \{2,4\}
      7. (2\ 4) \cdot \{1,3\} = \{1,3\}
      8. (1\ 4)(2\ 3) \cdot \{1,3\} = \{2,4\}

      So that \{1,3\} is a nontrivial block; hence this action is not primitive.

  3. We begin with some lemmas.

    Lemma 1: Let G \leq S_A act transitively on A and let B \subseteq A be a block under the action. Then \mathsf{stab}(B) = G if and only if B = A. Proof: The (\Leftarrow) direction is clear. (\Rightarrow) Suppose B is a proper subset and let x \in B, y \in A \setminus B. Now y \in (x\ y)[B] and y \notin B, so that (x\ y)[B] \neq B. Since B is a block, we have (x\ y)[B] \cap B = \emptyset. But x \in (x\ y)[B] \cap B since x \in B and y \notin B, a contradiction. So B is not proper, and we have A = B. \square

    Now we move to the main result.

    (\Rightarrow) Suppose G is primitive on A; then the only blocks of A are A and the singletons. Now let a \in A and let H \leq G be a subgroup with \mathsf{stab}(a) \leq H \leq G. We consider the set H \cdot a = \{ h \cdot a \ |\ h \in H \}.

    We claim that H \cdot a is a block. Proof of claim: H \cdot a is not empty since a = 1 \cdot a \in H \cdot a. Now let \sigma \in G. If \sigma \in H, then \sigma \cdot (H \cdot a) = \sigma H \cdot a = H \cdot a. If \sigma \notin H, then \sigma \cdot (H \cdot a) = \sigma H \cdot a. Suppose that \sigma H \cdot a \cap H \cdot a \neq \emptyset; say that \sigma\tau_1 \cdot a = \tau_2 \cdot a for some \tau_1, \tau_2 \in H. Then \tau_2^{-1} \sigma \tau_1 \cdot a = a, so that \tau_2^{-1} \sigma \tau_1 \in \mathsf{stab}(a) \leq H. But then \sigma \in \tau_2H\tau_1^{-1} = H, a contradiction. Thus if \sigma \notin H, then \sigma[H \cdot a] \cap H \cdot a = \emptyset. Hence H \cdot a is a block.

    Next we claim that \mathsf{stab}(H \cdot a) = H. Proof of claim: (\supseteq) If \tau \in H, then \tau \cdot (H \cdot a) = \tau H \cdot a = H \cdot a. (\subseteq) Suppose \sigma \cdot (H \cdot a) = \sigma H \cdot a = H \cdot a. Then \sigma \cdot a = \tau \cdot a for some \tau \in H, hence \tau^{-1} \sigma \cdot a = a. Then \tau^{-1} \sigma \in \mathsf{stab}(a) \leq H, so that \sigma \in H.

    Since G is primitive on a and a \in H \cdot a, we have H \cdot a = \{a\} or H \cdot a = A. If H \cdot a = \{a\}, we have H \leq \mathsf{stab}(a), so that H = \mathsf{stab}(a). If H \cdot a = A, we have H = \mathsf{stab}(H \cdot a) = \mathsf{stab}(A) = G. Thus \mathsf{stab}(a) is a maximal subgroup of G.

    (\Leftarrow) Suppose that for all a \in A, \mathsf{stab}(a) is a maximal subgroup in G. Let B \subseteq A be a block with a \in B. Now \mathsf{stab}(a) \leq \mathsf{stab}(B) \leq G by part 1 above. Since \mathsf{stab}(a) is maximal, there are two cases.

    If \mathsf{stab}(B) = \mathsf{stab}(a) and b \in B such that b \neq a, then since G acts transitively there exists \sigma \in G such that \sigma \cdot a = b. Now \sigma \in \mathsf{stab}(B) = \mathsf{stab}(a), a contradiction. Thus B = \{a\}.

    If \mathsf{stab}(B) = G, then by Lemma 1 we have B = A.

    Thus G is primitive on A.

Compute some orbits of an action by Sym(4) on polynomials in four variables

As in this previous exercise, let S_4 act on the set R of all polynomials with integer coefficients in the independent variables x_1,x_2,x_3,x_4 by permuting the indices: \sigma \cdot p(x_1,x_2,x_3,x_4) = p(x_{\sigma(1)}, x_{\sigma(2)}, x_{\sigma(3)}, x_{\sigma(4)}).

  1. Find the polynomials in the orbit of x_1 + x_2. (Recall from a previous exercise that the stabilizer of this element has order 4.)
  2. Find the polynomials in the orbit of x_1x_2 + x_3x_4. (Recall that the stabilizer of this element has order 8.)
  3. Find the polynomials in the orbit of (x_1 + x_2)(x_3 + x_4).

  1. We have [S_4 : \mathsf{stab}(x_1+x_2)] = 6. A simple calculation then shows that this orbit is \{ x_1+x_2, x_1+x_3, x_1+x_4, x_2+x_3, x_2+x_4, x_3+x_4 \}.
  2. We have [S_4 : \mathsf{stab}(x_1x_2 + x_3x_4)] = 3. A simple calculation then shows that this orbit is \{ x_1x_2+x_3x_4, x_1x_3+x_2x_4, x_1x_4+x_2x_3 \}.
  3. We saw in a previous exercise that \mathsf{stab}((x_1+x_2)(x_3+x_4)) = \mathsf{stab}(x_1x_2+x_3x_4). Thus [S_4 : \mathsf{stab}((x_1+x_2)(x_3+x_4))] = 3. A simple calculation then shows that this orbit is \{ (x_1+x_2)(x_3+x_4), (x_1+x_3)(x_2+x_4), (x_1+x_4)(x_2+x_3) \}.

Compute the orbits, cycle decompositions, and stabilizers of some group actions of Sym(3)

Repeat the previous example with each of the following actions.

  1. S_3 acting on the set A = \{ (i,j,k) \ |\ 1 \leq i,j,k \leq 3 \} by \sigma \cdot (i,j,k) = (\sigma(i), \sigma(j), \sigma(k))
  2. S_3 acting on the set B of all nonempty subsets of \{1,2,3\} by \sigma \cdot X = \sigma[X].

  • For S_3 acting on A:
    • We compute the orbits as follows.
      • 1 \cdot (1,1,1) = (2\ 3) \cdot (1,1,1) = (1,1,1), (1\ 2) \cdot (1,1,1) = (1\ 2\ 3) \cdot (1,1,1) = (2,2,2), and (1\ 3) \cdot (1,1,1) = (1\ 3\ 2) \cdot (1,1,1) = (3,3,3), so that \mathcal{O}_1 = \{ (1,1,1), (2,2,2), (3,3,3) \}.
      • 1 \cdot (1,1,2) = (1,1,2), (1\ 2) \cdot (1,1,2) = (2,2,1), (1\ 3) \cdot (1,1,2) = (3,3,2), (2\ 3) \cdot (1,1,2) = (1,1,3), (1\ 2\ 3) \cdot (1,1,2) = (2,2,3) and (1\ 3\ 2) \cdot (1,1,2) = (3,3,1), so that \mathcal{O}_2 = \{ (1,1,2), (2,2,1), (3,3,2), (1,1,3), (2,2,3), (3,3,1) \}.
      • 1 \cdot (1,2,1) = (1,2,1), (1\ 2) \cdot (1,2,1) = (2,1,2), (2\ 3) \cdot (1,2,1) = (1,3,1), (1\ 2\ 3) \cdot (1,2,1) = (2,3,2), and (1\ 3\ 2) \cdot (1,2,1) = (3,1,3), so that \mathcal{O}_3 = \{ (1,2,1), (2,1,2), (3,2,3), (1,3,1), (2,3,2), (3,1,3) \}.
      • 1 \cdot (2,1,1) = (2,1,1), (1\ 2) \cdot (2,1,1) = (1,2,2), (1\ 3) \cdot (2,1,1) = (2,3,3), (2\ 3) \cdot (2,1,1) = (3,1,1), (1\ 2\ 3) \cdot (2,1,1) = (3,2,2), and (1\ 3\ 2) \cdot (2,1,1) = (1,3,3), so that \mathcal{O}_4 = \{ (2,1,1), (1,2,2), (2,3,3), (3,1,1), (3,2,2), (1,3,3) \}.
      • 1 \cdot (1,2,3) = (1,2,3), (1\ 2) \cdot (1,2,3) = (2,1,3), (1\ 3) \cdot (1,2,3) = (3,2,1), (2\ 3) \cdot (1,2,3) = (1,3,2), (1\ 2\ 3) \cdot (1,2,3) = (2,3,1), and (1\ 3\ 2) \cdot (1,2,3) = (3,1,2), so that \mathcal{O}_5 = \{ (1,2,3), (2,1,3), (3,2,1), (1,3,2), (2,3,1), (3,1,2) \}.

      This exhausts the elements of A.

    • We fix the labeling
      \alpha_{1} = (1,1,1) \alpha_{10} = (2,1,1) \alpha_{19} = (3,1,1)
      \alpha_{2} = (1,1,2) \alpha_{11} = (2,1,2) \alpha_{20} = (3,1,2)
      \alpha_{3} = (1,1,3) \alpha_{12} = (2,1,3) \alpha_{21} = (3,1,3)
      \alpha_{4} = (1,2,1) \alpha_{13} = (2,2,1) \alpha_{22} = (3,2,1)
      \alpha_{5} = (1,2,2) \alpha_{14} = (2,2,2) \alpha_{23} = (3,2,2)
      \alpha_{6} = (1,2,3) \alpha_{15} = (2,2,3) \alpha_{24} = (3,2,3)
      \alpha_{7} = (1,3,1) \alpha_{16} = (2,3,1) \alpha_{25} = (3,3,1)
      \alpha_{8} = (1,3,2) \alpha_{17} = (2,3,2) \alpha_{26} = (3,3,2)
      \alpha_{9} = (1,3,3) \alpha_{18} = (2,3,3) \alpha_{27} = (3,3,3).

      Now under the permutation representation S_3 \rightarrow S_{27}, we have

      • 1 \mapsto 1
      • (1\ 2) \mapsto (\alpha_1\ \alpha_{14}) (\alpha_2\ \alpha_{13}) (\alpha_3\ \alpha_{15}) (\alpha_4\ \alpha_{11}) (\alpha_5\ \alpha_{10}) (\alpha_6\ \alpha_{12}) (\alpha_7\ \alpha_{17}) (\alpha_8\ \alpha_{16}) (\alpha_9\ \alpha_{18}) (\alpha_{19}\ \alpha_{23}) (\alpha_{20}\ \alpha_{22}) (\alpha_{21}\ \alpha_{24}) (\alpha_{25}\ \alpha_{26})
      • (1\ 3) \mapsto (\alpha_1\ \alpha_{27}) (\alpha_2\ \alpha_{26}) (\alpha_3\ \alpha_{25}) (\alpha_4\ \alpha_{24}) (\alpha_5\ \alpha_{23}) (\alpha_6\ \alpha_{22}) (\alpha_7\ \alpha_{21}) (\alpha_8\ \alpha_{20}) (\alpha_9\ \alpha_{19}) (\alpha_{10}\ \alpha_{18}) (\alpha_{11}\ \alpha_{17}) (\alpha_{12}\ \alpha_{16}) (\alpha_{13}\ \alpha_{15})
      • (2\ 3) \mapsto (\alpha_2\ \alpha_3) (\alpha_4\ \alpha_7) (\alpha_5\ \alpha_{9}) (\alpha_6\ \alpha_{8}) (\alpha_{10}\ \alpha_{19}) (\alpha_{11}\ \alpha_{21}) (\alpha_{12}\ \alpha_{20}) (\alpha_{13}\ \alpha_{25}) (\alpha_{14}\ \alpha_{27}) \alpha_{15}\ \alpha_{26}) (\alpha_{16}\ \alpha_{22}) (\alpha_{17}\ \alpha_{24}) (\alpha_{18}\ \alpha_{23})
      • (1\ 2\ 3) \mapsto (\alpha_1\ \alpha_{14}\ \alpha_{27}) (\alpha_2\ \alpha_{15}\ \alpha_{25}) (\alpha_3\ \alpha_{13}\ \alpha_{26}) (\alpha_{4}\ \alpha_{17}\ \alpha_{21}) (\alpha_5\ \alpha_{18}\ \alpha_{19}) (\alpha_6\ \alpha_{16}\ \alpha_{20}) (\alpha_7\ \alpha_{11}\ \alpha_{24}) (\alpha_8\ \alpha_{12}\ \alpha_{22}) (\alpha_9\ \alpha_{10}\ \alpha_{23})
      • (1\ 3\ 2) \mapsto (\alpha_1\ \alpha_{27}\ \alpha_{14}) (\alpha_2\ \alpha_{25}\ \alpha_{15}) (\alpha_3\ \alpha_{26}\ \alpha_{13}) (\alpha_{4}\ \alpha_{21}\ \alpha_{17}) (\alpha_5\ \alpha_{19}\ \alpha_{18}) (\alpha_6\ \alpha_{20}\ \alpha_{16}) (\alpha_7\ \alpha_{24}\ \alpha_{11}) (\alpha_8\ \alpha_{22}\ \alpha_{12}) (\alpha_9\ \alpha_{23}\ \alpha_{10})
    • If x \in \mathcal{O}_1, then [S_3 : \mathsf{stab}(x)] = 3 so that |\mathsf{stab}(x)| = 2. In particular, consider (3,3,3) \in \mathcal{O}_1. Since (1\ 2) \cdot (3,3,3) = (3,3,3), we have \mathsf{stab}((3,3,3)) = \langle (1\ 2) \rangle.

      Each remaining orbit has order 6. Thus, if x \in \mathcal{O}_k, 2 \leq k \leq 5, then |\mathsf{stab}(x)| = 1; hence \mathsf{stab}(x) = 1.

  • For S_3 acting on B:
    • We compute the orbits as follows.
      • We have 1 \cdot \{1\} = (2\ 3) \cdot \{1\} = \{1\}, (1\ 2) \cdot \{1\} = (1\ 2\ 3) \cdot \{1\} = \{2\}, and (1\ 3) \cdot \{1\} = (1\ 3\ 2) \cdot \{1\} = \{3\}. Thus \mathcal{O}_1 = \{ \{1\}, \{2\}, \{3\} \}.
      • We have 1 \cdot \{1,2\} = (1\ 2) \cdot \{1,2\} = \{1,2\}, (1\ 3) \cdot \{1,2\} = (1\ 2\ 3) \cdot \{1,2\} = \{2,3\}, and (2\ 3) \cdot \{1,2\} = (1\ 3\ 2) \cdot \{1,2\} = \{1,3\}. Thus \mathcal{O}_2 = \{ \{1,2\}, \{1,3\}, \{2,3\} \}.
      • There is only one remaining element of B. Thus \mathcal{O}_3 = \{ \{1,2,3\} \}.
    • We fix the labeling
      \alpha_{1} = \{1\} \alpha_{5} = \{1,3\}
      \alpha_{2} = \{2\} \alpha_{6} = \{2,3\}
      \alpha_{3} = \{3\} \alpha_{7} = \{1,2,3\}
      \alpha_{4} = \{1,2\}

      Under the permutation representation S_3 \rightarrow S_7,

      • 1 \mapsto 1
      • (1\ 2) \mapsto (\alpha_1\ \alpha_2)(\alpha_5\ \alpha_6)
      • (1\ 3) \mapsto (\alpha_1\ \alpha_3)(\alpha_4\ \alpha_6)
      • (2\ 3) \mapsto (\alpha_2\ \alpha_3)(\alpha_4\ \alpha_5)
      • (1\ 2\ 3) \mapsto (\alpha_1\ \alpha_2\ \alpha_3)(\alpha_4\ \alpha_6\ \alpha_5)
      • (1\ 3\ 2) \mapsto (\alpha_1\ \alpha_3\ \alpha_2)(\alpha_4\ \alpha_5\ \alpha_6)
    • If x \in \mathcal{O}_1, then [S_3 : \mathsf{stab}(x)] = 3, so that |\mathsf{stab}(x)| = 2. In particular, since (2\ 3) \cdot \{1\} = \{1\}, we have \mathsf{stab}(\{1\}) = \langle (2\ 3) \rangle.

      If x \in \mathcal{O}_2, we similarly have |\mathsf{stab}(x)| = 2. In particular, since (2\ 3) \cdot \{2,3\} = \{2,3\}, we have \mathsf{stab}(\{2,3\}) = \langle (2\ 3) \rangle.

      Now [S_3 : \mathsf{stab}(\{1,2,3\})] = 1, so that \mathsf{stab}(\{1,2,3\}) = S_3.