This sheet introduces permutations—bijections from a set to itself—and their properties. Permutations form the symmetric group Sn, 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 2.5.1. Let X be a nonempty set. A permutation of X is a bijection σ:X→X.
Definition 2.5.2. The set of all permutations of X, with the operation of composition of functions, is called the symmetric group on X, denoted Sym(X) or SX.
Definition 2.5.3. When X={1,2,…,n}, we write Sn for the symmetric group on n elements. The elements of Sn are called permutations of degree n.
Theorem 2.5.4. For any nonempty set X, Sym(X) is a group under composition. (See Sheet 1.)
Proof:
Identity: By definition 2.5.1, the identity bijection e=σ:X→X,σ(x)=x must be in Sym(X). It also implies that Sym(X) is non empty.
Closure: α,β∈Sym(X),α⋅β is still a bijection σ:X→X .
Associativity: α,β,θ∈Sym(X). [(α⋅β)⋅θ](x)=α(β(θ(x)))=[α⋅(β⋅θ)](x)
Inverse: for all α∈Sym(X), since it is bijection, there must exists α−1 such that α⋅α−1=e
Therefore, For any nonempty set X, Sym(X) is a group under composition.∎
Proof:
Suppose σ∈Sn,σ(1)→x1,σ(2)→x2…σ(n)→xn,xi=xj, for all i=j.
Then there is n possible values for x1, n−1 possible values for x2,…, 1 possible value for xn.
Thus, the number of elements in Sn is n!.
The order of Sn is ∣Sn∣=n!.∎
Example 2.5.6.S3 has 3!=6 elements: the identity, three transpositions, and two 3-cycles.
Exercise 2.5.7. Let X={1,2,3}. List all 6 permutations of X. Write them in product of transports.
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.
Proof:
Take any σ∈Snσ=(1σ(1)2σ(2)3σ(3)……nσ(n))Since a cycle (a1a2⋯ak) always sends ak↦a1,
We take a cycle starting with a, the smallest element in {1,2,…n} that is not fixed: (a,σ(a),σ2(a),…σk−1(a)),where σk(a)=a, and since σ is bijection so 0<m=n<k,σm(a)=σn(a). If we start with σt(a),t∈{0,1,…k−1} , the cycle would remain the same although in a different form (σp(a),σp+1(a),…,a,…σp−1(a)),where σk(a)=a.
Similarly, take another cycle starting with b, the smallest non-fixed element among b=σt(a),t∈{0,1,…k−1}, which is disjoint with the cycle above.
Keep taking cycles this way until no more cycles can be taken, and multiply them together.
Now we have proved that every permutation can be written as a product of disjoint cycles.
Uniqueness:
Suppose σ=C1C2…Cn is a product of disjoint cycles, and the only cycle containing a is Ci.
Since it is a cycle, Ci would map a→σ(a)→⋯→σk−1(a),σk−1(a)→a. Therefore, Ci is exactly (a,σ(a),σ2(a),…σk−1(a)),where σk(a)=a. The same applies for other cycles.
Remarks: This cycle is unique for :
a is unique given a σ;
If b=σt(a),t∈{0,1,…k−1}, then obviously a cycle invoving b would not be able to function the same as (a,σ(a),σ2(a),…σk−1(a)). In order words, this cycle must consist of only σt(a),t∈{0,1,…k−1};
∎
Example 2.5.17. The permutationσ=(132531465264)has disjoint cycle decomposition (13)(25)(46).
Example 2.5.18. The cycle (1352) sends 1↦3, 3↦5, 5↦2, 2↦1, and fixes all other elements.
Exercise 2.5.19. Write the following permutation in disjoint cycle notation:σ=(14253647516273).
Exercise 2.5.20. Compute the product of cycles (123)(234) in S4. Write the result in disjoint cycle notation.
Exercise 2.5.21. Show that (a1a2⋯ak)=(a1ak)(a1ak−1)⋯(a1a2). (Hint: Compute the product of transpositions.)
Proof: k=1 is trivial.
Apparently for k=2, (a1,a2)=(a1,a2).
Suppose for k=t−1, (a1a2⋯at−1)=(a1at−1)(a1at−2)⋯(a1a2).
Then for k=t, (a1,at)(a1at−1)(a1at−2)⋯(a1a2)=(a1,at)(a1a2⋯at−1)=(a1a2⋯at).
Therefore, it holds for all k∈Z+∎
Definition 2.5.22.0
Let σ be a permutation of a finite set. The order of σ, denoted ∣σ∣ is the smallest positive integer n such that
σ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).