Exercise 1.  Choose some permutations in S15  and compute their cycle decompositions.

Exercise 2.

1.  Describe all elements σ ∈ Sn  such that σ 2  = id.

2.  Determine the number of such σ ∈ Sn  that σ 3  = id.

3.  Determine the number of such σ ∈ Sn  that σ 4  = id.

Exercise 3  (Parity and cycle decompositions).  Let σ  ∈  Sn  and let σ  = γ 1 ··· γr , where γi  is an ℓi-cycle. Express the parity of σ in terms of ℓ1 , . . . ,ℓr .

Exercise 4.  Recall that an inversion of a permutation σ  ∈ Sn  is an ordered pair (i,j) ∈ {1, . . . ,n}2  such that i < j  and σ(j) < σ(i). We denote the set of inversions of σ by inv(σ).

1.  Prove that the largest number of inversions a permutation in Sn  can have is  2(n) .

2.  Prove that there is a unique element σ ∈ Sn  with  2(n)  inversions. What is this element? Exercise 5 (Alternating groups are non-abelian).  Prove that An  is non-abelian for n ≥ 4.    Exercise 6.  Prove that two transpositions commute if and only if they are disjoint.

Exercise 7 (Z(Sn ) and Z(An )).  Prove that Z(Sn ) = {id} for all n ≥ 3 and Z(A4 ) = {id} for all n ≥ 4. Exercise 8 (Generating sets of Sn ).

1.  Prove that every element of Sn can be written as a (possibly empty) product of elements in {(12), (13), . . . (1n)} . Thus, Sn  = ⟨(12), (13), . . . , (1n)⟩ .

2.  Recall that a group G is generated by a subset of elements {g1 ,g2 , . . . ,gk } if every element of G can be represented as a product of several copies of gi  and g   Prove that for n  ≥  2 the group Sn  is generated by (12) and (12 . . . n).

Exercise 9 (An  is generated by the 3-cycles and by pairs of transpositions) .

1.  Prove that the product of two transpositions is always a product of 3-cycles.

2.  Prove that An  is generated by the 3-cycles in Sn .

3.  Prove that An  is generated by the pairs of transpositions in Sn  for n ≥ 5.  (is this true for n < 5?) Exercise 10 (The subgroups of A4 ). In this exercise you will determine all subgroups of A4 .

1.  Prove that if a subgroup H of A4  contains two distinct 3-cycles α,β such that β  α −1, then H = A4 .

2.  Prove that if a subgroup H of A4  contains a 3-cycle and an element of order 2, then H = A4 .

3.  Prove that if H is a subgroup of A4 , then either H = {id}, H = A4 , H is generated by a 3-cycle, or H is generated by elements of order 2.

4.  Determine all subgroups of A4 .

Exercise  11  (Permutation matrices, sgn, and det).  For each σ  ∈  Sn , let P(σ) denote the n  × n  matrix whose ith  row is the σ−1(i)th  standard basis vector, that is,

 ⃗eσ − 1 (1)

P(σ) =                 

⃗eσ − 1 (n)

1.  Let σ ∈ Sn  and let A ∈ Matn×n(C). What is P(σ)A?

2.  Prove that for all σ 1 ,σ2  ∈ Sn  we have P(σ1 σ2 ) = P(σ1 )P(σ2 ).

3.  Prove that for all every transposition τ ∈ Sn  we have det(P(τ)) = −1.

4.  Prove that for all σ ∈ Sn  we have sgn(σ) = det(P(σ)).

Exercise 12. Let G be a group and let S ⊆ G be a subset that generates G .  (See the Week 2 Exercises for the definition of a group generated by a set.) Let S −1  = {s−1  : s ∈ S} . For each g ∈ G, we define the length of g  with respect to S to be the smallest n ∈ Z ≥0  such that g is a product of n elements of S ∪ S−1, and we denote it by ℓS (g). Prove that the function ℓ S  : G → Z ≥0  satisfies the following properties.

1.  For all g ∈ G we have ℓS (g) = 0 if and only if g = e .

2.  For all g ∈ G we have ℓS (g−1) = ℓS (g).

3.  For all g1 ,g2  ∈ G we have |ℓS (g1 ) − ℓS (g2 )| ≤ ℓS (g1g2 ) ≤ ℓS (g1 ) + ℓS (g2 ).

4.  For all g ∈ G and s ∈ S we have ℓS (sg) = ℓS (g) ± 1.

Define dS  : G × G → Z ≥0  by dS (g1 ,g2 ) = ℓS (g1g2(−)1 ) for all g1 ,g2  ∈ G .

5.  Prove that dS  is a metric on G .

Exercise 13.  Recall that Sn  is generated by the set S = {τi  : i = 1, . . . ,n − 1}, where τi  = (i(i + 1)) for each i ∈ {1, . . . ,n − 1} .  Therefore Sn  is also generated by the set S0  ⊆ Sn  of all transpositions in Sn .  Let ℓ0  : Sn  → Z ≥0  be the length function ℓ S0    and let ℓ  : Sn  → Z ≥0  be the length function ℓ S .  (These length functions are defined in the preceding exercise.) We will begin by comparing ℓ0  and ℓ .

1.  Prove that for all σ ∈ Sn  we have ℓ0 (σ) ≤ ℓ(σ).

2.  Find a permutation σ such that ℓ0 (σ)  ℓ(σ).

3.  For which n ∈ Z>0  is ℓ0 (σ) = ℓ(σ) for all σ ∈ Sn ?

Now we will establish formulas ℓ0  and ℓ that do not reference to the sets S0  and S .

4.  Define the length of a k-cycle to be k − 1.  Define the length of a permutation σ  ∈ Sn  to be the sum of the lengths of the cycles that occur in its cycle decomposition, and denote it by len(σ). Prove that sgn(σ) = (−1)len(σ) .

5.  Prove that for all σ ∈ Sn  and τ ∈ S0  we have(

(Hint: Compute (ci cj )(c1 c2  . . . cn ).)

6.  Prove by induction that for all n ∈ Z>0  we have ℓ0 (σ) = len(σ) for all σ ∈ Sn .

7.  Let σ ∈ Sn  and τi  ∈ S . Prove that

|inv(τi σ)| =

8.  Prove by induction that for all n ∈ Z>0  we have ℓ(σ) = |inv(σ)| for all σ ∈ Sn .

Parts 6 and 8 can be used to translate results about ℓ0  and ℓ into results about len and |inv |, and vice versa. Here are some examples: