Symmetric Groups II

Who can deny that life is not fair, nor easy, just a messy affair where we muddle along with glimpses of significant relationships, search of meaning and purpose? Who can justify that lies are abundant and spreading, news are mainly fake and driven by political and economic narratives, history is being twisted, trust is all gone, and we all know that something needs to be done? Who can deny that yesterday is gone, tomorrow is not promised, and we only have today? Who can rebuff that destiny is a bitch, money is king and sometimes even god, and life is but a dream, a worn out ship on troubled waters? Who can deny that I love you Bew like crazy, my sweet angel? Desperate verses IV, M. Anawim, #justtothepoint.

Theorem. Every permutation is a product of transpositions. In other words, every permutation α ∈ S_n, n > 1, is a product of transpositions or 2-cycles.

Proof.

By a previous result, every permutation on a finite set can be written or expressed as a product of disjoint cycles, that is, in the form, (a₁a₂…a_k)(b₁b₂…b_t)…(c₁c₂…c_s).

However, every permutation is a product of cycles: (a₁a₂...a_n) = (a₁a_n)(a₁a_n-1)...(a₁a₃)(a₁a₂)

And therefore, (a₁a₂…a_k)(b₁b₂…b_t)…(c₁c₂…c_s) = (a₁a_k)(a₁a_k-1)…(a₁a₂)(b₁b_t)(b₁b_t-1)…(b₁b₂)(c₁c_s)(c₁c_s-1)…(c₁c₂)∎

Examples:

• (12345) = (15)(14)(13)(12)
• (2745) = (25)(24)(27)
• (16)(253) = (16)(23)(25)

Definition. A permutation that can be written or expressed as a product of an even number of transpositions or 2-cycles is called an even permutation. A permutation that can be written or expressed as a product of an odd number of transpositions or 2-cycles is called an odd permutation.

Lemma. The identity permutation is an even permutation. An even permutation can be obtained as the composition of an even and only an even number of transpositions. More formally, if β₁β₂...β_n = e where the β's are transpositions or 2-cycles, then n is even (n % 2 = 0).

Proof.

• First notice that n ≠ 1 because a transposition could never be the identity.
• Suppose n = 2. Then, the lemma is obviously true.
• Suppose n > 2, and we proceed by induction.

β^n-1βⁿ can be expressed in one of the following forms:

1. e = (ab)(ab)
2. (ab)(bc) = (ac)(ab)
3. (ac)(cb) = (cb)(ab)
4. (ab)(cd) = (cd)(ab)

If we are in the first case, e = (ab)(ab) ⇒ β¹β²…β^n-2 = e. By induction hypothesis, n-2 < n, and therefore n-2 is even ⇒ n is even.

In the other cases, we replace the form of β^n-1βⁿ on the right by its counterpart on the left. We obtain a product of n transpositions where the rightmost occurrence of a is in the second place from the rightmost 2-cycle of the product. We repeat the process with β_n-2β_n-1 and the rightmost occurrence of a is in the third 2-cycle from the right of the product. This means that each time you apply any of these identities, the rightmost occurrence of a is one transposition further to the left.

Eventually either we will get two identical adjacent transpositions (ax)(ax) = id, so they disappear and we can apply induction to the shorter string of transpositions; or we end up with an “a” only appearing in the leftmost transposition of the entire product of transpositions, but such a product does not fix a, so it is not the identity, ⊥.

Theorem. A permutation cannot be written or expressed as a product of both an odd and an even number of transpositions or 2-cycles..

Proof. Let α = β₁β₂…β_r = ζ₁ζ₂…ζ_s

e = αα^-1 = ζ₁ζ₂…ζ_sβ_r^-1…β₂^-1β₁^-1 = [A transposition is its own inverse] ζ₁ζ₂…ζ_sβ_r…β₂β₁. By the previous theorem, r+s is even ⇒ r and s are both even or both odd.

Theorem. The alternating group of degree n, A_n, is the subgroup of all even permutations in the symmetric group S_n, A_n = {σ ∈ S_n | σ is even} ≤ S_n

Proof.

1. The identity permutation is an even permutation (Previous Lemma).
2. If α and β are even permutations, then β^-1 is even, because we just need to decompose β into an even number of transpositions and write the product backwards. Therefore, αβ^-1 is an even permutation (it is the product of two even products of transpositions), αβ^-1 ∈ A_n∎

   Let τ = (1243)(67), then τ^-1 = (76)(3421). Let σ = σ₁···σ_l, σ^-1 = σ_l^-1···σ₂^-1σ₁^-1 = σ_l···σ₂σ₁

Theorem. For n > 1, A_n has order n!/2, |A_n| = n/2.

Proof. Let A_n be the set of even permutations in S_n, and B_n be the set of odd permutations.

Let’s define a one-to-one function from A_n onto B_n, and therefore A_n and B_n has the same number of elements.

First, we define the function Φ: A_n → B_n, by Φ(α)=(12)α, α is even so it can be written or expressed as a product of an even number of transpositions, so (12)α ∈ B_n.

• is Φ a one-to-one function? Φ(α) = Φ(β) ⇒ (12)α = (12)β ⇒ [S_n is a group, and by the Cancellation property] α = β.

• is Φ onto? If α ∈ B_n, (12)^-1α = (12)α ∈ A_n ⇒ Φ((12)α) =(12)(12)α = α

• Hence, S_n is split equally in both even and odd permutations, |S_n| = n! = 2|A_n| ⇒ |A_n| = n!/2.

Exercises.

1. List the elements of A₄, |A₄| = 4!/2 = 12. A₄ = {() -identity-, (12)(34), (13)(24), (14)(23) -all 2 transpositions, we can’t include single transpositions, -all 3-cycles because they are a product of two transpositions- (123) = (13)(12), (132) = (12)(13) -they fix 4-, (142) = (12)(14), (124) -they fix 3-, (134), (143), -they fix 2- (234), (243) -they fix 1-}
2. The inverse of a permutation.

• τ = (1243)(67), τ^-1 = [Theorem of Sock and Shoes and σ=(a₁a₂···a_k), σ^-1=(a_ka_k-1···a₁), that is, σ written backwards, and σ^-1 = (σ₁···σ_l)^-1 = σ_l^-1···σ₂^-1σ₁^-1 ] (76)(3421) = [These cycles are disjoint] (1342)(67)

  σ: a₁ → a₂ → a₃··· a_k → a₁, then σ^-1: a_k → a_k-1 → a_k-2 ··· a₁ → a_k which is nothing more than σ written backwards.

• σ = (254), τ=(123)(45), σ^-1 =(452) = (245), τ^-1=(54)(321) = (321)(54) = (132)(45), σ^-1∘τ^-1=(245)∘(132)(45) = (1342)

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.