Permutation Groups: The Art of Rearrangement

 Permutation groups are where abstract algebra meets concrete action. Every time you shuffle cards or solve a Rubik's cube, you're working with permutations!

What is a Permutation?

A permutation of a set X is a bijection (one-to-one and onto function) from X to itself.

Simply put: it's a way to rearrange the elements.

Example: For {1, 2, 3}, one permutation is:

  • 1 → 2
  • 2 → 3
  • 3 → 1

We write this as (123) in cycle notation.

Cycle Notation

Instead of listing where each element goes, we write cycles:

(123) means: 1→2, 2→3, 3→1

(12)(34) means: 1↔2, 3↔4

(1) or just e is the identity (nothing moves)

Example: The permutation that swaps 1 and 3 while fixing 2: (13) or equivalently (13)(2), usually written as just (13)

The Symmetric Group S_n

S_n = the group of all permutations of {1, 2, 3, ..., n}

Order: |S_n| = n!

Examples:

  • S₃ has 3! = 6 elements
  • S₄ has 4! = 24 elements
  • S₅ has 5! = 120 elements

Elements of S₃

S₃ = {e, (12), (13), (23), (123), (132)}

Transpositions (swaps): (12), (13), (23) 3-cycles: (123), (132) Identity: e

Composition (Multiplication)

Permutations compose from right to left.

Example: (12)(123)

  • First apply (123): 1→2, 2→3, 3→1
  • Then apply (12): swap 1 and 2

Result:

  • 1 → 2 (from 123) → 1 (from 12) = 1
  • 2 → 3 (from 123) → 3 (stays) = 3
  • 3 → 1 (from 123) → 2 (from 12) = 2

So (12)(123) = (23)

Key Properties

Property 1: Every permutation can be written as a product of transpositions.

Property 2: S_n is non-abelian for n ≥ 3.

Check: (12)(123) = (23) but (123)(12) = (13) ✗

Property 3: Order of a cycle = length of the cycle

  • (123) has order 3
  • (12) has order 2
  • (1234) has order 4

Even and Odd Permutations

Even permutation: Can be written as a product of an even number of transpositions

Odd permutation: Product of an odd number of transpositions

Example:

  • (123) = (12)(23) → even (2 transpositions)
  • (12) → odd (1 transposition)

The Alternating Group A_n

A_n = subgroup of S_n containing only even permutations

Order: |A_n| = n!/2

A₃ = {e, (123), (132)} has order 3 A₅ is the smallest non-abelian simple group!

Practice Problem

Question: What is (123)(12) in S₃?

Answer: (13)

Solution:

  • 1 → 2 (from 12) → 3 (from 123) = 3
  • 2 → 2 (from 12) → 3 (from 123) = 3... wait.

Let me redo: Apply right to left!

  • 1 → 1 (from 12) → 2 (from 123)
  • 2 → 1 (from 12) → 2 (from 123) → 3
  • 3 → 3 (from 12) → 1 (from 123)

So: 1→2, 2→3, 3→1... that's (123).

Actually, let me be more careful: (123)(12) means first (12), then (123)

  • Start with 1: (12) sends 1→2, then (123) sends 2→3. Final: 1→3
  • Start with 2: (12) sends 2→1, then (123) sends 1→2. Final: 2→2
  • Start with 3: (12) fixes 3, then (123) sends 3→1. Final: 3→1

Result: 1→3, 2→2, 3→1, which is (13)

Why Permutation Groups Matter

Applications:

  • Rubik's Cube: Each move is a permutation
  • Cryptography: Encryption algorithms use permutations
  • Sorting Algorithms: Computer science studies permutation complexity
  • Chemistry: Molecular symmetries
  • Galois Theory: Solving polynomial equations!

Fun Fact

Every finite group is isomorphic to a subgroup of some S_n!

This is Cayley's Theorem – permutation groups are universal!

Quick Tips

  1. Always compose right to left
  2. Disjoint cycles commute: (12)(34) = (34)(12)
  3. Inverse of (abc...): reverse the cycle → (...cba)
  4. Order of disjoint cycles: LCM of individual orders

Permutation groups bridge abstract algebra and concrete computation. They're fundamental to understanding group structure and appear everywhere from puzzles to physics!

For more examples and problem-solving with permutations, check out my YouTube channel "Maths Mastery with Dr. Upasana P Taneja"!

Rearrange with purpose, compute with structure!
Dr. Upasana P Taneja

Comments

Post a Comment

Popular posts from this blog

The One-Step Subgroup Test: Why Check Three When One Will Do?

  During my years of teaching group theory, I've noticed that students often get overwhelmed when verifying subgroups. They diligently check closure, identity, and inverses separately – which is correct but sometimes unnecessarily tedious. That's when I introduce them to one of my favorite shortcuts: the One-Step Subgroup Test! The Traditional Way vs. The Smart Way Traditional approach: Check three separate conditions Closure under the operation Contains the identity element Contains inverse of every element One-Step Test: Check just ONE condition! The One-Step Subgroup Test Theorem For a non-empty subset H of group G: H is a subgroup of G if and only if for all a, b ∈ H, we have ab⁻¹ ∈ H. That's it! Just one condition to check instead of three. Why Does This Work? The beauty lies in how this single condition automatically ensures all three requirements: Step 1 - Identity: Take any element a ∈ H. Since aa⁻¹ = e must be in H, we get the identity! Step 2 - Inverses: For any a...
Read more

Understanding Groups: A Journey Through Algebraic Structures

  Group theory is one of the most elegant and fundamental branches of abstract algebra, providing a framework for understanding symmetry, structure, and operations across mathematics. At its heart lies the concept of a group, but to truly appreciate groups, we need to understand the algebraic structures that lead up to them. Let's embark on this journey, starting with the simplest structures and building our way up to the rich world of groups. https://youtu.be/YKkfgZWqbfA?si=0Zx-hZegRW7LhuDe Watch this video for Explanation with examples and MCQs.  The Foundation: Semigroup A semigroup is perhaps the most basic algebraic structure we encounter. It consists of a set equipped with a single binary operation that satisfies just one crucial property. Definition A semigroup is a set S together with a binary operation * such that: Associativity: For all a, b, c ∈ S, we have (a * b) * c = a * (b * c) That's it! This single requirement might seem modest, but it captures something funda...
Read more

Cyclic vs Non-Cyclic Groups: The Key Results

 After years of teaching group theory, I've found that students truly understand groups when they grasp the fundamental differences between cyclic and non-cyclic groups. Let me share the most important theorems you need to know! Essential Results on Cyclic Groups Result 1: Every Cyclic Group is Abelian Theorem : If G is cyclic, then G is abelian. Proof : Let G = ⟨g⟩. Any two elements are g^m and g^n. Then g^m · g^n = g^(m+n) = g^(n+m) = g^n · g^m ✓ Important : The converse is FALSE! Not every abelian group is cyclic. Counterexample : V₄ = Z₂ × Z₂ is abelian but NOT cyclic. Result 2: Every Subgroup of a Cyclic Group is Cyclic Theorem : If G is cyclic and H ≤ G, then H is cyclic. Proof Sketch : Let G = ⟨g⟩. If H = {e}, then H is cyclic. Otherwise, take the smallest positive integer m such that g^m ∈ H. Then H = ⟨g^m⟩. Example : In Z₁₂ = ⟨1⟩: H = {0, 4, 8} = ⟨4⟩ is cyclic H = {0, 3, 6, 9} = ⟨3⟩ is cyclic Result 3: Classification of Cyclic Groups Theorem : Every cyclic g...
Read more