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 $Sym\left(X\right)$ for the set of permutations of the set $X$ (so its elements are functions).

Then $Sym\left(X\right)$ is a group under the operation of composition of functions; it is the symmetric group on $X$.

We write $S_n$ for $Sym\left(\right\{1,2,\dots ,n\left\}\right)$, 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 $$\left(\begin{array}{cccc}1& 2& \dots & n\\ \sigma \left(1\right)& \sigma \left(2\right)& \dots & \sigma \left(n\right)\end{array}\right)$$ 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

TODO: perhaps "cycle" should be its own page, with properties such as "inverse" and "order".

A $k$-cycle is a member of $S_n$ which moves $k$ elements to each other cyclically. That is, letting $a_1,\dots ,a_k$ be distinct in $\{1,2,\dots ,n\}$, a $k$-cycle $\sigma$ is such that $\sigma \left(a_i\right)=a_{i+1}$ for $1\le i<k$, and $\sigma \left(a_k\right)=a_1$, and $\sigma \left(x\right)=x$ for any $x\notin \{a_1,\dots ,a_k\}$.

We have a much more compact notation for $\sigma$ in this case: we write $\sigma =(a_1{a}_2\dots a_k)$. (If spacing is ambiguous, we put in commas: $\sigma =(a_1,a_2,\dots ,a_k)$.) Note that there are several ways to write this: $(a_1{a}_2\dots a_k)=(a_2{a}_3\dots a_k{a}_1)$, for example. It is conventional to put the smallest $a_i$ at the start.

Note also that a cycle's inverse is extremely easy to find: the inverse of $(a_1{a}_2\dots a_k)$ is $(a_k{a}_{k-1}\dots a_1)$.

For example, the double-row notation $$\left(\begin{array}{ccc}1& 2& 3\\ 2& 3& 1\end{array}\right)$$ is written as $\left(123\right)$ or $\left(231\right)$ or $\left(312\right)$ in cycle notation.

Not every element of $S_n$ is a cycle. For example, the following element of $S_4$ has order $2$ so could only be a $2$-cycle, but it moves all four elements: $$\left(\begin{array}{cccc}1& 2& 3& 4\\ 2& 1& 4& 3\end{array}\right)$$

However, it may be written as the composition of the two cycles $\left(12\right)$ and $\left(34\right)$: it is the result of applying one and then the other. Note that since the cycles are disjoint (having no elements in common), it doesn't matter in which order we perform them. (TODO: create a separate page proving this.) It is a very important fact that every permutation may be written as the product of disjoint cycles. (TODO: create separate page proving this.)

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.

TODO: more examples; give examples of multiplying non-disjoint cycles together.

TODO: Cayley's Theorem TODO: order of an element being the LCM of the orders of the cycles TODO: every element is a product of transpositions TODO: link to the alternating group (which should have this page as a requisite, and should contain "conjugacy class splits iff cycle type condition") TODO: a group action induces a permutation TODO: conjugacy class = cycle type TODO: example listing of the conjugacy classes of $S_5$