Symmetric Groups

S_n: permutations, cycle order = lcm, and parity.

The idea

Groups were not invented as an abstraction; they were invented as symmetries, and the symmetric group is the original one.

Definition (Symmetric group).

Fix $n$ objects. A permutation of them is a bijection from the collection to itself. Under composition the permutations form a group, the symmetric group $S_n$, with $n!$ elements.

Composing two permutations gives a permutation, undoing one gives a permutation, and doing nothing is an identity, which is why $S_n$ is a group. These are not one family among many: every finite group is a subgroup of some $S_n$.

To compute with a permutation you first need to write it down. Follow one object as it is moved, then moved again; with finitely many objects you must eventually come back to where you started. That carves the objects into cycles, and listing the cycles side by side records the permutation completely — this is cycle notation.

Two facts fall straight out of that picture. The first concerns the order of a permutation, the number of applications after which it first returns to the identity.

Proposition (Order of a permutation).

The order of a permutation is the least common multiple of the lengths of its cycles.

This is because a cycle of length $k$ returns everything it touches to its starting place after exactly $k$ applications, so all the cycles are back at once exactly at a common multiple of their lengths. And any cycle can be assembled out of swaps of two objects. How many swaps you use is not fixed, but whether that number is even or odd is — which splits $S_n$ into the even and the odd permutations.

Ways to work on it

• Walkthrough. Cycle notation, order as an lcm, and parity.
• Practice. Order of a permutation from its cycle type.
• Hardest. The alternating group A_n and parity.

Not sure where to start? Take the ten-question placement test.