Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 37 ยท Cyclic and Permutation Groups

Permutations and Cycle Notation

Understand permutations as bijections, compose them, write them as disjoint cycles, compute their order with lcm, and code it all in Python.

A permutation of a set is a rearrangement of its elements. Permutations are the most important source of non-abelian groups, and a theorem of Cayley (a later lesson) says every group is hiding inside one of them. First we need a notation that makes permutations easy to compute with.

Permutations as bijections

A permutation of {1, 2, ..., n} is a bijection ฯƒ: {1,...,n} โ†’ {1,...,n}. Two-line notation lists inputs above outputs:

Text
ฯƒ = ( 1 2 3 4 5 )
    ( 3 1 2 5 4 )

This ฯƒ sends 1 โ†’ 3, 2 โ†’ 1, 3 โ†’ 2, 4 โ†’ 5, 5 โ†’ 4. There are n! permutations of n objects (n choices for where 1 goes, n-1 for 2, and so on).

Composition. ฯƒฯ„ means "apply ฯ„ first, then ฯƒ" (the convention for function composition used in this course, (ฯƒฯ„)(x) = ฯƒ(ฯ„(x))). Some books use the opposite order; always check the convention.

Cycle notation

The permutation above moves 1 โ†’ 3 โ†’ 2 โ†’ 1 and swaps 4 โ†” 5. We write it as the product of disjoint cycles:

ฯƒ = (1 3 2)(4 5).

A cycle (aโ‚ aโ‚‚ ... a_k) sends aโ‚ โ†’ aโ‚‚ โ†’ ... โ†’ a_k โ†’ aโ‚, and fixes everything else. Elements fixed by the permutation are usually omitted. The identity is written e or ().

Key facts:

  • Every permutation is a product of disjoint cycles, and this is unique up to the order of the cycles and starting point in each cycle.
  • Disjoint cycles commute.
  • A cycle of length k is a k-cycle; a 2-cycle is a transposition.

Computing in Python

Python Compose permutations and find their cycles

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two compositions differ, so permutation multiplication is not commutative.

The order of a permutation

For disjoint cycles, the order is the least common multiple of the cycle lengths: a cycle of length k returns to the start after k steps, and the whole permutation returns when all cycles do simultaneously. For example (1 2 3)(4 5) has order lcm(3, 2) = 6.

Python Order from cycle type

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The order alone does not pin down the cycle type: (1 2 3 4 5 6) and (1 2 3)(4 5) both have order 6. Always read the cycle lengths.

Writing the product by hand

To multiply (1 2 3) and (3 4) (right to left): follow 1: (3 4) fixes 1, then (1 2 3) sends it to 2, so 1 โ†’ 2. Follow 2: fixed by (3 4), then 2 โ†’ 3, so 2 โ†’ 3. Follow 3: (3 4) sends it to 4, then (1 2 3) fixes 4, so 3 โ†’ 4. Follow 4: (3 4) sends it to 3, then (1 2 3) sends 3 to 1, so 4 โ†’ 1. Result: (1 2 3 4).

flowchart LR
    A((1)) --> B((3)) --> C((2)) --> A
    D((4)) <--> E((5))

The permutation (1 3 2)(4 5): a 3-cycle and a 2-cycle on separate elements.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many permutations of {1, 2, 3, 4} are there?

    4! = 4 ยท 3 ยท 2 ยท 1 = 24.
  2. 2. What is the order of (1 2 3)(4 5)?

    The order is lcm of the cycle lengths 3 and 2, which is 6.
  3. 3. Which statement about disjoint cycles is true?

    Disjoint cycles move different elements, so the order of applying them does not matter.
  4. 4. What is a transposition?

    A transposition swaps two elements and fixes the rest.

Summary

  • A permutation is a bijection of a finite set; n objects have n! permutations.
  • Every permutation is a product of disjoint cycles, written uniquely up to ordering.
  • Disjoint cycles commute; general permutations do not.
  • The order of a permutation is the lcm of its cycle lengths.

Next: Symmetric Groups and Parity