# 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 α ∈ Sn, 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, (a1a2…ak)(b1b2…bt)…(c1c2…cs).

However, every permutation is a product of cycles: (a1a2...an) = (a1an)(a1an-1)...(a1a3)(a1a2)

And therefore, (a1a2…ak)(b1b2…bt)…(c1c2…cs) = (a1ak)(a1ak-1)…(a1a2)(b1bt)(b1bt-1)…(b1b2)(c1cs)(c1cs-1)…(c1c2)∎

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 β1β2...β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βn 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) ⇒ β1β2…β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βn 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 α = β1β2…βr = ζ1ζ2…ζs

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

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

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 ∈ An

Let τ = (1243)(67), then τ-1 = (76)(3421). Let σ = σ1···σl, σ-1 = σl-1···σ2-1σ1-1 = σl···σ2σ1

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

Proof. Let An be the set of even permutations in Sn, and Bn be the set of odd permutations.

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

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

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

• is Φ onto? If α ∈ Bn, (12)-1α = (12)α ∈ An ⇒ Φ((12)α) =(12)(12)α = α

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

Exercises.

1. List the elements of A4, |A4| = 4!/2 = 12. A4 = {() -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 σ=(a1a2···ak), σ-1=(akak-1···a1), that is, σ written backwards, and σ-1 = (σ1···σl)-1 = σl-1···σ2-1σ1-1 ] (76)(3421) = [These cycles are disjoint] (1342)(67)

σ: a1 → a2 → a3··· ak → a1, then σ-1: ak → ak-1 → ak-2 ··· a1 → ak 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

This content is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. This post relies heavily on the following resources, specially on NPTEL-NOC IITM, Introduction to Galois Theory, Michael Penn, and Contemporary Abstract Algebra, Joseph, A. Gallian.
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.
Bitcoin donation