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.)

Proof:
Identity: By definition 2.5.1, the identity bijection e=σ:X→X,σ(x)=xe=\sigma:X\to X,\sigma(x)=x must be in Sym(X)Sym(X). It also implies that Sym(X)Sym(X) is non empty.
Closure: α,β∈Sym(X),α⋅β\alpha, \beta \in Sym(X), \alpha \cdot \beta is still a bijection σ:X→X\sigma: X \to X .
Associativity: α,β,θ∈Sym(X)\alpha, \beta, \theta\in Sym(X).
[(α⋅β)⋅θ](x)=α(β(θ(x)))=[α⋅(β⋅θ)](x)[(\alpha \cdot \beta)\cdot \theta](x)=\alpha(\beta(\theta(x)))=[\alpha \cdot (\beta \cdot \theta)](x)
Inverse: for all α∈Sym(X)\alpha \in Sym(X), since it is bijection, there must exists α−1\alpha^{-1} such that α⋅α−1=e\alpha \cdot \alpha^{-1}=e
Therefore, For any nonempty set XX, Sym⁡(X)\operatorname{Sym}(X) is a group under composition.∎

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

Proof:
Suppose σ∈Sn,σ(1)→x1,σ(2)→x2…σ(n)→xn,xi≠xj, for all i≠j\sigma \in S_{n}, \sigma(1)\to x_{1}, \sigma(2)\to x_{2}\dots \sigma(n)\to x_{n},x_{i}\neq x_{j},\text{ for all }i\neq j.
Then there is nn possible values for x1x_{1}, n−1n-1 possible values for x2x_{2},…\dots, 11 possible value for xn.x_{n}.
Thus, the number of elements in SnS_{n} is n!n!.
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 product of transports.

(1,2,3);(1,3,2)=(2,3);(2,1,3)=(2,3)(1,3);(2,3,1)=(1,2)(1,3);(3,2,1)=(1,3)(1,2);(3,1,2)=(2,3)(1,2)(1,2,3);(1,3,2)=(2,3);(2,1,3)=(2,3)(1,3);(2,3,1)=(1,2)(1,3);(3,2,1)=(1,3)(1,2);(3,1,2)=(2,3)(1,2)

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).)

Proof:
For all SnS_n where n≥3n \geq 3:
(2,3,1),(3,2,1),(1,2),(1,3)∈Sn(2,3,1),(3,2,1),(1,2),(1,3) \in S_{n}
(2,3,1)=(1,2)(1,3)≠(3,2,1)=(1,3)(1,2)(2,3,1)=(1,2)(1,3) \neq(3,2,1)=(1,3)(1,2)
Thus, it is non-abelian.∎


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.

Proof:
Take any σ∈Sn\sigma \in S_{n}σ=(123…nσ(1)σ(2)σ(3)…σ(n))\sigma = \begin{pmatrix} 1 & 2 & 3 & \dots & n \\ \sigma(1) & \sigma(2) & \sigma(3) & \dots & \sigma(n) \end{pmatrix}Since a cycle (a1 a2 ⋯ ak)(a_1 \ a_2 \ \cdots \ a_k) always sends ak↦a1a_k \mapsto a_1,
We take a cycle starting with aa, the smallest element in {1,2,…n}\{ 1,2,\dots n \} that is not fixed: (a,σ(a),σ2(a),…σk−1(a)),where σk(a)=a(a,\sigma(a),\sigma^2(a),\dots \sigma^{k-1}(a)),\text{where }\sigma^k(a)=a, and since σ\sigma is bijection so 0<m≠n<k,σm(a)≠σn(a)0<m\neq n<k,\sigma^m(a)\neq \sigma^n(a). If we start with σt(a),t∈{0,1,…k−1}\sigma^t(a), t \in \{ 0,1,\dots 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(\sigma^p(a),\sigma^{p+1}(a),\dots,a, \dots \sigma^{p-1}(a)),\text{where }\sigma^k(a)=a.

Similarly, take another cycle starting with bb, the smallest non-fixed element among b≠σt(a),t∈{0,1,…k−1}b\neq \sigma^t(a), t\in \{ 0,1,\dots 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\sigma=C_{1}C_{2}\dots C_{n} is a product of disjoint cycles, and the only cycle containing aa is CiC_{i}.
Since it is a cycle, CiC_{i} would map a→σ(a)→⋯→σk−1(a),σk−1(a)→aa\to \sigma(a)\to\dots\to \sigma^{k-1}(a),\sigma^{k-1}(a)\to a. Therefore, CiC_{i} is exactly (a,σ(a),σ2(a),…σk−1(a)),where σk(a)=a(a,\sigma(a),\sigma^2(a),\dots \sigma^{k-1}(a)),\text{where }\sigma^k(a)=a. The same applies for other cycles.

Remarks: This cycle is unique for :

  1. aa is unique given a σ\sigma;
  2. If b≠σt(a),t∈{0,1,…k−1}b\neq \sigma^t(a), t\in \{ 0,1,\dots k-1 \}, then obviously a cycle invoving bb would not be able to function the same as (a,σ(a),σ2(a),…σk−1(a))(a,\sigma(a),\sigma^2(a),\dots \sigma^{k-1}(a)). In order words, this cycle must consist of only σt(a),t∈{0,1,…k−1}\sigma^t(a), t \in \{ 0,1,\dots k-1 \};

∎

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.)

Proof:
k=1k=1 is trivial.
Apparently for k=2k=2, (a1,a2)=(a1,a2)(a_{1},a_{2})=(a_{1},a_{2}).
Suppose for k=t−1k=t-1, (a1 a2 ⋯ at−1)=(a1 at−1)(a1 at−2)⋯(a1 a2)(a_1 \ a_2 \ \cdots \ a_{t-1}) = (a_1 \ a_{t-1})(a_1 \ a_{t-2}) \cdots (a_1 \ a_2).
Then for k=tk=t, (a1,at)(a1 at−1)(a1 at−2)⋯(a1 a2)=(a1,at)(a1 a2 ⋯ at−1)=(a1 a2 ⋯ at)(a_{1},a_{t})(a_1 \ a_{t-1})(a_1 \ a_{t-2}) \cdots (a_1 \ a_2)=(a_{1},a_{t})(a_1 \ a_2 \ \cdots \ a_{t-1})= (a_1 \ a_2 \ \cdots \ a_t).
Therefore, it holds for all k∈Z+k \in \mathbb{Z}_{+}∎


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)\sigma=(a_1 \ a_2 \ \cdots \ a_k) is kk.

Proof:
We prove by induction for all the 1≤t≤k1\leq t\leq k:σt=(a1a2…ak−tak−t+1akat+1at+2…aka1at).\sigma^t = \begin{pmatrix} a_{_{1}} & a_{2} & \dots & a_{k-t} & a_{k-t+1} & a_{k} \\ a^{t+1} & a^{t+2} & \dots & a^k & a^1 & a^{t} \end{pmatrix}.where we stipulate when ak+t=ata^{k+t}=a^t.

For t=1t=1, apparently it holds.
Suppose for 1≤t=m−1≤k1\leq t=m-1\leq k,σm−1=(a1a2…ak−m+1ak−m+2akamam+1…aka1am−1). .\sigma^{m-1} = \begin{pmatrix} a_{_{1}} & a_{2} & \dots & a_{k-m+1} & a_{k-m+2} & a_{k} \\ a^{m} & a^{m+1} & \dots & a^k & a^1 & a^{m-1} \end{pmatrix}.\,.

For t=mt=m,σm=σm−1⋅σ=(a1a2…ak−mak−m+1akam+1am+2…aka1am). .\sigma^{m} = \sigma^{m-1}\cdot \sigma=\begin{pmatrix} a_{_{1}} & a_{2} & \dots & a_{k-m} & a_{k-m+1} & a_{k} \\ a^{m+1} & a^{m+2} & \dots & a^k & a^1 & a^{m} \end{pmatrix}.\,.

Therefore, for all the 1≤t≤k1\leq t\leq k:σt=(a1a2…ak−tak−t+1akat+1at+2…aka1at).\sigma^t = \begin{pmatrix} a_{_{1}} & a_{2} & \dots & a_{k-t} & a_{k-t+1} & a_{k} \\ a^{t+1} & a^{t+2} & \dots & a^k & a^1 & a^{t} \end{pmatrix}.When t=kt=k, σk=(a1a2…ak−tak−t+1aka1a2…ak−tak−1ak).\sigma^k = \begin{pmatrix} a_{_{1}} & a_{2} & \dots & a_{k-t} & a_{k-t+1} & a_{k} \\ a_{1} & a_{2} & \dots & a_{k-t} & a_{k-1} & a_{k} \end{pmatrix}.

The order of a cycle σ=(a1 a2 ⋯ ak)\sigma=(a_1 \ a_2 \ \cdots \ a_k) is kk.∎