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 {1,2,…,n}\{1, 2, \ldots, n\} is a one-to-one and onto function from the set to itself. Under composition, all permutations form the symmetric group SnS_n, with n!n! elements.

Cycle notation. Follow where each number goes until it returns. The permutation 1→41 \to 4, 2→12 \to 1, 3→53 \to 5, 4→24 \to 2, 5→35 \to 3 is

(1 4 2)(3 5)(1\ 4\ 2)(3\ 5)

since 1→4→2→11 \to 4 \to 2 \to 1 and 3→5→33 \to 5 \to 3. A two-element cycle is a transposition.

Composition runs right to left, as for functions: in στ\sigma\tau, apply τ\tau 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

  1. How many elements does S4S_4 have?

    Answer

    2424

    Full solution

    4!=244! = 24.

  2. Write 1→31 \to 3, 2→22 \to 2, 3→53 \to 5, 4→14 \to 1, 5→45 \to 4 in cycle notation.

    Answer

    (1 3 5 4)(1\ 3\ 5\ 4)

    Full solution

    1→3→5→4→11 \to 3 \to 5 \to 4 \to 1, and 22 stays fixed.

  3. Find the inverse of (1 3 5 2)(1\ 3\ 5\ 2).

    Answer

    (1 2 5 3)(1\ 2\ 5\ 3)

    Full solution

    Reverse the cycle: each arrow points back the other way.

  4. Compute (1 2 3)(2 4)(1\ 2\ 3)(2\ 4) in S4S_4.

    Answer

    (1 2 4 3)(1\ 2\ 4\ 3)

    Full solution

    Apply (2 4)(2\ 4) first: 1→1→21 \to 1 \to 2, 2→4→42 \to 4 \to 4, 4→2→34 \to 2 \to 3, 3→3→13 \to 3 \to 1.

  5. Find the order of (1 2)(3 4 5 6)(1\ 2)(3\ 4\ 5\ 6).

    Answer

    44

    Full solution

    lcm⁡(2,4)=4\operatorname{lcm}(2, 4) = 4.

  6. Is (1 2 3 4)(1\ 2\ 3\ 4) even or odd?

    Answer

    Odd

    Full solution

    A 4-cycle is a product of 33 transpositions: (1 4)(1 3)(1 2)(1\ 4)(1\ 3)(1\ 2).

  7. How many elements does A4A_4 have?

    Answer

    1212

    Full solution

    Half of the 2424 permutations in S4S_4 are even.

  8. A student computes (1 2)(1 3)(1\ 2)(1\ 3) as (1 2 3)(1\ 2\ 3). What went wrong?

    Answer

    The product was read left to right; the answer is (1 3 2)(1\ 3\ 2).

    Full solution

    Composition applies the right-hand permutation first, as with f(g(x))f(g(x)).

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.

What to learn next