Skip to main content

Exercises 10.3 Exercises

1.

Write the following permutations in cycle notation.
  1. \begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{pmatrix} \end{equation*}
  2. \begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 5 & 1 & 3 \end{pmatrix} \end{equation*}
  3. \begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 4 & 2 \end{pmatrix} \end{equation*}
  4. \begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 & 2 & 5 \end{pmatrix} \end{equation*}

2.

Compute each of the following.
  1. \(\displaystyle (1345)(234)\)
  2. \(\displaystyle (12)(1253)\)
  3. \(\displaystyle (143)(23)(24)\)
  4. \(\displaystyle (1423)(34)(56)(1324)\)
  5. \(\displaystyle (1254)(13)(25)\)
  6. \(\displaystyle (1254) (13)(25)^2\)
  7. \(\displaystyle (1254)^{-1} (123)(45) (1254)\)
  8. \(\displaystyle (1254)^2 (123)(45)\)
  9. \(\displaystyle (123)(45) (1254)^{-2}\)
  10. \(\displaystyle (1254)^{100}\)
  11. \(\displaystyle |(1254)|\)
  12. \(\displaystyle |(1254)^2|\)
  13. \(\displaystyle (12)^{-1}\)
  14. \(\displaystyle (12537)^{-1}\)
  15. \(\displaystyle [(12)(34)(12)(47)]^{-1}\)
  16. \(\displaystyle [(1235)(467)]^{-1}\)

3.

Express the following permutations as products of transpositions and identify them as even or odd.
  1. \(\displaystyle (14356)\)
  2. \(\displaystyle (156)(234)\)
  3. \(\displaystyle (1426)(142)\)
  4. \(\displaystyle (17254)(1423)(154632)\)
  5. \(\displaystyle (142637)\)

4.

Find \((a_1, a_2, \ldots, a_n)^{-1}\text{.}\)

5.

List all of the subgroups of \(S_4\text{.}\) Find each of the following sets:
  1. \(\displaystyle \{ \sigma \in S_4 : \sigma(1) = 3 \}\)
  2. \(\displaystyle \{ \sigma \in S_4 : \sigma(2) = 2 \}\)
  3. \(\{ \sigma \in S_4 : \sigma(1) = 3\) and \(\sigma(2) = 2 \}\text{.}\)
Are any of these sets subgroups of \(S_4\text{?}\)

6.

Find all of the subgroups in \(A_4\text{.}\) What is the order of each subgroup?

7.

Find all possible orders of elements in \(S_7\) and \(A_7\text{.}\)

8.

Show that \(A_{10}\) contains an element of order \(15\text{.}\)

9.

Does \(A_8\) contain an element of order \(26\text{?}\)

10.

Find an element of largest order in \(S_n\) for \(n = 3, \ldots, 10\text{.}\)

11.

What are the possible cycle structures of elements of \(A_5\text{?}\) What about \(A_6\text{?}\)

12.

Let \(\sigma \in S_n\) have order \(n\text{.}\) Show that for all integers \(i\) and \(j\text{,}\) \(\sigma^i = \sigma^j\) if and only if \(i \equiv j \pmod{n}\text{.}\)

13.

Let \(\sigma = \sigma_1 \cdots \sigma_m \in S_n\) be the product of disjoint cycles. Prove that the order of \(\sigma\) is the least common multiple of the lengths of the cycles \(\sigma_1, \ldots, \sigma_m\text{.}\)

14.

If \(\sigma\) is a permutation in \(S_n\text{,}\) then an inversion of \(\sigma\) is defined to be a pair of integers \((i,j)\) such that \(1 \leq i < j \leq n\) and \(\sigma(i) > \sigma(j)\text{.}\) The number of inversions of \(\sigma\) is denoted \(\inv(\sigma)\text{.}\)
  1. Show that \(\inv(\sigma) \leq n(n-1)/2\text{.}\)
  2. Prove that \(\inv(\sigma) = 0\) if and only if \(\sigma\) is the identity permutation.
  3. If \(\sigma\) is the transposition \((a\;b)\) with \(a < b\text{,}\) then show that \(\inv(\sigma) = 2(b-a)-1\text{.}\) In particular, \(\inv(\sigma)\) is odd.
  4. Let \(\sigma\) and \(\tau\) be two permutations in \(S_n\text{.}\) Define the sets:
    \begin{align*} A &= \{i, j : 1 \leq i < j \leq n, \sigma(i) > \sigma(j), \tau(\sigma(i)) > \tau(\sigma(j))\}\\ B &= \{i, j : 1 \leq i < j \leq n, \sigma(i) < \sigma(j), \tau(\sigma(i)) > \tau(\sigma(j))\}\\ C &= \{i, j : 1 \leq i < j \leq n, \sigma(i) > \sigma(j), \tau(\sigma(i)) < \tau(\sigma(j))\} \end{align*}
    Prove the identities:
    \begin{align*} \inv(\sigma) &= \lvert A \rvert + \lvert C\rvert\\ \inv(\tau) &=\lvert B\rvert + \lvert C\rvert\\ \inv(\tau\sigma) & = \lvert A\rvert + \lvert B \rvert \end{align*}
  5. Using the notation of the previous part, show that
    \begin{equation*} \inv(\tau\sigma) \equiv \inv(\tau) + \inv(\sigma) \pmod{2} \end{equation*}
  6. Suppose that \(\sigma \in S_n\) can be written as a product \(\sigma = \tau_1 \cdots \tau_n\text{,}\) where \(\tau_1, \ldots, \tau_n\) are transpositions. Prove that \(\inv(\sigma) \equiv n \pmod{2}\text{.}\) In other words, \(\inv(\sigma)\) is even if \(\sigma\) is an even permutation and \(\inv(\sigma)\) is odd if \(\sigma\) is an odd permutation.

15.

Using cycle notation, list the elements in \(D_5\text{.}\) What are \(r\) and \(s\text{?}\) Write every element as a product of \(r\) and \(s\text{.}\)

16.

If the diagonals of a cube are labeled as Figure 10.26, to which motion of the cube does the permutation \((12)(34)\) correspond? What about the other permutations of the diagonals?

17.

Find the group of rigid motions of a tetrahedron. Show that this group is isomorphic to \(A_4\text{.}\)

18.

Prove that \(S_n\) is nonabelian for \(n \geq 3\text{.}\)

19.

Show that \(A_n\) is nonabelian for \(n \geq 4\text{.}\)

20.

Prove that \(D_n\) is nonabelian for \(n \geq 3\text{.}\)

21.

Let \(\sigma \in S_n\) be a cycle. Prove that \(\sigma\) can be written as the product of at most \(n-1\) transpositions.

22.

Let \(\sigma \in S_n\text{.}\) If \(\sigma\) is not a cycle, prove that \(\sigma\) can be written as the product of at most \(n - 2\) transpositions.

23.

If \(\sigma\) can be expressed as an odd number of transpositions, show that any other product of transpositions equaling \(\sigma\) must also be odd.

24.

If \(\sigma\) is a cycle of odd length, prove that \(\sigma^2\) is also a cycle.

25.

Show that a \(3\)-cycle is an even permutation.

26.

Prove that in \(A_n\) with \(n \geq 3\text{,}\) any permutation is a product of cycles of length \(3\text{.}\)

27.

Prove that any element in \(S_n\) can be written as a finite product of the following permutations.
  1. \(\displaystyle (1 2), (13), \ldots, (1n)\)
  2. \(\displaystyle (1 2), (23), \ldots, (n- 1,n)\)
  3. \(\displaystyle (12), (1 2 \ldots n )\)

28.

Let \(G\) be a group and define a map \(\lambda_g : G \rightarrow G\) by \(\lambda_g(a) = g a\text{.}\) Prove that \(\lambda_g\) is a permutation of \(G\text{.}\)

29.

Prove that there exist \(n!\) permutations of a set containing \(n\) elements.

30.

Recall that the center of a group \(G\) is
\begin{equation*} Z(G) = \{ g \in G : gx = xg \text{ for all } x \in G \}. \end{equation*}
  1. Find the center of \(D_8\text{.}\)
  2. Find the center of \(D_{10}\text{?}\)
  3. What is the center of \(D_n\text{?}\)

31.

Let \(\tau = (a_1, a_2, \ldots, a_k)\) be a cycle of length \(k\text{.}\)
  1. Prove that if \(\sigma\) is any permutation, then
    \begin{equation*} \sigma \tau \sigma^{-1 } = ( \sigma(a_1), \sigma(a_2), \ldots, \sigma(a_k)) \end{equation*}
    is a cycle of length \(k\text{.}\)
  2. Let \(\mu\) be a cycle of length \(k\text{.}\) Prove that there is a permutation \(\sigma\) such that \(\sigma \tau \sigma^{-1 } = \mu\text{.}\)

32.

For \(\alpha\) and \(\beta\) in \(S_n\text{,}\) define \(\alpha \sim \beta\) if there exists an \(\sigma \in S_n\) such that \(\sigma \alpha \sigma^{-1} = \beta\text{.}\) Show that \(\sim\) is an equivalence relation on \(S_n\text{.}\)

33.

Let \(\sigma \in S_X\text{.}\) If \(\sigma^n(x) = y\text{,}\) we will say that \(x \sim y\text{.}\)
  1. Show that \(\sim\) is an equivalence relation on \(X\text{.}\)
  2. If \(\sigma \in A_n\) and \(\tau \in S_n\text{,}\) show that \(\tau^{-1} \sigma \tau \in A_n\text{.}\)
  3. Define the orbit of \(x \in X\) under \(\sigma \in S_X\) to be the set
    \begin{equation*} {\mathcal O}_{x, \sigma} = \{ y : x \sim y \}. \end{equation*}
    Compute the orbits of each of the following elements in \(S_5\text{:}\)
    \begin{align*} \alpha & = (1254)\\ \beta & = (123)(45)\\ \gamma & = (13)(25). \end{align*}
  4. If \({\mathcal O}_{x, \sigma} \cap {\mathcal O}_{y, \sigma} \neq \emptyset\text{,}\) prove that \({\mathcal O}_{x, \sigma} = {\mathcal O}_{y, \sigma}\text{.}\) The orbits under a permutation \(\sigma\) are the equivalence classes corresponding to the equivalence relation \(\sim\text{.}\)
  5. A subgroup \(H\) of \(S_X\) is transitive if for every \(x, y \in X\text{,}\) there exists a \(\sigma \in H\) such that \(\sigma(x) = y\text{.}\) Prove that \(\langle \sigma \rangle\) is transitive if and only if \({\mathcal O}_{x, \sigma} = X\) for some \(x \in X\text{.}\)

34.

Let \(\alpha \in S_n\) for \(n \geq 3\text{.}\) If \(\alpha \beta = \beta \alpha\) for all \(\beta \in S_n\text{,}\) prove that \(\alpha\) must be the identity permutation; hence, the center of \(S_n\) is the trivial subgroup.

35.

If \(\alpha\) is even, prove that \(\alpha^{-1}\) is also even. Does a corresponding result hold if \(\alpha\) is odd?

36.

Show that \(\alpha^{-1} \beta^{-1} \alpha \beta\) is even for \(\alpha, \beta \in S_n\text{.}\)

37.

Let \(r\) and \(s\) be the elements in \(D_n\) described in Theorem 10.23
  1. Show that \(srs = r^{-1}\text{.}\)
  2. Show that \(r^k s = s r^{-k}\) in \(D_n\text{.}\)
  3. Prove that the order of \(r^k \in D_n\) is \(n / \gcd(k,n)\text{.}\)
PrevTopNext