21-373: Algebraic Structures Assignment 3

Peter Battaglino 18. February, 2005

Problem 5.19: 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.

\underline{Solution:} Let H ⩽ S_{n}. If every element of H is an even permutation, then there is nothing to show. Suppose there is at least one odd permutation in H. Let A denote the set of all even permutations in H and B = H \ A denote the set of all odd permutations in H. Let β ∈ B and let f: A → B be defined by f(α) = αβ for each α ∈ A. Now suppose f(γ) = f(δ), where γ, δ ∈ A. Then γβ = δβ. Since H is a group, we know that there is an element β^{−1} of H such that ββ^{−1} = ε, so we can write γββ^{−1} = δββ^{−1}, so we see that γ = δ. Thus f is injective. Now let ω ∈ B be given. We know that ω = ω(β^{−1}β) = (ωβ^{−1})β. Since the identity cycle ε is even and ββ^{−1} = ε and β is odd, we know that β^{−1} is also odd. Thus, since ω and β^{−1} are both odd, ωβ^{−1} is even. Thus we have found for every element ω ∈ B an element ωβ^{−1} ∈ A such that f(ωβ^{−1}) = ω, proving that f is also surjective. Hence, f is a bijection, and it follows that there exists a bijection between A and B, which implies that the cardinality of A is equal to the cardinality of B. In other words, the number of even permutations is equal to the number of odd permutations, which is half the total number of elements in H.

Problem 5.32: Let β = (1, 3, 5, 7, 9, 8, 6)(2, 4, 10). What is the smallest positive integer n for which β^{n} = β^{−5}?

\underline{Solution:} The orders of the two disjoint cycles that comprise β are 7 and 3. The least common multiple of 7 and 3 is 21, so we know that the order of β is 21. Let n be a positive integer. We see that β^{n} = β^{−5} follows from

β^{5}β^{n} = β^{5}β^{−5}  (1)
β^{n+5} = ε,  (2)

which follows from the statement 21 | (n + 5). The smallest positive integer n that makes this statement true is 16. This is what we were asked to find.

Problem 5.46: Show that for n ≥ 3, Z(S_{n}) = {ε}.

\underline{Solution:} If n = 1, then S_{n} = \{ε\}. If n = 2, then S_{n} = \{ε, (1, 2)\}. Since (1, 2) commutes with itself, Z(S_{2}) = S_{2}. Now suppose n ≥ 3, and denote n^{]} := {1, 2, ⋯, n}. Let σ ∈ Z(S_{n}). Then, for every two-cycle (a, b) ∈ S_{n}, with a, b ∈ n^{]}, a ≠ b we have σ(a, b) = (a, b)σ. This means that (σ(a) = a and σ(b) = b), or (σ(a) = b and σ(b) = a). Suppose σ(a) = b and σ(b) = a. Then, since we have assumed n ≥ 3, we can choose an element c ∈ n^{]}, c ≠ b, c ≠ a such that σ commutes with (a, c). Once again, this implies that (σ(a) = a and σ(c) = c), or (σ(a) = c and σ(c) = a). We’ve already excluded the case σ(a) = a, so we see that since σ(a) = b, it is true that b = c. However, this contradicts our earlier assumption that c ≠ b so it follows that the only possibility is that σ(a) = a for all a ∈ n^{]}. Thus, σ = ε. Since we chose σ ∈ Z(S_{n}) arbitrarily, it follows that Z(S_{n}) = {ε} for n ≥ 3.

Problem 5.50: (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?

\underline{Solution:} We can represent this permutation by the matrix

( \begin{matrix}A & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & J & Q & K \\ 10 & 9 & Q & 8 & K & 3 & 4 & A & 5 & J & 6 & 2 & 7 \end{matrix} )

Calling this permutation γ, we see that γ has the decomposition

γ = (A, 10, J, 6, 3, Q, 2, 9, 5, K, 7, 4, 8).  (3)

We seek a cycle α ∈ S_{13} such that α^{2} = γ is satisfied. To do this, examine the cycle (a, b, c, d, e, f, g, h, i, j, k, l, m), with each of its elements in the set {1, 2, ⋯, 13}, noting that it has the same length as γ. We see that its square is

(a, c, e, g, i, k, m, b, d, f, h, j, l).

Now, to read off the original cycle, we pick the first element as a and write it down, and then count off seven elements until we get to b, and then count off another seven elements, circling back around to the beginning when we reach the end until we get to c, etc. until we have thirteen elements written down. It is easy to see that this cycle is the original cycle we started with. We simply apply this approach to the card-shuffling cycle of this problem to get

α = (A, 9, 10, 5, J, K, 6, 7, 3, 4, Q, 8, 2).  (4)

Applying this permutation to the original sorted deck of cards yields

( \begin{matrix}A & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & J & Q & K \\ 9 & A & 4 & Q & J & 7 & 3 & 2 & 10 & 5 & K & 8 & 6 \end{matrix} ) .

The bottom row of this permutation represents the deck after one shuffle, which is what we were asked to find.