This sheet introduces permutations—bijections from a set to itself—and their properties. Permutations form the symmetric group SnS_n, 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 XX be a nonempty set. A permutation of XX is a bijection σ:X→X\sigma: X \to X.

Definition 2.5.2. The set of all permutations of XX, with the operation of composition of functions, is called the symmetric group on XX, denoted Sym⁡(X)\operatorname{Sym}(X) or SXS_X.

Definition 2.5.3. When X={1,2,…,n}X = \{1, 2, \ldots, n\}, we write SnS_n for the symmetric group on nn elements. The elements of SnS_n are called permutations of degree nn.

Theorem 2.5.4. For any nonempty set XX, Sym⁡(X)\operatorname{Sym}(X) is a group under composition. (See Sheet 1.)

Theorem 2.5.5. The order of SnS_n is ∣Sn∣=n!|S_n| = n!.

Example 2.5.6. S3S_3 has 3!=63! = 6 elements: the identity, three transpositions, and two 3-cycles.

Exercise 2.5.7. Let X={1,2,3}X = \{1, 2, 3\}. List all 6 permutations of XX. Write them in two-row notation.

Exercise 2.5.8. Show that SnS_n is non-abelian for n≥3n \geq 3. (Hint: Compute (1 2)(1 3)(1 \ 2)(1 \ 3) and (1 3)(1 2)(1 \ 3)(1 \ 2).)


Two-Row Notation#

Definition 2.5.9. A permutation σ∈Sn\sigma \in S_n can be written in two-row notation as:σ=(12⋯nσ(1)σ(2)⋯σ(n)).\sigma = \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{pmatrix}.

Example 2.5.10. The permutation σ∈S3\sigma \in S_3 with σ(1)=2\sigma(1) = 2, σ(2)=3\sigma(2) = 3, σ(3)=1\sigma(3) = 1 is written:σ=(123231).\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}.

Exercise 2.5.11. Write the permutation σ=(12343142)\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{pmatrix} in two-row notation with the top row in order.

Exercise 2.5.12. Compute the product σ∘τ\sigma \circ \tau where:σ=(123213),τ=(123132).\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}, \qquad \tau = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}.Is σ∘τ=τ∘σ\sigma \circ \tau = \tau \circ \sigma?


Cycle Notation#

Definition 2.5.13. A cycle of length kk is a permutation (a1 a2 ⋯ ak)(a_1 \ a_2 \ \cdots \ a_k) that sends ai↦ai+1a_i \mapsto a_{i+1} for 1≤i<k1 \leq i < k, sends ak↦a1a_k \mapsto a_1, 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 permutationσ=(123456351624)\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 5 & 1 & 6 & 2 & 4 \end{pmatrix}has disjoint cycle decomposition (1 3)(2 5)(4 6)(1 \ 3)(2 \ 5)(4 \ 6).

Example 2.5.18. The cycle (1 3 5 2)(1 \ 3 \ 5 \ 2) sends 1↦31 \mapsto 3, 3↦53 \mapsto 5, 5↦25 \mapsto 2, 2↦12 \mapsto 1, and fixes all other elements.

Exercise 2.5.19. Write the following permutation in disjoint cycle notation:σ=(12345674567123).\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 4 & 5 & 6 & 7 & 1 & 2 & 3 \end{pmatrix}.

Exercise 2.5.20. Compute the product of cycles (1 2 3)(2 3 4)(1 \ 2 \ 3)(2 \ 3 \ 4) in S4S_4. Write the result in disjoint cycle notation.

Exercise 2.5.21. Show that (a1 a2 ⋯ ak)=(a1 ak)(a1 ak−1)⋯(a1 a2)(a_1 \ a_2 \ \cdots \ a_k) = (a_1 \ a_k)(a_1 \ a_{k-1}) \cdots (a_1 \ a_2). (Hint: Compute the product of transpositions.)


Order of a Permutation#

Definition 2.5.22.0
Let σ\sigma be a permutation of a finite set. The order of σ\sigma, denoted ∣σ∣|\sigma| is the smallest positive integer nn such that

σn=1\sigma^n=1

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 (a1 a2 ⋯ ak)(a_1 \ a_2 \ \cdots \ a_k) is kk.

Theorem 2.5.23. If σ=σ1σ2⋯σr\sigma = \sigma_1 \sigma_2 \cdots \sigma_r is a product of disjoint cycles of lengths k1,k2,…,krk_1, k_2, \ldots, k_r, then:∣σ∣=lcm⁡(k1,k2,…,kr).|\sigma| = \operatorname{lcm}(k_1, k_2, \ldots, k_r).

Example 2.5.24. The permutation σ=(1 2 3)(4 5)\sigma = (1 \ 2 \ 3)(4 \ 5) has order lcm⁡(3,2)=6\operatorname{lcm}(3, 2) = 6.

Exercise 2.5.25. Find the order of (1 2 3 4)(5 6 7)(1 \ 2 \ 3 \ 4)(5 \ 6 \ 7).

Exercise 2.5.26. Find the order of (1 2)(3 4 5 6)(1 \ 2)(3 \ 4 \ 5 \ 6).


Transpositions and Parity#

Definition 2.5.27. A transposition is a cycle of length 2, i.e., a permutation (i j)(i \ j) that swaps ii and jj and fixes all other elements.

Theorem 2.5.28. Every permutation can be written as a product of transpositions.

By exercise 2.521.

Example 2.5.29. (1 2 3 4)=(1 4)(1 3)(1 2)(1 \ 2 \ 3 \ 4) = (1 \ 4)(1 \ 3)(1 \ 2).

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 kk is even iff kk is odd. That is:

  • A cycle of odd length is even.
  • A cycle of even length is odd.

Example 2.5.33. (1 2 3)(1 \ 2 \ 3) is even (product of 2 transpositions). (1 2 3 4)(1 \ 2 \ 3 \ 4) is odd (product of 3 transpositions).

Exercise 2.5.34. Determine whether the following permutations are even or odd:
(a) (1 2 3 4 5)(1 \ 2 \ 3 \ 4 \ 5)
(b) (1 2)(3 4 5)(1 \ 2)(3 \ 4 \ 5)
(c) (1 2 3)(4 5)(1 \ 2 \ 3)(4 \ 5)


The Alternating Group#

Definition 2.5.35. The set of all even permutations in SnS_n forms a subgroup called the alternating group AnA_n.

Theorem 2.5.36. For n≥2n \geq 2, the order of AnA_n is ∣An∣=n!/2|A_n| = n!/2.

Theorem 2.5.37. An◃SnA_n \triangleleft S_n for n≥2n \geq 2.

Example 2.5.38. A3={ι,(1 2 3),(1 3 2)}≅Z3A_3 = \{\iota, (1 \ 2 \ 3), (1 \ 3 \ 2)\} \cong \mathbb{Z}_3.

Example 2.5.39. A4A_4 has order 12 and contains the Klein four-group V4={ι,(1 2)(3 4),(1 3)(2 4),(1 4)(2 3)}V_4 = \{\iota, (1 \ 2)(3 \ 4), (1 \ 3)(2 \ 4), (1 \ 4)(2 \ 3)\}.

Exercise 2.5.40. List all elements of A4A_4.

Exercise 2.5.41. Show that A3A_3 is cyclic but A4A_4 is not.

Exercise 2.5.42. Prove that AnA_n is generated by the set of all 3-cycles for n≥3n \geq 3.


Conjugacy in SnS_n (need to refine the def of conjuacy"#

Theorem 2.5.43. Two permutations in SnS_n are conjugate iff they have the same cycle type. That is, σ,τ∈Sn\sigma, \tau \in S_n are conjugate iff their disjoint cycle decompositions have the same number of cycles of each length.

Example 2.5.44. In S5S_5, (1 2 3)(4 5)(1 \ 2 \ 3)(4 \ 5) and (1 3 5)(2 4)(1 \ 3 \ 5)(2 \ 4) are conjugate (both have one 3-cycle and one 2-cycle).

Example 2.5.45. In S4S_4, (1 2)(3 4)(1 \ 2)(3 \ 4) and (1 2 3)(1 \ 2 \ 3) are not conjugate (different cycle types).

Exercise 2.5.46. Find the conjugacy class of (1 2 3)(1 \ 2 \ 3) in S4S_4. How many elements does it have?

Exercise 2.5.47. How many conjugacy classes are there in S3S_3? List them.


Generators of SnS_n Def not clear enough#

Theorem 2.5.48. SnS_n is generated by the set of all transpositions.

Theorem 2.5.49. SnS_n is generated by {(1 2),(1 3),…,(1 n)}\{(1 \ 2), (1 \ 3), \ldots, (1 \ n)\}.

Theorem 2.5.50. SnS_n is generated by the transposition (1 2)(1 \ 2) and the nn-cycle (1 2 3 ⋯ n)(1 \ 2 \ 3 \ \cdots \ n).

Theorem 2.5.51. AnA_n is generated by the set of all 3-cycles.

Exercise 2.5.52. Show that S3S_3 is generated by (1 2)(1 \ 2) and (1 2 3)(1 \ 2 \ 3).

Exercise 2.5.53. Show that A4A_4 is generated by (1 2 3)(1 \ 2 \ 3) and (1 2 4)(1 \ 2 \ 4).


Summary#

We have introduced:

  • Permutations as bijections from a set to itself
  • The symmetric group SnS_n 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 AnA_n
  • Conjugacy in SnS_n (same cycle type)
  • Generators of SnS_n and AnA_n