Symmetric Groups

This is not what it was meant to be, but my crash course in purgatory. I should have known better. I should have been wiser. The more things seems to change, the more they stay the same. Everything just keeps going round and round, people chasing the wind and clutching at clouds and shadows, an insane game of smoke and mirrors. Life is not just a mess mirage in a world ruled by chaos, lies, and deception, but a merry-go-round where we all go around in circles before the final curtains close. And there are never really happy endings, that’s not how the story goes, but love is always new, awesome, and makes the ride worthwhile, Desperate verses III, M. Anawim, #justtothepoint.

Let A be any nonempty set. A permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order or if the set is already ordered, a rearrangement of its elements. More formally, a permutation of a set A is a bijection from a set A onto itself (like a shuffle of the elements of the set), that is, a function that is both one-to-one and onto.

All permutations of a set A with n elements form a group under function composition. S_A = {f | f: A → A, bijective}. The symmetric group, denoted as S_A, is defined as the group of all permutations of a given set.In the particular case when A = {1, 2, 3,···, n} the symmetric group on A is denoted as S_n, the symmetric group of degree n.

Proof:

1. Closure. ∀π, σ ∈ S_n ⇒ πσ ∈ S_n because the composition of bijections is itself a bijection.
2. Since function composition is always associative, ° is associativity, ∀π, σ, η ∈ S, (πσ)η = π(ση).
3. Identity. The identity is defined by Id(a) = a, ∀a ∈ A.
4. The inverse of πσ is σ^-1π^-1.

Proposition: Let X be a finite, non-empty set. Then, |S_x| = |X|!

Proof. Figure 1.b.

Without the loss of generality, we may assume that X = {1, 2, 3, …, n}. The permutations of X -a finite set- are the injective functions of this set to itself. An injection function σ can send 1 to any of the n elements. However, there are n-1 choices for σ(2) -it can be any element of A except σ(1)-, and n-2 choices for σ(3) -it can be any element of A except σ(1) or σ(2)-, and so on. Thus, there are precisely n·(n-1)·(n-2)·…·1 = n! possible injective functions.

Example. Let X = {1, 2, 3}, |S_X| = 6 (Figure 1.c.)  

A convenient way to write a permutation is to write it in array form and show where each element goes (Figure 1.a.)

σ = $(\begin{smallmatrix}1 & 2 & 3 & 4 & 5 & 6\\ 3 & 2 & 5 & 1 & 4 & 6\end{smallmatrix}\bigr)$

This means that σ(1)=3, σ(2)=2, σ(3)=5, and so on.

Let σ = $(\begin{smallmatrix}1 & 2 & 3 & 4\\ 2 & 3 & 4 & 1\end{smallmatrix}\bigr)$ and η = $(\begin{smallmatrix}1 & 2 & 3 & 4\\ 1 & 3 & 4 & 2 \end{smallmatrix}\bigr)$. We can compose any two permutations since they have the same domain as codomain, and this composite will itself be a permutation, e.g, ση (first apply η and then σ; in other words, we need to read it from right to left ←) = $(\begin{smallmatrix}1 & 2 & 3 & 4\\ 2 & 4 & 1 & 3\end{smallmatrix}\bigr)$, e.g., ση(1)=σ(η(1))=σ(1)=2 (Figure 1.d.).  

σ = $(\begin{smallmatrix}1 & 2 & 3 & 4 & 5 & 6\\ 3 & 2 & 5 & 1 & 4 & 6\end{smallmatrix}\bigr)$. Permutations always have inverses since they are bijective. They are easily construct by reflecting horizontally the given permutation and reordering the elements, if necessary, e.g., σ^-1 = $(\begin{smallmatrix}1 & 2 & 3 & 4 & 5 & 6\\ 4 & 2 & 1 & 5 & 3 & 6\end{smallmatrix}\bigr)$ (Figure 1.e.)

If two arbitrary sets A and B have the same cardinality, |A| = |B|, then S_A ≋ S_B. That’s because the structure of the group S_A is concerned only with the number of elements in the set A, and not with the elements themselves.

Suppose that there are two sets A and B having the same cardinality, let f: A → B be a one-to-one function mapping from A onto B. We define the function ϕ: S_A → S_B, ∀σ ∈ S_A, then ϕ(σ) is the permutation σ’ ∈ S_B such that σ’(f(a)) = f(σ(a)).

Example: A = {1, 2, 3}, B = {a, b, c}, let f: A → B defined as f(1)=a, f(2)=b, f(3)=c. ϕ: S_A → S_B, $ϕ(\begin{smallmatrix}1 & 2 & 3\\ 2 & 3 & 1\end{smallmatrix}\bigr)=(\begin{smallmatrix}a & b & c\\ b & c & a\end{smallmatrix}\bigr).$

Therefore, we can take {1, 2, …, n} to be a prototype for a finite set A of n elements, e.g., S₃. This is also the group D₃ of symmetries of an equilateral triangle = { id (identity), two rotations (ρ₁, ρ₂), and three mirror images (μ₁, μ₂, μ₃)}.

$id = (\begin{smallmatrix}A & B & C\\ A & B & C\end{smallmatrix}) = (\begin{smallmatrix}1 & 2 & 3\\ 1 & 2 & 3\end{smallmatrix}), ρ_1 = (\begin{smallmatrix}A & B & C\\ B & C & A\end{smallmatrix}) = (\begin{smallmatrix}1 & 2 & 3\\ 2 & 3 & 1\end{smallmatrix}), ρ_2 = ρ_1^2 = (\begin{smallmatrix}1 & 2 & 3\\ 3 & 1 & 2\end{smallmatrix}), μ_1 = (\begin{smallmatrix}1 & 2 & 3\\ 1 & 3 & 2\end{smallmatrix}), μ_2 = (\begin{smallmatrix}1 & 2 & 3\\ 2 & 1 & 3\end{smallmatrix}) = ρ_1μ_1, μ_3 = (\begin{smallmatrix}1 & 2 & 3\\ 3 & 2 & 1\end{smallmatrix}) = ρ_1^2μ_1$

Notice that μ₁ρ₁ = $(\begin{smallmatrix}1 & 2 & 3\\ 3 & 2 & 1\end{smallmatrix})$ ≠ ρ₁μ₁, so therefore S₃ is non Abelian. Futhermore, μ₁ρ₁ = ρ₁²μ₁ = $(\begin{smallmatrix}1 & 2 & 3\\ 3 & 2 & 1\end{smallmatrix})$, and this relation can be used to compute other products, e.g., μ₁ρ₁² = (μ₁ρ₁)ρ₁ = (ρ₁²μ₁)ρ₁ = ρ₁²(μ₁ρ₁) = ρ₁²(ρ₁²μ₁) = ρ₁⁴μ₁ = ρ₁μ₁.

Definition. A cycle is a permutation which maps a finite set {a₁, a₂, …, a_n} by a₁ → a₂ → … → a_n → a₁, that is, it maps some elements (some subset of elements) to each other in a cyclic fashion, while fixing all others.

More generally, we say that a permutation σ ∈ S_X is a cycle of length k if ∃a₁, a₂, ... a_k ∈ X such that a₁ → a₂ → ... → a_k → a₁ and it fixes all other elements of X, and it is denoted or written as σ = (a₁a₂...a_k)

A cycle of length 2 is called a transposition. A transposition is a permutation that swaps two elements and leaves everything else fixed. Two cycles are disjoint if they have no common elements between them.

Examples:

• δ₁ = (1, 3) or sometimes written as (13) is the transposition that swaps 1 and 3 and leaves everything else fixed.
• μ₁ = (12)(34) and ρ₁ = (1234). Therefore, μ₁ρ₁ = (12)(34)(1234) = (1)(24)(3) = (24) - For convenience’s sake, we do not write cycles of length one.- = δ₂.
• σ = $(\begin{smallmatrix}1 & 2 & 3 & 4 & 5 & 6\\ 2 & 3 & 6 & 4 & 1 & 5\end{smallmatrix})=(12365)$ is a cycle of length 5 where the element 4 is fixed.
• σ = $(\begin{smallmatrix}1 & 2 & 3 & 4 & 5\\ 2 & 1 & 3 & 5 & 4\end{smallmatrix})=(12)(3)(45), τ =(\begin{smallmatrix}1 & 2 & 3 & 4 & 5\\ 5 & 4 & 1 & 2 & 3\end{smallmatrix})=(153)(24), στ = (12)(3)(45)(153)(24) = (14)(253)$

Properties of Permutations

Theorem. Every permutation on a finite set can be decomposed, expressed or written as a product of disjoint cycles, that is, no element is moved by both of them, e.g. (135) and (24) are disjoint cycles.

Proof. Let’s induct on the number of elements in the set A.

Case base. Let’s prove the result for a set with just one element. This is trivial, there is only one permutation, the identity, and it is the cycle {a}.

Suppose that a permutation on a set with less than n elements set can be written as a product of disjoint cycles. Let’s take a permutation on a set with n element, that is, σ ∈S_n.

Let m be the order of σ, a₁ ∈ A and consider the set Q = {a₁, σ(a₁), σ²(a₁),… σ^m-1(a₁)} being constructed as follows, a₂ = σ(a₁), a₃ = σ(σ(a₁)) = σ(a₂), and so on, until we arrive at a₁ = σ^m(a₁) for some m. We know that m exists because the sequence a₁, σ(a₁), σ²(a₁) must be finite since A is finite.

If Q = A, σ is the cycle and we are done. Otherwise, |A - Q| < n, and by the induction assumption, the permutation σ on A - Q can be written as a product of disjoint cycles, say η₁η₂…η_k.

And therefore the permutation σ on the whole set A can be written as a product of disjoint cycles, more specifically, as (a₁ σ(a₁) σ²(a₁)… σ^m-1(a₁))η₁η₂…η_k ∎

Examples:

• σ = $(\begin{smallmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7\\ 7 & 6 & 3 & 1 & 2 & 5 & 4\end{smallmatrix})=(174)(265)$ is a product of two disjoint 3-cycles.

• σ = (16527348), τ = (152468)(37), στ = (16527348)(152468)(37) = (1286)(457).

Disjoint Cycles Commute. If two cycles move different sets of elements, then their effects are independent and it does not matter in which order they’re applied. More formally, If two pair of cycles σ and η are disjoint, i.e, they do no have entries in common, then ση=ησ.

Proof. Suppose σ and η are disjoint cycles, σ = {a₁, a₂,…, a_m} and η = {b₁, b₂,…, b_n}, and {a₁, a₂,…, a_m} ∩ {b₁, b₂,…, b_n} = ∅. Let A = {a₁, a₂,…, a_m, b₁, b₂,…, b_n, c₁, c₂,…, c_s} where the c’s are the elements left fixed by both σ and η.

Then, ση(i) = ησ(i) ∀i∈A because (ση)(a_i) = σ(η(a_i)) =[η fixes all a_i, 1 ≤ i ≤ m] σ(a_i)= a_i+1 where a_m+1=a₁. (ησ)(a_i) = η(σ(a_i)) = η(a_i+1) =[η fixes all a_i, 1 ≤ i ≤ m] a_i+1

A similar argument shows that (ση)(b_i) = (ησ)(b_i).

Finally, (ση)(c_i) = σ(η(c_i)) = σ(c_i) = c_i. (ησ)(c_i) = η(σ(c_i)) = η(c_i) = c_i∎

Order of a permutation. The order of a permutation of a finite set A written in disjoint cycle form or representation is the least common multiple of the lengths of the cycles.

Proof:

• Case 1. Let |A| = n. If α is a permutation on A and can be represented as a cycle of length n, then it has order n. Therefore, the order of α is equal to the length of its cycle, i.e., |α| = n, and the result holds for this particular case.

• Case 2. Let us now suppose that α can be expressed as a product of two disjoint cycles, say α = α₁α₂ where α₁ and α₂ are disjoint cycles of lengths t₁ and t₂ respectively. |α| = t. We need to show that t = lcm (t₁, t₂).

Recall: lcm(t₁, t₂) = k ⇒ k = t₁s₁ = t₂s₂.

α^k = (α₁α₂)^k = [∴ disjoint cycles commute] α₁^kα₂^k = α₁^t₁s₁α₂^t₂s₂ = (α₁^t₁)^s₁(α₂^t₂)^s₂ = [A cycle of length n has order n] ee = e ⇒ |α| = t divides k = lcm(t₁, t₂).

Let α^t = (α₁α₂)^t = [∴ disjoint cycles commute] α₁^tα₂^t = e ⇒ α₁^t = α₂^-t. However, α₁ and α₂ are disjoint, they share no common symbol ⇒ α₁^t and α₂^-t share not common symbol either. If these two cycles are both equal and yet, they share no symbol, it follows that they are both the identity because every symbol that no appears in a permutation is fixed by it, so every symbol in α₁^t is fixed by α₂^-t and vice-versa.

Therefore, both t₁ and t₂ must divide t ⇒ lcm(t₁, t₂) divides t, too. Then, t = lcm(t₁, t₂) ∎

• The general case is quite similar. α = α₁α₂…α_r where α₁, α₂,… α_r are disjoint cycles of lengths m₁, m₂,…. and m_r respectively. |α| = t. We need to show that t = lcm (m₁, m₂,… m_r).

lcm (m₁, m₂,… m_r) = k ⇒ k = m₁s₁ = m₂s₂ = … = m_rs_r

α^k = (α₁α₂…α_r)^k = [∴ disjoint cycles commute] α₁^kα₂^k…α_r^k = α₁^m₁s₁α₂^m₂s₂…α_r^m_rs_r = (α₁^m₁)^s₁(α₂^m₂)^s₂…(α_r^m_r)^s_r= ee…e = e ⇒ |α| = t divides lcm(m₁, m₂, … m_r).

Let α^t = (α₁α₂…α_r)^t = [∴ disjoint cycles commute] α₁^tα₂^t…α_r^t = e. For the same reasons of two disjoint cycles (that is, α₁^t does not share any symbols with α₂^t, α₃^t …, and α_r^t, and every symbol that no appears in α₂^t, …, α_r^t is fixed by these cycles ⇒ α₁^t is the identity), α₁^t = α₂^t = … = α_r^t = e ⇒ m₁, m₂,… m_r divide t ⇒ lcm(m₁, m₂, … m_r) divides t ⇒ t = lcm(m₁, m₂, … m_r)∎

Examples:

• α = (123)(456) ⇒ |α| = lcm(3, 3) = 3.
• α = (12)(345) ⇒ |α| = lcm(2, 3) = 6.
• α = (12345) ⇒ |α| = 5.
• α = (1234)(567)(89) ⇒ |α| = lcm(4, 3, 2) = 12.
• α = (45)(237) ⇒ |α|=lcm(2, 3) = 6.
• α = $(\begin{smallmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 5 & 8 & 3 & 6 & 7 & 4 & 1 & 2\end{smallmatrix})$ = (157)(28)(46) ⇒ |α|=lcm(3, 2, 2) = 6.
• Let’s calculate |α¹⁰⁰⁰| where α = (138)(27)(4965) ⇒ |α| = lcm(3, 2, 4) = 12 ⇒ α¹⁰⁰⁰ = α^{1000 mod 12} = α⁴ ⇒ |α¹⁰⁰⁰| = |α⁴| = [Theorem. Let a be an arbitrary element of order n in a group G, and let k be a positive integer. Then, ⟨a^k⟩=⟨a^gcd(n,k)⟩ and |⟨a^k⟩| = $\frac{n}{gcd(n,k)}$] = $\frac{12}{gcd(12, 4)} = \frac{12}{4} = 3$

Definition. A transposition is a permutation which interchanges or swaps two elements and leaves everything else fixed. In other words, a transposition is a cycle of length 2, e.g., (2, 3) is the transposition that swaps 2 and 3 and leaves everything else fixed.

Bibliography

1. NPTEL-NOC IITM, Introduction to Galois Theory.
2. Algebra, Second Edition, by Michael Artin.
3. LibreTexts, Abstract and Geometric Algebra, Abstract Algebra: Theory and Applications (Judson).
4. Field and Galois Theory, by Patrick Morandi. Springer.
5. Michael Penn (Abstract Algebra), and MathMajor.
6. Contemporary Abstract Algebra, Joseph, A. Gallian.
7. Andrew Misseldine: College Algebra and Abstract Algebra.