Tag Archives: cycle notation

Alt(n) is generated by the set of all 3-cycles

Prove that A_n is generated by the set of all 3-cycles for n \geq 3.


Let n \geq 3 and let T = \{ (a\ b\ c) \ |\ 1 \leq a,b,c \leq n \} be the set of 3-cycles in A_n.

Note that A_n contains T, so that \langle T \rangle \leq A_n.

Recall that A_n consists of all permutations which can be written as an even product of transpositions; more specifically, A_n is generated by the set of all products of two distinct 2-cycles. (Here we use the fact that n \geq 3.) Each product \sigma of two 2-cycles has one of two forms.

If \sigma = (a\ b)(c\ d), note that \sigma = (a\ c\ b)(a\ c\ d).

If \sigma = (a\ b)(a\ c), note that \sigma = (a\ c\ b).

Thus A_n \leq \langle T \rangle, hence A_n = \langle T \rangle.

Compute the size of each conjugacy class in Sym(n)

This exercise gives a formula for the size of each conjugacy class in S_n. Let \sigma be a permutation in S_n and let m_1,m_2,\ldots,m_s be the distinct integers which appear in the cycle shape of \sigma (including 1-cycles). Let k_1,k_2,\ldots,k_s be the multiplicity of each m_i in the cycle shape of \sigma. (That is, \sum_{i=1}^s k_im_i = n.) Prove that the number of conjugates of \sigma is n!/(\prod_{i=1}^s k_i! m_i^{k_i}).


The conjugates of \sigma are precisely those permutations having the same cycle type. There are n! different ways we can “fill in” a permutation having the same cycle shape as \sigma. In doing so, we overcount due to two factors: each cycle of length m_i can be cyclically permuted m_i times and the cycles of length m_i can be permuted among themselves (with k_i! ways to do this for each i) without changing the permutation.

For odd n, the n-cycles in Alt(n) comprise two conjugacy classes of equal size

Prove that if n is odd then the set of all n-cycles consists of two conjugacy classes of equal size in A_n.


Let n be an odd positive integer. Then any n-cycle is an even permutation, so that the set (hence conjugacy class) K \subseteq S_n consisting of all n-cycles is contained in A_n. Note that the cycle type of any \sigma \in K is n; that is, the cycle type of \sigma consists of distinct odd integers. Thus, by this previous exercise, K consists of two A_n-conjugacy classes of equal size.

Find conjugators in Sym(5)

Let \sigma = (1\ 2\ 3\ 4\ 5) \in S_5. Find an element \tau that satisfies each of the following equations: (1) \tau\sigma\tau^{-1} = \sigma^2, (2) \tau\sigma\tau^{-1} = \sigma^{-1}, and (3) \tau\sigma\tau^{-1} = \sigma^{-2}.


  1. If \tau = (2\ 3\ 5\ 4), then \tau\sigma\tau^{-1} = (2\ 3\ 5\ 4)(1\ 2\ 3\ 4\ 5)(2\ 4\ 5\ 3) = (1\ 3\ 5\ 2\ 4) = \sigma^2.
  2. If \tau = (2\ 5)(3\ 4), then \tau\sigma\tau^{-1} = (2\ 5)(3\ 4)(1\ 2\ 3\ 4\ 5)(2\ 5)(3\ 4) = (1\ 5\ 4\ 3\ 2) = \sigma^{-1}.
  3. If \tau = (2\ 4\ 5\ 3), then \tau\sigma\tau^{-1} = (2\ 4\ 5\ 3)(1\ 2\ 3\ 4\ 5)(2\ 3\ 5\ 4) = (1\ 4\ 2\ 5\ 3) = \sigma^{-2}.

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.

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

Let S_3 act on the set A = \{ (i,j) \ |\ 1 \leq i,j \leq 3 \} by \sigma \cdot (i,j) = (\sigma(i), \sigma(j)).

  1. Find the orbits of S_3 on A.
  2. Fix a labeling of the elements of A. For each \sigma \in S_3, find the cycle decomposition of \sigma under the permutation representation S_3 \rightarrow S_9.
  3. For each orbit \mathcal{O} of this action, choose some a \in \mathcal{O} and compute \mathsf{stab}(a).

  1. We have 1 \cdot (1,1) = (2\ 3) \cdot (1,1) = (1,1), (1\ 2) \cdot (1,1) = (1\ 2\ 3) \cdot (1,1) = (2,2), and (1\ 3) \cdot (1,1) = (1\ 3\ 2) \cdot (1,1) = (3,3). Thus the orbit containing (1,1) is \mathcal{O}_1 = \{ (1,1), (2,2), (3,3) \}.

    We also have 1 \cdot (1,2) = (1,2), (1\ 2) \cdot (1,2) = (2,1), (1\ 3) \cdot (1,2) = 3,2), (2\ 3) \cdot (1,2) = (1,3), (1\ 2\ 3) \cdot (1,2) = (2,3), and (1\ 3\ 2) \cdot (1,2) = (3,2). Thus the orbit containing (1,2) is \mathcal{O}_2 = \{ (1,2), (2,1), (3,2), (1,3), (2,3), (3,2) \}. These two orbits exhaust the elements of A.

  2. Fix the labeling
    \alpha_{1} = (1,1) \alpha_{4} = (2,1) \alpha_{7} = (3,1)
    \alpha_{2} = (1,2) \alpha_{5} = (2,2) \alpha_{8} = (3,2)
    \alpha_{3} = (1,3) \alpha_{6} = (2,3) \alpha_{9} = (3,3)

    Under the permutation representation S_3 \rightarrow S_9, we have

    1. 1 \mapsto 1
    2. (1\ 2) \mapsto (\alpha_1\ \alpha_5)(\alpha_2\ \alpha_4)(\alpha_3\ \alpha_6)(\alpha_7\ \alpha_8)
    3. (1\ 3) \mapsto (\alpha_1\ \alpha_9)(\alpha_2\ \alpha_8)(\alpha_3\ \alpha_7)(\alpha_4\ \alpha_6)
    4. (2\ 3) \mapsto (\alpha_2\ \alpha_3)(\alpha_4\ \alpha_7)(\alpha_5\ \alpha_9)(\alpha_6\ \alpha_8)
    5. (1\ 2\ 3) \mapsto (\alpha_1\ \alpha_5\ \alpha_9)(\alpha_2\ \alpha_6\ \alpha_7)(\alpha_3\ \alpha_4\ \alpha_8)
    6. (1\ 3\ 2) \mapsto (\alpha_1\ \alpha_9\ \alpha_5)(\alpha_2\ \alpha_7\ \alpha_6)(\alpha_3\ \alpha_8\ \alpha_4)
  3. If \sigma \in \mathcal{O}_1, we have [S_3 : \mathsf{stab}(\sigma)] = 3, so that |\mathsf{stab}(\sigma)| = 2. Consider (2,2) \in \mathcal{O}_1; since (1\ 3) \cdot (2,2) = (2,2), we have \mathsf{stab}((2,2)) = \langle (1\ 3) \rangle.

    If \sigma \in \mathcal{O}_2, then [S_3 : \mathsf{stab}(\sigma)] = 6. Hence |\mathsf{stab}(\sigma)| = 1, and we have \mathsf{stab}(\sigma) = 1.

Find a generating set for Sym(p)

Let p be a prime. Show that S_p = \langle \sigma, \tau \rangle where \sigma is any transposition and \tau any p-cycle.


Let \sigma = (a_1\ a_2) and \tau = (a_1\ b_2\ \ldots\ b_p). (We have a_2 = b_i for some i.) By a previous exercise, \tau^k(a_1) = a_2 for some k. Because \tau has prime order, \langle \sigma, \tau \rangle = \langle \sigma, \tau^k \rangle. Relabeling the elements \{ 1, \ldots, n \}, by the previous exercise we have S_p = \langle \sigma, \tau^k \rangle = \langle \sigma, \tau \rangle.

Determine whether a given permutation is even or odd

In these two previous exercises, we were asked to find the cycle decompositions of some permutations. Write each of those permutations as a product of transpositions and determine whether each is odd or even.


  • (1\ 3\ 5)(2\ 4) = (1\ 5)(1\ 3)(2\ 4) is odd.
  • (1\ 5)(2\ 3) is even.
  • (1\ 5\ 3) = (1\ 3)(1\ 5) is even.
  • (2\ 5\ 3\ 4) = (2\ 4)(2\ 3)(2\ 5) is odd.
  • (1\ 2\ 4\ 3) = (1\ 3)(1\ 4)(1\ 2) is odd.
  • (1\ 13\ 5\ 10)(3\ 15\ 18)(4\ 14\ 11\ 7\ 12\ 9) = (1\ 10)(1\ 5)(1\ 13)(3\ 18)(3\ 15)(4\ 9)(4\ 12)(4\ 7)(4\ 11)(4\ 14) is even.
  • (1\ 14)(2\ 9\ 15\ 13\ 4)(3\ 10)(5\ 12\ 7)(8\ 11) = (1\ 14)(2\ 4)(2\ 13)(2\ 15)(2\ 9)(3\ 10)(5\ 7)(5\ 12)(8\ 11) is odd.
  • (1\ 5)(3\ 8\ 15)(4\ 11\ 12)(7\ 9\ 14)(10\ 13) = (1\ 5)(3\ 15)(3\ 8)(4\ 12)(4\ 11)(7\ 14)(7\ 9)(10\ 13) is even.
  • (1\ 11\ 3)(2\ 4)(5\ 9\ 8\ 7\ 10\ 15)(13\ 14) = (1\ 3)(1\ 11)(2\ 4)(5\ 15)(5\ 10)(5\ 7)(5\ 8)(5\ 9)(13\ 14) is odd.
  • (1\ 4)(2\ 9)(3\ 13\ 12\ 15\ 11\ 5)(8\ 10\ 14) = (1\ 4)(2\ 9)(3\ 5)(3\ 11)(3\ 15)(3\ 12)(3\ 13)(8\ 14)(8\ 10) is odd.
  • (1\ 2\ 15\ 8\ 3\ 4\ 14\ 11\ 12\ 13\ 7\ 5\ 10) = (1\ 10)(1\ 5)(1\ 7)(1\ 13)(1\ 12)(1\ 11)(1\ 14)(1\ 4)(1\ 3) \circ (1\ 8)(1\ 15)(1\ 2) is even.

Exhibit a generating set of Sym(4) consisting of two 4-cycles

Prove that S_4 = \langle (1\ 2\ 3\ 4), (1\ 2\ 4\ 3) \rangle.


We have

  1. (1\ 2\ 3\ 4)^2 = (1\ 3)(2\ 4)
  2. (1\ 2\ 3\ 4)^3 = (1\ 4\ 3\ 2)
  3. (1\ 2\ 3\ 4)^4 = 1
  4. (1\ 2\ 4\ 3)^2 = (1\ 4)(2\ 3)
  5. (1\ 2\ 4\ 3)^3 = (1\ 3\ 4\ 2)
  6. (1\ 2\ 3\ 4)(1\ 2\ 4\ 3) = (1\ 3\ 2)
  7. (1\ 2\ 4\ 3)(1\ 2\ 3\ 4) = (1\ 4\ 2)
  8. (1\ 3\ 2)^2 = (1\ 2\ 3)
  9. (1\ 4\ 2)^2 = (1\ 2\ 4)
  10. (1\ 3\ 2)(1\ 2\ 4) = (2\ 4\ 3)
  11. (1\ 4\ 2)(1\ 2\ 3) = (2\ 3\ 4)

So that |\langle (1\ 2\ 3\ 4), (1\ 2\ 4\ 3) \rangle| \geq 13. By Lagrange’s Theorem, the order of a subgroup of a finite group must divide the order of the group; thus |\langle (1\ 2\ 3\ 4), (1\ 2\ 4\ 3) \rangle| = 24 and we have \langle (1\ 2\ 3\ 4), (1\ 2\ 4\ 3) \rangle = S_4.

Sym(3) is generated by any pair of distinct 2-cycles

Prove that the subgroup of S_3 generated by any two distinct elements of order 2 is all of S_3.


The only elements of order 2 in S_3 are 2-cycles. Let (a\ b), (c\ d) be arbitrary distinct elements of order 2 in S_3; these cycles cannot be disjoint, so we assume without loss of generality that a = d, so that in fact (a\ b) and (a\ c) can represent arbitrary distinct elements of order 2 in S_3. We can compute \langle (a\ b), (a\ c) \rangle explicitly; (a\ b)^2 = 1, (a\ b)(a\ c) = (a\ c\ b), (a\ c)(a\ b) = (a\ b\ c), and (a\ b)(a\ c)(a\ b) = (b\ c). Thus we have generated all of S_3.