Symmetric group

by Patrick Stevens Jun 14 2016 updated Jun 17 2016

The symmetric groups form the fundamental link between group theory and the notion of symmetry.

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.


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.


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)$~$.

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.

%%%knows-requisite(Conjugacy class):

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. %%%

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).

%%%knows-requisite(Normal subgroup): In fact $~$A_n$~$ is a Normal subgroup of $~$S_n$~$, obtained by taking the quotient by the sign homomorphism. %%%


Patrick Stevens

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.