Permutations

Definition

Definition: let $X$ be a set.

A bijection of $X$ to itself is called a permutation of $X$. The set of all permutations of $X$ is denoted by $\text{Sym}(X)$ and is called the symmetric group on $X$.

The product $g \cdot h$ of two permutations $g,h$ in $\text{Sym}(X)$ is defined as the composition $g \circ h$ of $g$ and $h$.

If $X = \{1, \dots, n\}$ we write $\mathrm{Sym}_n(X)$ instead of $\mathrm{Sym}(X)$.

Definition: the identity map is defined as $\mathrm{id}: X \to X$ with $g = g \cdot \mathrm{id} = \mathrm{id} \cdot g$ for all $g$ in $\mathrm{Sym}(X)$. The inverse of $g$ denoted by $g^{-1}$ satisfies $g^{-1} \cdot g = g \cdot g^{-1} = \mathrm{id}$.

In matrix notation: let $g = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1\end{pmatrix}$ and $h = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3\end{pmatrix}$ with $g,h \in \mathrm{Sym}_3(X)$, then we can take

\[ g \cdot h = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ \hline 2 & 1 & 3 \\ 3 & 2 & 1\end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1\end{pmatrix}, \]

and we have $g^{-1} = \begin{pmatrix} 2 & 3 & 1 \\1 & 2 & 3 \end{pmatrix}$.

Theorem: $\mathrm{Sym}_n$ has exactly $n!$ elements.

Proof:

A permutation can be described in a matrix notation by a $2$ by $n$ matrix with the numbers $1,\dots,n$ in the first row and the images in the second row. There are $n!$ possibilities to fill the second row.

We can also omit the matrix notation and use the list notation for permutations then we have for $g = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1\end{pmatrix} = [2,3,1]$, as the first row speaks for itself.

Definition: the order of a permutation $g$ is the smallest positive integer $m$ such that $g^m = \mathrm{id}$.

For example the order of the permutation $[2,1,3]$ in $\mathrm{Sym}_3$ is 2.

If $g$ is a permutation in $\mathrm{Sym}_n$ then the permutations $g, g^2, g^3, \dots$ can not all be distinct, since there are only $n!$ distinct permutations in $\mathrm{Sym}_n$. So there must exists a $r < s$ such that $g^r = g^s$. Since $g$ is a bijection there must be $g^{s-r} = e$. So there exist positive numbers $m$ with $g^m = e$ and in particular a smallest such number. Therefore each permutation $g$ has a well-defined order.

Cycles

Definition: the fixed points of a permutation $g$ of $\mathrm{Sym}(X)$ are the elements of $x \in X$ for which $g(x) = x$ holds. The set of all fixed points is $\mathrm{fix}(g) = \{x \in X \;|\; g(x) = x\}$.

The support of $g$ is the complement in $\mathrm{Sym}(X)$ of $\mathrm{fix}(g)$, denoted by $\mathrm{support}(g)$.

For example consider the permutation $g = [1,3,2,5,4,6] \in \mathrm{Sym}_6$. The fixed points of $g$ are 1 and 6. So $\mathrm{fix}(g) = \{1,6\}$. Thus the points moved by $g$ form the set $\mathrm{support}(g) = \{2,3,4,5\}$.

Definition: let $g \in \mathrm{Sym}_n$ be a permutation with $\mathrm{support}(g) = \{a_1, \dots, a_m\}$ with $a_i$ pairwise distinct.

We say $g$ is an $m$-cycle if $g(a_i) = g(a_{i+1})$ for all $i \in \{1, \dots, m-1\}$ and $g(a_m) = a_1$. For such a cycle $g$ we also use the cycle notation $(a_1, \dots, a_m)$.

2-cycles are called transpositions.

The composition of permutation in $\mathrm{Sym}_n$ is not commutative. This implies that for $g, h \in \mathrm{Sym}_n(X)$ the products $g \cdot h$ and $h \cdot g$ are not the same.

Two cycles are called disjoint if the intersection of their supports is empty. Two disjoint cycles always commute.

For example in $\mathrm{Sym}_4$ the permutation $[2,1,4,3]$ is not a cycle, but it is the product of two disjoint cycles $(1,2)$ and $(3,4)$.

Theorem: every permutation in $\mathrm{Sym}_n$ is a product of disjoint cycles. This product is unique up to rearrangement of the factors.

Proof:

Will be added later.

For example consider the permutation $g = [8,4,1,6,7,2,5,3]$ in $\mathrm{Sym}_8$. The following steps lead to the disjoint cycles decomposition.

: Choose an element in the support of $g$, for example 1. Now construct the cycle

$$
    (1,g(1),g^2(1),\dots),
$$

obtaining the cycle $(1,8,3)$.

Next choose an element in the support of $g$, but outside $\{1,3,8\}$, for example 2. Construct the cycle

$$
    (2,g(2),g^2(2),\dots),
$$

obtaining the cycle $(2,4,6)$.

Choose an element in the support of $g$ but outside $\{1,2,3,4,6,8\}, for example 5. Construct the cycle

$$
    (5,g(5),g^2(5),\dots),
$$

obtaining the cycle $(5,7)$. Then $g$ and $(1,8,3) \cdot (2,4,6) \cdot (5,7)$ coincide on $\{1,\dots,8\}$ and the decomposition is finished. As these cycles are disjoint they may commute, implying that $g$ can also be written as $(5,7) \cdot (1,8,3) \cdot (2,4,6)$ and $(2,4,6) \cdot (5,7) \cdot (1,8,3)$.

Definition: the cycle structure of a permutation $g$ is the sequence of the cycle lengths in an expression of $g$ as a product of disjoint cycles.

This means that every permutation has a unique cycle structure.

Conjugation

The choice $X = \{1, \dots, n\}$ fixed the set $X$ under consideration. Suppose a different numbering of the elements in $X$ is chosen. How may a permutation of $X$ be compared with respect to two different numberings?

Lemma: let $h$ be a permutation in $\mathrm{Sym}_n$.

For every cycle $(a_1, \dots, a_m)$ in $\mathrm{Sym}_n$ we have $$ h \cdot (a_1, \dots, a_m) \cdot h^{-1} = (h(a_1), \dots, h(a_m)). $$

If $(g_1, \dots, g_k)$ are in $\mathrm{Sym}_n$, then $h \cdot g_1 \cdots g_k \cdot h^{-1} = h g_1 h^{-1} \cdots h g_k h^{-1}$. In particular, if $g_1, \dots, g_k$ are disjoint cycles, then $h \cdot g_1 \cdots g_k \cdot h^{-1}$ is the product of the disjoint cycles $h g_1 h^{-1}, \dots, h g_k h^{-1}$.

Proof:

Will be added later.

Conjugation is similar to basis transformation in linear algebra.

Theorem: two permutations $g$ and $h$ in $\mathrm{Sym}_n$ have the same cycle structure if and only if there exists a permutation $k$ in $\mathrm{Sym}_n$ with $g = k \cdot h \cdot k^{-1}$.

Proof:

Will be added later.

Corollary: being conjugate is an equivalence relation on $\mathrm{Sym}_n$.

Proof:

Two elements in $\mathrm{Sym}_n$ are conjugate if and only if they have the same cycle structure. But having the same cycle structure is reflexive, symmetric and transitive.

For example in $\mathrm{Sym}_4$ the permutations $g = [2,1,4,3]$ and $h=[3,4,1,2] are conjugate, since both have the cycle structure $2,2$: $g = (1,2) \cdot (3,4)$ and $h = (1,3) \cdot (2,4)$. A permutation $k$ such that $k \cdot g \cdot k^{-1} = h$ is $k = [1,3,2,4] = (2,3)$.

Theorem: let $n \geq 2$. Every permutation of $\mathrm{Sym}_n$ is the product of transpositions.

Proof:

Since every permutation in $\mathrm{Sym}_n$ can be written as a product of disjoint cycles, it suffices to show that every cycle is a product of 2-cycles. Now every $m$-cycle $(a_1, \dots, a_m)$ is equal to the product

\[ (a_1, a_2) \cdot (a_2, a_3) \cdots (a_{m-1}, a_m). \]

Alternating groups

To be able to distinguish between permutations defined by an even or odd number of products (length of products), the following result is needed.

Theorem: if a permutation can be written in two way as a product of 2-cycles, then both products have even length or both products have odd length.

Proof:

Will be added later.

From this theorem the following definition follows.

Definition: let $g$ be a permutation of $\mathrm{Sym}_n$. The sign of $g$, denoted by $\mathrm{sign}(g)$, is defined as

1 if $g$ can be written as a product of an even number of 2-cycles, and

-1 if $g$ can be written as a product of an odd number of 2-cycles.

We say that $g$ is even if $\mathrm{sign}(g)=1$ and odd if $\mathrm{sign}(g)=-1$.

Theorem: for all permutations $g,h$ in $\mathrm{Sym}_n$, we have

\[ \mathrm{sign}(g \cdot h) = \mathrm{sign}(g) \cdot \mathrm{sign}(h). \]

Proof:

Let $g$ and $h$ be elements of $\mathrm{Sym}_n$, if one of the permutations is even and the other is odd, then $g \cdot h$ can be written as the product of an odd number of 2-cycles and is therefore odd. If $g$ and $h$ are both even or both odd, then the product $g \cdot h$ can be written as the product of an even number of 2-cycles so that $g \cdot h$ is even.

The fact that sign is multiplicative implies that products and inverses of even permutations are event, this given rise to the following definition.

Definition: by $\mathrm{Alt}_n$ we denote the set of even permutations in $\mathrm{Sym}_n$, called the alternating group on $n$ letters.

The alternating group is closed with respect to taking products and inverse elements.

For example for $n=3$ the even permutations are given by ($\mathrm{id}$ or $(1,2,3)$), $(3,1,2)$ and $(2,3,1)$.

Theorem: for $n > 1$ the alternating group $\mathrm{Alt}_n$ contains precisely $\frac{n!}{2}$ permutations.

Proof:

A permutation $g$ of $\mathrm{Sym}_n$ is even if and only if the product $g \cdot (1,2)$ is odd. Hence the map $g \mapsto g \cdot (1,2)$ defines a bijection between the even and the odd permutations of $\mathrm{Sym}_n$. Then half of the $n!$ permutations of $\mathrm{Sym}_n$ are even.