# Symmetric group

The notion that group theory captures the idea of “symmetry” derives from the notion of the symmetric group, and the very important theorem due to Cayley that every group is a subgroup of a symmetric group.

# Definition

Let \(X\) be a set. A bijection \(f: X \to X\) is a *permutation* of \(X\).
Write \(\mathrm{Sym}(X)\) for the set of permutations of the set \(X\) (so its elements are functions).

Then \(\mathrm{Sym}(X)\) is a group under the operation of composition of functions; it is the *symmetric group on \(X\)*.
(It is also written \(\mathrm{Aut}(X)\), for the *automorphism group*.)

We write \(S_n\) for \(\mathrm{Sym}(\{ 1,2, \dots, n\})\), the *symmetric group on \(n\) elements*.

# Elements of \(S_n\)

We can represent a permutation of \(\{1,2,\dots, n\}\) in two different ways, each of which is useful in different situations.

## Double-row notation

Let \(\sigma \in S_n\), so \(\sigma\) is a function \(\{1,2,\dots,n\} \to \{1,2,\dots,n\}\). Then we write \($\begin{pmatrix}1 & 2 & \dots & n \\ \sigma(1) & \sigma(2) & \dots & \sigma(n) \\ \end{pmatrix}\)$ for \(\sigma\). This has the advantage that it is immediately clear where every element goes, but the disadvantage that it is quite hard to see the properties of an element when it is written in double-row notation (for example, “$\sigma$ cycles round five elements” is hard to spot at a glance), and it is not very compact.

## Cycle notation

Cycle notation is a different notation, which has the advantage that it is easy to determine an element’s order and to get a general sense of what the element does. Every element of \(S_n\) can be expressed in (disjoint) cycle notation in an essentially unique way.

## Product of transpositions

It is a useful fact that every permutation in a (finite) symmetric group may be expressed as a product of transpositions.

# Examples

The group \(S_1\) is the group of permutations of a one-point set. It contains the identity only, so \(S_1\) is the trivial group.

The group \(S_2\) is isomorphic to the cyclic group of order \(2\). It contains the identity map and the map which interchanges \(1\) and \(2\).

Those are the only two abelian symmetric groups. Indeed, in cycle notation, \((123)\) and \((12)\) do not commute in \(S_n\) for \(n \geq 3\), because \((123)(12) = (13)\) while \((12)(123) = (23)\).

The group \(S_3\) contains the following six elements: the identity, \((12), (23), (13), (123), (132)\). It is isomorphic to the dihedral group \(D_6\) on three vertices. (Proof.)

# Why we care about the symmetric groups

A very important (and rather basic) result is Cayley’s Theorem, which states the link between group theory and symmetry.

# Conjugacy classes of \(S_n\)

It is a useful fact that the conjugacy class of an element in \(S_n\) is precisely the set of elements which share its cycle type. (Proof.) We can therefore list the conjugacy classes of \(S_5\) and their sizes. <div>

# Relationship to the alternating group

The alternating group \(A_n\) is defined as the collection of elements of \(S_n\) which can be made by an even number of transpositions. This does form a group (proof).

Children:

- Cayley's Theorem on symmetric groups
The “fundamental theorem of symmetry”, forging the connection between symmetry and group theory.

- Cycle notation in symmetric groups
Cycle notation is a convenient way to represent the elements of a symmetric group.

- Disjoint cycles commute in symmetric groups
In cycle notation, if two cycles are disjoint, then they commute.

- Conjugacy class is cycle type in symmetric group
There is a neat characterisation of the conjugacy classes in the symmetric group on a finite set.

- Conjugacy classes of the symmetric group on five elements
The symmetric group on five elements is a group of just the right size to make a good example of a table of conjugacy classes.

- Transposition (as an element of a symmetric group)
A transposition is the simplest kind of permutation: it swaps two elements.

- Every member of a symmetric group on finitely many elements is a product of transpositions
This fact can often simplify arguments about permutations: if we can show that something holds for transpositions, and that it holds for products, then it holds for everything.

- The sign of a permutation is well-defined
This result is what allows the alternating group to exist.

- Sign homomorphism (from the symmetric group)
The sign homomorphism is how we extract the alternating group from the symmetric group.

Parents:

- Group
The algebraic structure that captures symmetry, relationships between transformations, and part of what multiplication and addition have in common.

It would be awesome to have the details written out of the case of the symmetric group on the empty set.

Request for comment: is the definition of “cycle” something that should be on its own page? They’re not about the symmetric group per se, but I’ve only heard of cycles being used in the context of symmetric groups.

For core/definition pages I think we want to have super modular content (easier browsing, lets people pick just the parts they want to learn, reduces page scope creep), so putting it on its own page is good. It’s a child of this page, which seems like the appropriate relationship.

I took the plunge and put it on its own page.