exercises-permute.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section5.3Exercises

¶

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*}$$

Hint

(a) $(12453)\text{;}$ (c) $(13)(25)\text{.}$

2

Compute each of the following.

1. $(1345)(234)$

2. $(12)(1253)$

3. $(143)(23)(24)$

4. $(1423)(34)(56)(1324)$

5. $(1254)(13)(25)$

6. $(1254) (13)(25)^2$

7. $(1254)^{-1} (123)(45) (1254)$

8. $(1254)^2 (123)(45)$

9. $(123)(45) (1254)^{-2}$

10. $(1254)^{100}$

11. $|(1254)|$

12. $|(1254)^2|$

13. $(12)^{-1}$

14. $(12537)^{-1}$

15. $[(12)(34)(12)(47)]^{-1}$

16. $[(1235)(467)]^{-1}$

Hint

(a) $(135)(24)\text{;}$ (c) $(14)(23)\text{;}$ (e) $(1324)\text{;}$ (g) $(134)(25)\text{;}$ (n) $(17352)\text{.}$

3

Express the following permutations as products of transpositions and identify them as even or odd.

1. $(14356)$

2. $(156)(234)$

3. $(1426)(142)$

4. $(17254)(1423)(154632)$

5. $(142637)$

Hint

(a) $(16)(15)(13)(14)\text{;}$ (c) $(16)(14)(12)\text{.}$

4

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

Hint

$(a_1, a_2, \ldots, a_n)^{-1} = (a_1, a_{n}, a_{n-1}, \ldots, a_2)$

5

List all of the subgroups of $S_4\text{.}$ Find each of the following sets.

1. $\{ \sigma \in S_4 : \sigma(1) = 3 \}$

2. $\{ \sigma \in S_4 : \sigma(2) = 2 \}$

3. $\{ \sigma \in S_4 : \sigma(1) = 3$ and $\sigma(2) = 2 \}$

Are any of these sets subgroups of $S_4\text{?}$

Hint

(a) $\{ (13), (13)(24), (132), (134), (1324), (1342) \}$ is not a subgroup.

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.

Hint

$(12345)(678)\text{.}$

9

Does $A_8$ contain an element of order 26?

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{?}$

Hint

Permutations of the form

$$\begin{equation*} (1), (a_1, a_2)(a_3, a_4), (a_1, a_2, a_3), (a_1, a_2, a_3, a_4, a_5) \end{equation*}$$

are possible for $A_5\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

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{.}$

15

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

16

Find the group of rigid motions of a tetrahedron. Show that this is the same group as $A_4\text{.}$

17

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

Hint

Calculate $(123)(12)$ and $(12)(123)\text{.}$

18

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

19

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

20

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

21

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.

22

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

23

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

24

Show that a 3-cycle is an even permutation.

25

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

Hint

Consider the cases $(ab)(bc)$ and $(ab)(cd)\text{.}$

26

Prove that any element in $S_n$ can be written as a finite product of the following permutations.

1. $(1 2), (13), \ldots, (1n)$

2. $(1 2), (23), \ldots, (n- 1,n)$

3. $(12), (1 2 \ldots n )$

27

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{.}$

28

Prove that there exist $n!$ permutations of a set containing $n$ elements.

29

Recall that the of a group $G$ is

$$\begin{equation*} Z(G) = \{ g \in G : gx = xg \text{ for all } x \in G \}. \end{equation*}$$

Find the center of $D_8\text{.}$ What about the center of $D_{10}\text{?}$ What is the center of $D_n\text{?}$

30

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{.}$

Hint

For (a), show that $\sigma \tau \sigma^{-1 }(\sigma(a_i)) = \sigma(a_{i + 1})\text{.}$

31

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{.}$

32

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 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 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{.}$

33

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.

34

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

35

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

36

Let $r$ and $s$ be the elements in $D_n$ described in Theorem 5.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{.}$