This sheet introduces permutations—bijections from a set to itself—and their properties. Permutations form the symmetric group , which is the prototypical example of a non-abelian group and the foundation for Galois theory.
Commentary. Permutations are one of the oldest and most important objects in algebra. They arise naturally in counting problems, geometry, and the study of polynomial equations. The fact that every group can be realized as a group of permutations (Cayley's Theorem, Sheet 5) makes permutations fundamental to all of group theory.
Definition of Permutations#
Definition 2.5.1. Let be a nonempty set. A permutation of is a bijection .
Definition 2.5.2. The set of all permutations of , with the operation of composition of functions, is called the symmetric group on , denoted or .
Definition 2.5.3. When , we write for the symmetric group on elements. The elements of are called permutations of degree .
Theorem 2.5.4. For any nonempty set , is a group under composition. (See Sheet 1.)
Theorem 2.5.5. The order of is .
Example 2.5.6. has elements: the identity, three transpositions, and two 3-cycles.
Exercise 2.5.7. Let . List all 6 permutations of . Write them in two-row notation.
Exercise 2.5.8. Show that is non-abelian for . (Hint: Compute and .)
Two-Row Notation#
Definition 2.5.9. A permutation can be written in two-row notation as:
Example 2.5.10. The permutation with , , is written:
Exercise 2.5.11. Write the permutation in two-row notation with the top row in order.
Exercise 2.5.12. Compute the product where:Is ?
Cycle Notation#
Definition 2.5.13. A cycle of length is a permutation that sends for , sends , and fixes all other elements.
Definition 2.5.14. A cycle of length 2 is called a transposition.
Definition 2.5.15. Two cycles are disjoint if they have no elements in common.
Theorem 2.5.16. Every permutation can be written uniquely (up to order) as a product of disjoint cycles.
Example 2.5.17. The permutationhas disjoint cycle decomposition .
Example 2.5.18. The cycle sends , , , , and fixes all other elements.
Exercise 2.5.19. Write the following permutation in disjoint cycle notation:
Exercise 2.5.20. Compute the product of cycles in . Write the result in disjoint cycle notation.
Exercise 2.5.21. Show that . (Hint: Compute the product of transpositions.)
Order of a Permutation#
Definition 2.5.22.0
Let be a permutation of a finite set. The order of , denoted is the smallest positive integer such that
where 1 denotes the identity permutation (i.e., the permutation that fixes every element).
If no such positive integer exists, the order is said to be infinite (though for permutations of a finite set, the order is always finite).
Theorem 2.5.22. The order of a cycle is .
Theorem 2.5.23. If is a product of disjoint cycles of lengths , then:
Example 2.5.24. The permutation has order .
Exercise 2.5.25. Find the order of .
Exercise 2.5.26. Find the order of .
Transpositions and Parity#
Definition 2.5.27. A transposition is a cycle of length 2, i.e., a permutation that swaps and and fixes all other elements.
Theorem 2.5.28. Every permutation can be written as a product of transpositions.
By exercise 2.521.
Definition 2.5.30. A permutation is even if it can be expressed as a product of an even number of transpositions. It is odd if it can be expressed as a product of an odd number of transpositions.
Theorem 2.5.31 (Well-Definedness). No permutation can be both even and odd.
多项式证法
Theorem 2.5.32. A cycle of length is even iff is odd. That is:
- A cycle of odd length is even.
- A cycle of even length is odd.
Example 2.5.33. is even (product of 2 transpositions). is odd (product of 3 transpositions).
Exercise 2.5.34. Determine whether the following permutations are even or odd:
(a)
(b)
(c)
The Alternating Group#
Definition 2.5.35. The set of all even permutations in forms a subgroup called the alternating group .
Theorem 2.5.36. For , the order of is .
Theorem 2.5.37. for .
Example 2.5.39. has order 12 and contains the Klein four-group .
Exercise 2.5.40. List all elements of .
Exercise 2.5.41. Show that is cyclic but is not.
Exercise 2.5.42. Prove that is generated by the set of all 3-cycles for .
Conjugacy in (need to refine the def of conjuacy"#
Theorem 2.5.43. Two permutations in are conjugate iff they have the same cycle type. That is, are conjugate iff their disjoint cycle decompositions have the same number of cycles of each length.
Example 2.5.44. In , and are conjugate (both have one 3-cycle and one 2-cycle).
Example 2.5.45. In , and are not conjugate (different cycle types).
Exercise 2.5.46. Find the conjugacy class of in . How many elements does it have?
Exercise 2.5.47. How many conjugacy classes are there in ? List them.
Generators of Def not clear enough#
Theorem 2.5.48. is generated by the set of all transpositions.
Theorem 2.5.49. is generated by .
Theorem 2.5.50. is generated by the transposition and the -cycle .
Theorem 2.5.51. is generated by the set of all 3-cycles.
Exercise 2.5.52. Show that is generated by and .
Exercise 2.5.53. Show that is generated by and .
Summary#
We have introduced:
- Permutations as bijections from a set to itself
- The symmetric group and its order
- Two-row notation and cycle notation
- Composition of permutations
- The order of a permutation (lcm of cycle lengths)
- Transpositions and parity (even/odd permutations)
- The alternating group
- Conjugacy in (same cycle type)
- Generators of and