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.
![1413_Figure.png](https://secure.tutorsglobe.com/CMSImages/1413_Figure.png)
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 S16.)
2. Let σ ∈ Sn. 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 π ∈ Sn, 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· · · τ2τ1 where τi is a transposition for every i. Define the permutation ρj = τjτj-1· · · τ2τ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) φ: S3 → GL3(C).
(b) φ: D2n → GL2(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
D6 S3 Z/6Z Z/2Z × Z/3Z.