Skip to content
Tutorials Center
My learning

Topics

Lesson 53 of 68 ยท Algebraic Structures and Boolean Algebra

Permutation Groups: Cycles, Transpositions, Parity and Conjugation

Work with permutations in cycle notation, factor them into transpositions, decide even or odd, find orders, use conjugation and inner automorphisms, and apply parity to sliding puzzles.

Groups and Symmetry showed that the permutations of n objects form the symmetric group S_n. Permutation groups are the most important concrete groups: Cayley's theorem says every finite group is a subgroup of some S_n, so understanding permutations means understanding all finite groups. This lesson gives you the working toolkit: cycle notation, factoring into transpositions, even and odd permutations, orders, and conjugation.

Cycle notation

Writing a permutation as a table of images is clumsy. Cycle notation is shorter. Take the permutation of {1, ..., 6} that sends 1 -> 3, 3 -> 5, 5 -> 1, 2 -> 6, 6 -> 2, 4 -> 4. Follow 1 and you get the loop 1 -> 3 -> 5 -> 1, written (1 3 5). Follow 2: (2 6). Vertex 4 stays put: a fixed point, usually omitted. So the permutation is (1 3 5)(2 6).

Every permutation splits into disjoint cycles, and disjoint cycles commute. This cycle decomposition is unique up to the order of the cycles and the starting point inside each cycle. The list of cycle lengths, here 3 + 2 + 1, is the cycle type.

To multiply permutations, apply them right to left (as with function composition), tracking where each element travels.

Order of a permutation: the smallest k > 0 with p^k = identity is the least common multiple of its cycle lengths. For (1 3 5)(2 6) the order is lcm(3, 2) = 6.

Transpositions and parity

A transposition is a 2-cycle (a b): it swaps two elements. Every permutation is a product of transpositions, because a cycle factors as

Text
(a1 a2 a3 ... ak) = (a1 ak) ... (a1 a3)(a1 a2)

so a k-cycle needs k - 1 transpositions. The factorization is not unique, but the parity (evenness or oddness) of the number of transpositions is: a permutation is either always written with an even number of swaps or always with an odd number. That makes the sign well defined:

Text
sign(p) = (-1)^(n - c)      where c is the number of cycles, counting fixed points

Equivalently, a k-cycle is even when k is odd. The sign is multiplicative, sign(pq) = sign(p) sign(q), which makes it a group homomorphism from S_n onto {+1, -1}. Its kernel, the set of even permutations, is a subgroup called the alternating group A_n, of order n!/2.

Python Cycles, parity, order and the alternating group

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.

S_4 is not abelian, and its elements have orders 1, 2, 3 and 4. For S_7 the largest possible order is 12, from a 4-cycle together with a 3-cycle, not from a 7-cycle (order 7): the product of different cycle lengths can beat a single long cycle.

Conjugation and inner automorphisms

Take a permutation p and any g in the group. The permutation g p g^-1 is the conjugate of p by g. Conjugation has a beautiful interpretation: it relabels the points. If p = (a b c), then g p g^-1 = (g(a) g(b) g(c)). So conjugate permutations always have the same cycle type, and in S_n two permutations are conjugate if and only if they have the same cycle type.

For a fixed g, the map x -> g x g^-1 is an automorphism of the group, called an inner automorphism. All inner automorphisms form a group Inn(G). The identity inner automorphism arises from every element of the center Z(G) (the elements that commute with everything), so |Inn(G)| = |G| / |Z(G)|. For abelian groups every inner automorphism is trivial.

Python Conjugation preserves cycle type; counting inner automorphisms

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.

Parity in action: the sliding puzzle

Parity decides real puzzles. In a sliding-tile puzzle every move swaps the blank with a neighboring tile, which acts as a transposition on the arrangement. On a board with an odd number of columns, a move never changes the parity of the permutation of the tiles (a vertical move shifts a tile across an even number of other tiles, so an even number of inversions change). So only half of all arrangements can be reached from the solved position. The famous Sam Loyd "14-15" puzzle with two tiles swapped is therefore unsolvable.

Python Which 2x3 sliding-puzzle positions are reachable?

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 reachable set has exactly 360 elements, half of 720, and it coincides with the arrangements of even parity. In a game with an even number of columns the rule shifts to include the row of the blank, but the principle is the same.

More uses

  • Permutation ciphers: a transposition cipher rearranges letters by a permutation; the order of the permutation tells you after how many repeated encryptions you get the plaintext back.
  • Card shuffling: a riffle shuffle is a permutation of the deck; its order says how many repeats restore the original order (eight perfect out-shuffles do it for 52 cards).
  • Symmetry and chemistry: permutations of atoms or faces describe the symmetries of molecules and cubes; Burnside's lemma counts arrangements up to those symmetries.
  • Sorting: the number of inversions of a permutation is the number of adjacent swaps bubble sort needs; its parity is the sign.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the order of the permutation (1 2 3)(4 5) in S5?

    The order of a permutation is the lcm of its cycle lengths: lcm(3, 2) = 6.
  2. 2. A 4-cycle written as a product of transpositions uses how many, and is it even or odd?

    A k-cycle needs k - 1 transpositions. Three is odd, so a 4-cycle is an odd permutation.
  3. 3. How many elements does the alternating group A_5 have?

    A_n has n!/2 elements, so A_5 has 120/2 = 60.
  4. 4. Two permutations in S_n are conjugate exactly when:

    Conjugation relabels the points, so cycle lengths are preserved, and any two permutations with equal cycle type can be mapped to each other by some relabeling.
  5. 5. If the center of a group G has 2 elements and |G| = 8, how many inner automorphisms does G have?

    |Inn(G)| = |G| / |Z(G)| = 8 / 2 = 4.

Summary

  • Every permutation factors uniquely into disjoint cycles; the cycle type and the order (the lcm of the cycle lengths) follow immediately.
  • Every permutation is a product of transpositions, and the parity of their number is fixed; sign(p) = (-1)^(n - c).
  • Even permutations form the alternating group A_n of order n!/2.
  • Conjugation relabels points, preserves cycle type, and gives the inner automorphisms, |Inn(G)| = |G| / |Z(G)|.
  • Parity explains why only half of the sliding-puzzle positions are reachable.

Next: Group Homomorphisms.