Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 37 ยท Cyclic and Permutation Groups

Symmetric Groups and Parity

Meet the symmetric group S_n, write permutations as transpositions, define even and odd permutations, and build the alternating group A_n of order n!/2.

The set of all permutations of {1, ..., n} under composition is a group, the symmetric group S_n. It has n! elements, is non-abelian for n โ‰ฅ 3, and holds a remarkable subgroup: the alternating group, built from the "even" permutations.

The group S_n

Composition of bijections is closed and associative, the identity permutation is the identity, and the inverse function of a bijection is an inverse. So S_n is a group of order n!.

| n | |S_n| | Abelian? | |---|---|---| | 1 | 1 | yes | | 2 | 2 | yes (it is โ„คโ‚‚) | | 3 | 6 | no | | 4 | 24 | no | | 5 | 120 | no |

Transpositions generate everything

A transposition swaps two elements. Every permutation is a product of transpositions, because a cycle can be split:

(aโ‚ aโ‚‚ aโ‚ƒ ... a_k) = (aโ‚ a_k)(aโ‚ a_{k-1}) ... (aโ‚ aโ‚‚).

For instance (1 2 3) = (1 3)(1 2) (apply (1 2) first). A cycle of length k is a product of k - 1 transpositions. The decomposition is not unique, but its parity is.

Even and odd permutations

A permutation is even if it is a product of an even number of transpositions, odd otherwise. A theorem says no permutation can be both. The idea: count inversions, the pairs i < j with ฯƒ(i) > ฯƒ(j). Swapping two entries changes the number of inversions by an odd amount, so the parity of the inversion count equals the parity of the number of transpositions. The sign is sgn(ฯƒ) = (-1)^(number of inversions).

Python Sign by inversions and by 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 second check says the sign map respects multiplication: even ร— even = even, even ร— odd = odd, odd ร— odd = even. This is a homomorphism S_n โ†’ {1, -1}, a concept formalized in chapter 5.

The alternating group

The even permutations form a subgroup A_n of S_n: the identity is even, the product of two evens is even, the inverse of an even is even. For n โ‰ฅ 2 exactly half of the n! permutations are even (multiplying by a fixed transposition pairs each even permutation with an odd one), so |A_n| = n!/2.

Python Build A_4 and tabulate orders in S_4

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โ‚„ has 1 identity, 9 elements of order 2 (six transpositions and three double transpositions), 8 of order 3 and 6 of order 4. Aโ‚„ keeps the identity, the 3 double transpositions and the 8 three-cycles, giving 12 elements. Notice Aโ‚„ has no elements of order 4, and (as we will prove with Lagrange in chapter 4) it has no subgroup of order 6 even though 6 divides 12.

Do not confuse "even length" with "even permutation". A 3-cycle has odd length but is an even permutation (two transpositions); a 2-cycle is odd. A k-cycle is even exactly when k is odd.

flowchart TB
    S["S_n<br/>n! permutations"] --> A["A_n<br/>even permutations<br/>n!/2 elements"]
    S --> O["odd permutations<br/>the other half"]

The alternating group is exactly the kernel of the sign map.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many elements does the alternating group Aโ‚… have?

    |A_n| = n!/2 = 120/2 = 60.
  2. 2. A 4-cycle is a product of how many transpositions?

    A k-cycle is a product of k - 1 transpositions; a 4-cycle is odd.
  3. 3. Which permutations are in A_n?

    A_n consists of the even permutations.
  4. 4. The sign of the product of two odd permutations is:

    (-1)(-1) = +1, so the product is even.

Summary

  • S_n, the group of all permutations of n objects, has order n! and is non-abelian for n โ‰ฅ 3.
  • Every permutation is a product of transpositions; its parity (even or odd) is well defined.
  • sgn(pq) = sgn(p) sgn(q).
  • The even permutations form the alternating group A_n of order n!/2.

Next: Cayley's Theorem