Permutation Groups

Let

Compute each of the following.

Let

Write $\alpha$, $\beta$, and $\alpha \beta$ as a products of disjoint cycles and as products of 2-cycles.

Write each of the following permutations as a product of disjoint cycles.

Find the order of each of the following permutations.

What is the order of each of the following permutations?

What is the order of each of the following permutations?

What is the order of the product of a pair of disjoint cycles of lengths 4 and 6? What about the product of three disjoint cycles of lengths 6, 8, and 10?

Determine whether the following permutations are even or odd.

Write $((14562)(2345)(136)(235))^{10}$ as a product of disjoint cycles.

Write $(13)(1245)(13)$ and $(24)(13456)(24)$ in disjoint cycle form. Give a simple description of how each product cycle compares with middle cycle in each product.

Let $n$ be a positive integer. If $n$ is odd, is an $n$-cycle an odd or an even permutation? If $n$ is even, is an $n$-cycle an odd or an even permutation?

If $\alpha$ is even, prove that $\alpha^{-1}$ is even. If $\alpha$ is odd, prove that $\alpha^{-1}$ is odd.

Show that a function from a finite set $S$ to itself is one-to- one if and only if it is onto. Is this true when $S$ is infinite? (This exercise is referred to in Chapter 6.)

For $n \geq 4$ how many elements in $S_n$ are there that map 1 to 2, 2 to 3, and 3 to 1? For $n \geq 5$, how many are in $A_n$?

Let $\alpha$ and $\beta$ belong to $S_n$. Prove that $\alpha \beta$ is even if and only if $\alpha$ and $\beta$ are both even or both odd.

Associate an even permutation with the number $+1$ and an odd permutation with the number $-1$. Draw an analogy between the result of multiplying two permutations and the result of multiplying their corresponding numbers $+1$ or $-1$.

If $n$ is any integer and $\alpha$ is odd complete the following statement: $\alpha^n$ is odd if and only if .

In $S_n$, let $\alpha$ be an $r$-cycle, $\beta$ an $s$-cycle, and $\gamma$ a $t$-cycle. Complete the following statements: $\alpha \beta$ is even if and only if $r + s$ is ; $\alpha \beta \gamma$ is even if and only if $r + s + t$ is .

Let $\alpha$ and $\beta$ belong to $S_n$. Prove that $\alpha^{-5}\beta \alpha^3$ is odd if and only if $\beta$ is odd.

Let $\alpha$ and $\beta$ belong to $S_n$. Prove that $\beta \alpha \beta^{-1}$ and $\alpha$ are both even or both odd.

Complete the following statement: A product of cycles is an even permutation if and only if the number of cycles of even length is .

What is the smallest $n$ for which $S_n$ has an element of order 30? What about $A_n$?

What are the possible orders for the elements of $S_6$ and $A_6$? What about $A_7$? (This exercise is referred to in Chapter 24.)

Find an element in $A_8$ of order 15. Find an element in $A_{12}$ of order 30.

Let $\beta = (1, 3, 5, 7, 9, 8, 6)(2, 4, 10)$. What is the smallest positive integer $n$ for which $\beta^n = \beta^{-5}$?

What cycle is $(a_1 a_2 \cdots a_n)^{-1}$?

Show that if $H$ is a subgroup of $S_n$, then either every member of $H$ is an even permutation or exactly half of the members are even. (This exercise is referred to in Chapter 24.)

Suppose that $H$ is a subgroup of $S_n$ of odd order. Prove that $H$ is a subgroup of $A_n$.

Give two reasons why the set of odd permutations in $S_n$ is not a subgroup.

Let $\alpha$ and $\beta$ belong to $S_n$. Prove that $\alpha^{-1}\beta^{-1}\alpha \beta$ is an even permutation.

How many elements are there of order 2 in $A_8$ that have the disjoint cycle form $(a_1 a_2)(a_3 a_4)(a_5 a_6)(a_7 a_8)$?

For $n \geq 5$, how many odd permutations of order 5 are in $S_n$?

How many elements in $A_6$ have order 2? How many elements in $A_7$ have order 6?

Let $H = \left\{ x^2 \mid x \in A_4\right\}$. Prove that $H$ is not a subgroup of $A_4$. (Compare with Example 5 of Chapter 3.)

What is the smallest $n$ for which there is a solution in $S_n$ to the equation $x^5 = (12345)$? Give an example of a solution. How many solutions are there for your $n$?

Let $\alpha = (1, 3, 5, 7, 9)(2, 4, 6)(8, 10)$. If $\alpha^m$ is a 5-cycle, what can you say about $m$?

How many elements of order 4 does $S_6$ have? How many elements of order 2 does $S_6$ have?

Prove that $(1234)$ is not the product of 3-cycles. Generalize.

Let $\beta \in S_7$ and suppose $\beta^4 = (2143567)$. Find $\beta$. What are the possibilities for $\beta$ if $\beta \in S_9$?

Let $\beta = (123)(145)$. Write $\beta^{99}$ in disjoint cycle form.

Let $(a_1 a_2 a_3 a_4)$ and $(a_5 a_6)$ be disjoint cycles in $S_{10}$. Show that there is no element $x$ in $S_{10}$ such that $x^2 = (a_1 a_2 a_3 a_4)(a_5 a_6)$.

If $\alpha$ and $\beta$ are distinct 2-cycles, what are the possibilities for $|\alpha \beta |$?

Let $G$ be a group of permutations on a set $X$. Let $a \in X$ and define $\mathrm{stab}(a) = \left\{ \alpha \in G \mid \alpha (a) = a\right\}$. We call $\mathrm{stab}(a)$ the stabilizer of $a$ in $G$ (since it consists of all members of $G$ that leave $a$ fixed). Prove that $\mathrm{stab}(a)$ is a subgroup of $G$. (This subgroup was introduced by Galois in 1832.) This exercise is referred to in Chapter 7.

Let $H = \left\{ \beta \in S_5 \mid \beta (1) = 1 \text{ and } \beta (3) = 3\right\}$. Prove that $H$ is a subgroup of $S_5$. How many elements are in $H$? Is your argument valid when $S_5$ is replaced by $S_n$ for $n \geq 3$? How many elements are in $H$ when $S_5$ is replaced by $A_n$ for $n \geq 4$?

For $n \geq 3$, let $H = \left\{ \beta \in S_n \mid \beta (1) = 1 \text{ or } 2 \text{ and } \beta (2) = 1 \text{ or } 2\right\}$. Prove that $H$ is a subgroup of $S_n$. Determine $|H|$.

Let $\alpha$ be a 12-cycle. Describe the cycle structure of $\alpha^2, \alpha^3, \alpha^4$ and $\alpha^6$. More generally, if $\alpha$ is an $n$-cycle and $k$ divides $n$ describe the cycle structure of $\alpha^k$.

Let $\alpha$ be a $n$-cycle and $k$ a positive integer. Prove that $\alpha^k$ is an $n$-cycle if and only if $\gcd (n, k) = 1$.

In $S_3$, find elements $\alpha$ and $\beta$ such that $|\alpha | = 2$, $|\beta | = 2$, and $|\alpha \beta | = 3$.

Find group elements $\alpha$ and $\beta$ in $S_5$ such that $|\alpha | = 3$, $|\beta | = 3$, and $|\alpha \beta | = 5$.

Represent the symmetry group of an equilateral triangle as a group of permutations of its vertices (see Example 3).

Prove that $S_n$ is non-Abelian for all $n \geq 3$. Prove that $A_n$ is non-Abelian for all $n \geq 4$.

Show that in $S_n$ ($n \geq 4$), the equation $x^2 = (1234)$ has no solutions but in $S_7$ the equation $x^3 = (1234)$ has three solutions.

Prove Theorem 5.6.

(Theorem 5.6, Even Permutations Form a Group: The set of even permutations in $S_n$ forms a subgroup of $S_n$.)

If $(ab)$ and $(cd)$ are distinct 2-cycles in $S_n$, prove that $(ab)$ and $(cd)$ commute if and only if they are disjoint.

In $S_4$, find a cyclic subgroup of order 4 and a noncyclic subgroup of order 4.

In $S_{100}$ let $\alpha = (1, 2, 3, \ldots , 100)$ and $\beta = (1, 50, 100)$. What is $|\alpha \beta |$? Give an example of two elements in $S_{100}$ that both have order 100 and whose product has order 3.

Viewing the members of $D_4$ as a group of permutations of a square labeled 1, 2, 3, 4 as described in Example 3, which geometric symmetries correspond to even permutations?

Viewing the members of $D_5$ as a group of permutations of a regular pentagon with consecutive vertices labeled 1, 2, 3, 4, 5, what geometric symmetry corresponds to the permutation $(14253)$? Which symmetry corresponds to the permutation $(25)(34)$?

Let $n$ be an odd integer greater than 1. Viewing $D_n$ as a group of permutations of a regular $n$-gon with consecutive vertices labeled $1, 2, \ldots , n$, explain why the rotation subgroup of $D_n$ is a subgroup of $A_n$. Is $D_5$ a subgroup of $A_5$? If so, identify a reflection in $D_5$ that is in $A_5$. Why does this prove that $D_5$ is a subgroup of $A_5$? Is $D_7$ a subgroup of $A_7$? If so, identify a reflection in $D_7$ that is in $A_7$.

Show that every element in $A_n$ for $n \geq 3$ can be expressed as a 3-cycle or a product of 3-cycles.

For $n \geq 4$ let $B_n$ be the set of all elements in $S_n$ that can be written as the product of an even number of 4-cycles. Prove that $B_n$ is a subgroup of $A_n$.

Letting $B_n$ be as defined in previous exercise prove that every 3-cycle in $A_n$ ($n \geq 4$) is the product of two 4-cycles.

Letting $B_n$ ($n \geq 4$) be the subgroup of $A_n$ defined in Exercise 61, prove that $B_n = A_n$.

Let $\alpha_1, \alpha_2$ and $\alpha_3$ be 2-cycles. Prove that $\alpha_1 \alpha_2 \alpha_3 \neq \varepsilon$. Generalize.

Show that $A_5$ has 24 elements of order 5, 20 elements of order 3, and 15 elements of order 2. (This exercise is referred to in Chapter 24.)

Find a cyclic subgroup of $A_6$ that has order 4. Find a noncyclic subgroup of $A_8$ that has order 4.

Show that a permutation with odd order must be an even permutation.

Compute the order of each member of $A_4$. What arithmetic relationship do these orders have with the order of $A_4$?

For any odd integer $n$ at least 3 write $(2, n)(3, n - 1) \cdots ((n+1)/2, (n+3)/2)(12 \cdots n)$ in disjoint cycle form. Notice that $|(2, n)(3, n - 1) \cdots ((n+1)/2, (n+3)/2)| = 2$ and $|(12 \cdots n)| = n$ and their product has order 2. Labeling the vertices of a regular $n$-gon with $1, 2, \ldots , n$ counterclockwise as in Example 3, which elements of $D_n$ correspond to $(2, n)(3, n - 1) \cdots ((n+1)/2, (n+3)/2)$ and $(12 \cdots n)$?

Show that for $n \geq 3$, $Z(S_n) = \{ \varepsilon \}$.

Verify the statement made in the discussion of the Verhoeff check digit scheme based on $D_5$ that $a * \sigma (b) \neq b * \sigma (a)$ for distinct $a$ and $b$. Use this to prove that $\sigma^i(a) * \sigma^{i+1}(b) \neq \sigma^i(b) * \sigma^{i+1}(a)$ for all $i$. Prove that this implies that all transposition errors involving adjacent digits are detected.

(Recall the Verhoeff scheme: view the digits 0 through 9 as the elements of the dihedral group $D_5$ of order 10, using the permutation $\sigma = (01589427)(36)$ and the group operation $*$ of $D_5$. To a string of digits $a_1 a_2 \ldots a_{n-1}$, a check digit $a_n$ is appended so that $\sigma (a_1) * \sigma^2(a_2) * \cdots * \sigma^{n-1}(a_{n-1}) * \sigma^n(a_n) = 0$, where $\sigma^2(x) = \sigma (\sigma (x))$, $\sigma^3(x) = \sigma (\sigma^2(x))$, and so on. Since $\sigma$ has the property that $\sigma^i(a) \neq \sigma^i(b)$ if $a \neq b$, all single-digit errors are detected automatically.)

Use the Verhoeff check-digit scheme based on $D_5$ to append a check digit to 45723.

Prove that every element of $S_n$ ($n > 1$) can be written as a product of elements of the form $(1k)$.

(Indiana College Mathematics Competition) A card- shuffling machine always rearranges cards in the same way relative to the order in which they were given to it. All of the hearts arranged in order from ace to king were put into the machine, and then the shuffled cards were put into the machine again to be shuffled. If the cards emerged in the order 10, 9, Q, 8, K, 3, 4, A, 5, J, 6, 2, 7, in what order were the cards after the first shuffle?

Determine integers $n$ for which $H = \left\{ \alpha \in A_n \mid \alpha^2 = \varepsilon \right\}$ is a subgroup of $A_n$.

Find five subgroups of $S_5$ of order 24.

Why does the fact that the orders of the elements of $A_4$ are 1, 2, and 3 imply that $|Z(A_4)| = 1$?

Let $\alpha$ belong to $S_n$. Prove that $|\alpha |$ divides $n!$.

Encrypt the message ATTACK POSTPONED using the permutation $\alpha = \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 5 & 3 & 4 \end{bmatrix}$.

The message VAADENWCNHREDEYA was encrypted using the permutation $\alpha = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{bmatrix}$. Decrypt it.