Math 171: Abstract Algebra, Fall 2014- Assignment 3

1. Consider the following game played on a 4-by-4 grid together with 15 tiles numbered 1, 2, . . . , 15, and a single vacant location on the grid.

A legal move consists of sliding a numbered tile into the vacant location. From the initial configuration above, for instance, there are two legal moves: sliding the 12 down or the 15 to the right. The object of the puzzle is to use a sequence of legal moves to interchange the position of the tiles labeled 14 and 15 while leaving all other tiles unchanged.

Is it possible to achieve this goal? Prove or disprove. (Hint: Write down moves and configurations as permutations in S₁₆.)

2. Let σ ∈ S_n. In this problem we will prove that if σ is written as the product of transpositions in two different ways, one with r transpositions and one with r' transpositions, then we must have r ≡ r' mod 2. Throughout this, for any permutation π ∈ S_n, we define c(π) to be the number of cycles in the disjoint cycle decomposition of π, including its 1-cycles. For instance, if π is a transposition, then c(π) = n - 1.

(a) Suppose σ = τ_rτ_r-1· · · τ₂τ₁ where τ_i is a transposition for every i. Define the permutation ρ_j = τ_jτ_j-1· · · τ₂τ₁ for every j ∈ {1, 2, . . . ,r}. Show that c(ρ_j+1) - c(ρ_j) ∈ {±1}.

(b) Let g be the number of indices j ∈ {1, 2, . . . ,r - 1} for which c(ρ_j+1) - c(ρ_j) = 1 and h be the number of indices j ∈ {1, 2, . . . ,r - 1} for which c(ρ_j+1) - c(ρ_j) = -1. Prove c(σ) = (n - 1) + g - h.

(c) Explain why g + h = r - 1 and use this to prove r = n - c(σ) + 2g.

(d) Conclude the desired result.

3. Find, with justification, an injective homomorphism φ in each of the following cases:

(a) φ: S₃ → GL₃(C).

(b) φ: D₂n → GL₂(C) for any n ≥ 3.

4. Let φ : G → H be a homomorphism.

(a) Prove that if H' ≤ H and G' = {g ∈ G | φ(g) ∈ H'}, then G' ≤ G. G' is called the pre-image of H' under φ.

(b) If φ is an isomorphism, and k is a positive integer, prove the number of elements of order k in G equals the number of elements of order k in H.

5. Below is a list of groups. Determine which pairs of these are isomorphic and which are not. Justify

D₆           S₃            Z/6Z       Z/2Z × Z/3Z.