Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Symmetric group

The symmetric group $S_{n}$ is defined to be the group of all permutations of $n$ objects. More generally, the symmetric group of a set $M$, denoted $S_M$, $\mathfrak{S}_M$, or $\text{Sym}(M)$, is the group of permutations on $M$. A subgroup of the symmetric group on $M$ is sometimes called a permutation group on $M$. In this context, a permutation is to be thought of as a bijective function from a set of size $n$ to itself, and the group operation is composition of functions.

The symmetric group is of interest in many different branches of mathematics, especially combinatorics. (This is in part due to the various different representations of permutations: as functions, as products of cycles, as sequences or words, etc.) Knowledge of the symmetric group $S_{n}$ can also be crucial in such areas as Galois theory. For example, an important theorem in Galois theory is that the Galois group of the general polynomial equation of degree $n$ is $S_{n}$, and this can be used to prove that polynomial equations of degree five and higher are unsolvable through the use of elementary arithmetic and root extractions.

The study of symmetric groups is also interesting because every group is isomorphic to a permutation group, i.e., a subgroup of a symmetric group. Indeed, if $G$ is a group, then for $a \in G$, the mapping $x \mapsto ax$ is a permutation of $G$. Thus symmetric groups can be considered universal with respect to subgroups, just as free groups can be considered universal with respect to quotient groups.

Representations of Finite Permutations

Let $\sigma$ be an element of $\mathfrak{S}_n$. One way to denote $\sigma$ is as \[\begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{pmatrix}\] So for instance, with $n=6$, we might have \[\sigma_1 = \begin{pmatrix} 1 & 2&3&4&5&6 \\ 5&4&1&2&3&6 \end{pmatrix} .\] In the more concise cycle notation, we represent a cycle $\zeta$ of order $k$ as \[\begin{pmatrix} x & \zeta(x) & \zeta^2(x) & \cdots & \zeta^{k-1}(x) \end{pmatrix},\] for some arbitrary $x$ in the support of $x$; and we write an arbitrary permutation as a composition of cycles. Thus we may have \[\sigma_1 = \begin{pmatrix} 1&5&3 \end{pmatrix} \begin{pmatrix} 2&4 \end{pmatrix} .\] This notation is concise; it lends itself to easy computation of products and inverses.

Finally, we may represent a permutation as a permutation matrix, i.e., the matrix that maps $\begin{pmatrix} 1 \\ 2 \\ \vdots \\ n \end{pmatrix}$ to $\begin{pmatrix} \sigma(1) \\ \sigma(2) \\ \vdots \\ \sigma(n) \end{pmatrix}$. An $n\times n$ matrix is a permutation matrix if and only if all its entries are zeros and ones, each column has exactly one 1, and each row has exactly one 1. In this instance, we have \[\sigma_1 = \begin{bmatrix} 0&0&0&0&1&0 \\ 0&0&0&1&0&0 \\ 1&0&0&0&0&0 \\ 0&1&0&0&0&0 \\ 0&0&1&0&0&0 \\ 0&0&0&0&0&1 \end{bmatrix} .\]

In the next two sections, $M$ will represent a finite set.

Transpositions and Generators

A transposition is a cycle whose support has two elements. A transposition whose support is $\{a,b\}$ may be denoted $\tau_{a,b}$. Evidently, every transposition is its own inverse.

In this section and the next one, $M$ will represent a finite set.

Theorem 1. The symmetric group $\mathfrak{S}_M$ is generated by its transpositions.

Proof. We induct on $|M|$. For our base case, $n=1$, the theorem is trivial. Now, suppose that $\sigma$ is an element of $\mathfrak{S}_M$. Let $x$ be an arbitrary element of $M$. Let $G$ be the subgroup of elements of $\mathfrak{S}_M$ for which $\sigma(x)$ is a fixed point. Evidently, $G$ is isomorphic to $\mathfrak{S}_{M \setminus \{x\}}$ by restrictions of mappings, so by inductive hypothesis, it is generated by its transpositions. Then $\sigma = \sigma' \circ \tau_{x, \sigma(x)}$, for some permutation $\sigma' \in G$. Since $\sigma'$ can be expressed as a product of transpositions, it follows that $\sigma$ can be expressed as a product of transpositions. $\blacksquare$

Note that in general this theorem is not true on infinite sets without permitting infinite compositions of functions.

Theorem 2. The symmetric group $\mathfrak{S}_n$ is generated by the transpositions $(\tau_{i,i+1})_{1 \le i \le n-1}$.

Proof. By theorem 1, it is enough to prove that any transposition $\tau_{a,b}$ is generated by $(\tau_{i,i+1})_{1 \le i \le n-1}$. Without loss of generality, suppose $a \le b$. We induct on $b-a$. Our base case, $b-a=0$, is trivial. For the inductive step, we note that \[\tau_{a,b} = \tau_{a,a+1} \tau_{a+1,b} \tau_{a,a+1} .\] Since $\tau_{a+1,b}$ is in the subgroup generated by $(\tau_{i,i+1})_{1 \le i \le n-1}$, it follows that $\tau_{a,b}$ is, as well. $\blacksquare$

Theorem 3. Let $\zeta$ be a cycle whose orbit is $M$, let $a$ be an element of $M$, and let $\tau_{a,\zeta(a)}$ be a transposition on $M$. Then $\zeta$ and $\tau_{a,\zeta(a)}$ generate $\mathfrak{S}_M$.

Proof. Let $x$ be an arbitrary element of $M$. Then we may denote every element of $M$ as $\zeta^k(x)$, where $k$ is an integer. Suppose $a= \zeta^m(x)$. By Theorem 2, it is enough to show that $\tau_{\zeta^{k}(x), \zeta^{k+1}(x)}$ lies in the subgroup generated by $\zeta$ and $\tau_{a,b}$, for each integer $k$. But this follows from the observation \[\tau_{\zeta^{k}(x), \zeta^{k+1}(x)} = \zeta^{k-m} \circ \tau_{\zeta^m(x), \zeta^{m+1}(x)} \circ \zeta^{m-k} .\] Thus $\zeta$ and $\tau_{a,\zeta(a)}$ generate $\mathfrak{S}_M$, as desired. $\blacksquare$

Even and Odd Permutations; Alternating Groups

For an element $\sigma \in \mathfrak{S}_n$, an inversion is an ordered pair of integers $(a,b)$ such that $1 \le a < b \le n$ and $\sigma(a) > \sigma(b)$. We will let $\nu(\sigma)$ denote the number of inversions of $\sigma$. A permutation is called odd if it has an odd number of inversions, and even if it contains an even number of inversions. We wish to show that the mapping $\sigma \mapsto (-1)^{\nu(\sigma)}$ is a homomorphism; this would imply that even permutations form a normal subgroup of $\mathfrak{S}_n$.

Let $f$ be a mapping from $\mathbb{Z}^n$ to $\mathbb{Z}$, and suppose $\sigma \in \mathfrak{S}_n$. Let $\sigma f$ be the mapping so that \[\sigma f(z_1, \dotsc, z_n) = f(z_{\sigma(1)}, \dotsc, z_{\sigma(n)}) .\] Then evidently $\sigma(-f) = -\sigma f$.

Let $p : \mathbb{Z}^n \to \mathbb{Z}$ be the mapping \[(z_1, \dotsc, z_n) \mapsto \prod_{i<j} (z_j - z_i).\]

Lemma. The function $p$ is not the zero function, and $\sigma p = (-1)^{\nu(\sigma)} p$.

Proof. If $z_1, \dotsc, z_n$ are distinct, then $p(z_1, \dotsc, z_n) \neq 0$. Let $\chi(i,j)$ denote 1 if $(i,j)$ is a $\sigma$-inversion, and 0, otherwise. Then by rearranging terms, \[\sigma p(z_1, \dotsc, z_n) = \prod_{i<j} (z_{\sigma(i)} - z_{\sigma(j)} = \prod_{i < j}(-1)^{\chi(i,j)} (z_i - z_j) = (-1)^{\nu(\sigma)} p(z_1, \dotsc, z_n),\] as desired. $\blacksquare$

Theorem 4. There exists a unique homomorphism $\epsilon$ from $\mathfrak{S}_M$ to the multiplicative group $\{-1,1\}$ such that $\epsilon(\tau) = -1$, for any transposition $\tau$.

Proof. To show the existance of $\epsilon$, it suffices to show its existance for $M = \{1,\dotsc, n\}$. We will show that $\epsilon(\sigma) = (-1)^{\nu(\sigma)}$ is such a homomorphism. Indeed, if $\sigma, \sigma'$ are elements of $\mathfrak{S}_n$, then by the lemma, \[\sigma \sigma' p = \sigma\bigl(\epsilon(\sigma') \bigr) p = \epsilon(\sigma') \cdot \sigma p = \epsilon(\sigma') \epsilon(\sigma) p = \epsilon(\sigma) \epsilon(\sigma') p .\] On the other hand, \[\sigma \sigma' p = \epsilon(\sigma \sigma') p.\] Since $p\neq -p$ (from the lemma), it follows that \[\epsilon(\sigma \sigma') = \epsilon(\sigma) \epsilon(\sigma'),\] i.e., $\epsilon$ is a homomorphism, as desired, and evidently $\epsilon(\tau) = -1$ for every transposition $\tau$.

Since $\mathfrak{S}_M$ is generated by its transpositions (Theorem 1), it follows that $\epsilon$ is unique. $\blacksquare$

This is what we wanted to prove. The kernel of $\epsilon$ is the set of even permutations on $M$, called the alternating group of $M$. It is usually denoted as $A_M$, $\mathfrak{A}_M$, or $\text{Alt}(M)$.

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Symmetric_group&oldid=26141"