344 CH 5 Solns W09 TEMP

MA344 Selected Chapter 5 Solutions Revised: Winter 2009
Solutions are in boldface. Most of the problems without solutions are routine compu-
tations.
All text problems are found on pages 112-115.
1. Composing permutations: Problem 17 (The author abbreviates β ◦ α as βα and writes

“product” instead of “composition.” That’s fine and it’s standard, but don’t forget
that you are actually composing functions, not multiplying. The use of “product” is
universal slang among group theorists, but it’s not necessarily good for novices. You
should consider avoiding the slang.)
2. Cycle notation: Read the Cycle Notation Section on pages 97-99. By the way, the
word “cycle” here should not be confused with the word “cyclic” as used in Chapter
3.
(a) Problem 18a. (By “product,” the author actually means “composition.” See
above.)
(b) Write the permutations given in problems 4 and 17 as compositions of disjoint
cycles.
(c) Now reverse the process by writing the permutations given in problem 3a,c,e,f in
the array notation.
(d) Do problems 1, 2 (an educated guess based on problem 1 is all that I am after in
problem 2); 3a,c with the definition only, without using any theorems.
(e) After doing part 2d above, read the statement of Theorem 5.3. Use that theorem
to check your answers to 3a,c.
(f) Use Thm. 5.3 to do 3b,d,e,f and 20. Caution: 3e,f are not given initially as the
composition of disjoint cycles.
(g) Problem 6
Consider the permutation α := (1; 2 3 4 5) ◦ (6 7 8) in S8 . By Ruffini’s
Theorem 5.3, α has order 15. By direct computation, α = (1 5) ◦ (1 4) ◦
(1 3) ◦ (1 2) ◦ (6 8) ◦ (1 5), the composition of 6 2-cycles. Therefore, α is
even, in other words, α ∈ A8 .
(h) Problem 30
We did this one class.
3. A basic fact about Sn : Problem 41. Your task here is to take a generic n which is at
least 3 and show that Sn is not Abelian.
Let
" n be a positive # integer with "n ≥ 3. Consider the
# permutations
1 2 3 4 ···n 1 2 3 4 ···n
= (1 2 3) and = (1 2). Both are visibly
2 3 1 4 ···n 2 1 3 4 ···n
in Sn . Moreover, (1 2 3) ◦ (1 2) = (1 3) while (1 2) ◦ (1 2 3) = (2 3). Thus,
(1 2 3) ◦ (1 2) 6= (1 2) ◦ (1 2 3), showing that Sn is not abelian.
4. Writing permutations as compositions of 2-cycles: Problem 18b

5. Even and odd permutations: Problem 9
6. Thinking of symmetry groups as permutation groups: Problem 40
Examples: Numbering the vertices of the triangle 1, 2, 3 in counterclockwise
order, a counterclockwise rotation of 120 degrees may be represented by
(1 2 3), meaning vertex 1 goes to where vertex 2 used to be, vertex 2 goes to
where vertex 3 used to be, and vertex 3 goes to where vertex 1 used to be.
A counterclockwise rotation of 240 degrees may be represented by (1 3 2).
The others are similar.
7. Proofs about even and odd permutations: Problems 11 (provide a proof–it’s short),
12, 15. Important–notice in 11 the permutations are cycles, but in 12 and 15 they can
be any permutations. These are particularly useful problems.
Problem 11.
Let n be a positive integer. Take any n-cycle, (a1 a2 , · · · an ).
Claim 1: If n is an odd integer, then (a1 a2 , · · · an ) is an even permutation.
Claim 2: If n is an even integer, then (a1 a2 , · · · an ) is an odd permutation.
By direct computation we know (a1 a2 , · · · an ) = (a1 an ) ◦ (a1 an−1 ) ◦ · · · ◦ (a1 a2 )
which is the composition of n − 1 2-cycles.
Assume n is an odd integer, then n − 1 is even. Therefore, (a1 a2 , · · · an )
is an even permutation by definition since it is the composition of an even
number of 2-cycles. That proves the first claim.
Assume n is an even integer, then n − 1 is odd. Therefore, (a1 a2 , · · · an ) is
an odd permutation by definition. That proves the second claim.
Problem 12. Repeated warning, do not assume α and β are cycles.

Assume α is an even permutation. Then, by definition of an even permuta-
tion, α = (b1 c1 ) ◦ (b2 c2 ) ◦ · · · ◦ (bk ck ) for some 2-cycles (b1 c1 ), (b2 c2 ), · · · , (bk ck )
where k is an even integer. Then
α−1 = [(b1 c1 ) ◦ (b2 c2 ) ◦ · · · ◦ (bk ck )]−1
= (bk ck )−1 ◦ (bk−1 ck−1 )−1 ◦ · · · ◦ (b1 c1 )−1 (by Shoes and Socks)
= (ck bk ) ◦ (ck−1 bk−1 ) ◦ · · · ◦ (c1 b1 ) (by problem 30, done earlier)
Therefore, since k is an even integer, α−1 is an even permutation.
(The odd case is similar.)
Problem 15. Half was done in class. The other half is similar.
8. Short answer problems. In the interest of time, full proofs are optional. Write enough
to explain your basic thinking, however.
(a) Problem 14
The first blank is completed this way: r + s is even. The second blank:
r + s + t is odd. (Those are obtained by decomposing the cycles into
the composition of 2-cycles in the usual way, and then counting the
number of 2-cycles in terms of r, s, and t.)
(b) Problems 24 and 25 (some discrete math!) (over ,→)
Problem 24 Count the number of elements of order 5 in S7 .
Let’s first figure out what elements of order 5 look like in S7 . By Rufini’s
Theorem 5.3, the lcm of the lengths of the cycles in the disjoint cycle
decomposition must be 5. Since 5 is prime, that means all the cycles have
lengths 1 or 5. We only have the numbers 1, 2, 3, 4, 5, 6, 7 in the domain,
so there are not enough elements to have more than 1 5-cycle. Thus, the
elements of order 5 are just the 5-cycles (technically, composed with 2 1-
cycles, but we don’t write those).
Now we use standard counting methods: There are 7 choices for the first
entry in a 5-cycle, 6 choices for the second entry, 5 choices for the third, 4
for the fourth, and 3 for the fifth. Making a total of 7 · 6 · 5 · 4 · 3. However,
each 5-cycle is counted 5 times in that calculation since we can write it by
starting at any of its entries. (Example: (1 2 3 4 5) = (2 3 4 5 1) = etc.)
Therefore, we have to divide by 5. Therefore, the number of elements of
order 5 in S7 is (7 · 6 · 5 · 4 · 3)/5 = 504.
9. (a) The set of all even permutations is a subgroup: Problem 13

Proof: Recall the set of even permutations in Sn is An , that is, An :=
{β ∈ Sn : β is even} (That was the definition stipulated in class). So we
want to show An ≤ Sn .
(subset) An ⊆ Sn because of the universal set of An .
(closure) Closure follows immediately from problem 15.
(identity) Since the identity is the composition of 0 2-cycles, it is even.
Therefore, it is in An .
(inverses) Problem 12 proved inverses.
(b) The set of all odd permutations a subgroup?: Problem 21
No. Closure fails by problem 15, which tells us the composition of two
odd permutations is even.
10. Prove Theorem 0.7 parts 2 & 3. Collaboration ban in effect for this problem.
This one won’t be on the midterm. I’ll be reading the solutions that you
submitted for homework.

344 CH 5 Solns W09 TEMP

Uploaded by

Copyright:

Available Formats

344 CH 5 Solns W09 TEMP

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

344 CH 5 Solns W09 TEMP

Uploaded by

Copyright:

Available Formats

MA344 Selected Chapter 5 Solutions Revised: Winter 2009

1. Composing permutations: Problem 17 (The author abbreviates β ◦ α as βα and writes

4. Writing permutations as compositions of 2-cycles: Problem 18b

Problem 12. Repeated warning, do not assume α and β are cycles.

9. (a) The set of all even permutations is a subgroup: Problem 13

You might also like