Abstract Algebra · Undergraduate
Permutation Groups and Cycle Notation
Quick answer
A permutation of {1, …, n} is a one-to-one rearrangement, and all of them together form the symmetric group Sₙ, with n! elements. Cycle notation such as (1 4 2)(3 5) records where each number goes: 1 to 4, 4 to 2, 2 back to 1, and 3 and 5 swap. Products are composed right to left, and the order matters: (1 2)(1 3) = (1 3 2) but (1 3)(1 2) = (1 2 3). The order of a permutation is the lcm of its cycle lengths, and every permutation is even or odd according to how many swaps build it.
What you'll learn
- Write a permutation in cycle notation
- Compose permutations and find inverses
- Find the order of a permutation from its cycle lengths
- Decide whether a permutation is even or odd
Rearrangements as a group
A permutation of is a one-to-one and onto function from the set to itself. Under composition, all permutations form the symmetric group , with elements.
Cycle notation. Follow where each number goes until it returns. The permutation , , , , is
since and . A two-element cycle is a transposition.
Composition runs right to left, as for functions: in , apply first.
Why every permutation splits into disjoint cycles
Start at any number and keep applying the permutation. Since there are finitely many numbers, you eventually repeat, and because the permutation is one-to-one, the first repeat must be the starting number: no two arrows point to the same place. So each number lies on exactly one closed loop, and the loops never share a number. Disjoint cycles move different numbers, so they commute, and the whole permutation returns to the identity when every cycle does at once: after the lcm of the cycle lengths.
Worked examples
Common mistakes
Practice problems
-
How many elements does have?
Answer
Full solution
.
-
Write , , , , in cycle notation.
Answer
Full solution
, and stays fixed.
-
Find the inverse of .
Answer
Full solution
Reverse the cycle: each arrow points back the other way.
-
Compute in .
Answer
Full solution
Apply first: , , , .
-
Find the order of .
Answer
Full solution
.
-
Is even or odd?
Answer
Odd
Full solution
A 4-cycle is a product of transpositions: .
-
How many elements does have?
Answer
Full solution
Half of the permutations in are even.
-
A student computes as . What went wrong?
Answer
The product was read left to right; the answer is .
Full solution
Composition applies the right-hand permutation first, as with .
Frequently asked questions
What is the symmetric group Sₙ?
The group of all permutations of {1, 2, …, n} under composition. It has n! elements and is not abelian for n ≥ 3.
How do you read cycle notation?
In (1 4 2), 1 goes to 4, 4 goes to 2, and 2 goes back to 1. Numbers not listed stay where they are.
In which order are permutations composed?
Right to left, like functions: in στ, apply τ first, then σ.
What is the order of a permutation?
The lcm of the lengths of its disjoint cycles. (1 2 3)(4 5) has order lcm(3, 2) = 6.
What makes a permutation even or odd?
Whether it can be written as an even or odd number of transpositions (two-element swaps). A cycle of length k is a product of k − 1 transpositions.