197 lines
No EOL
9.2 KiB
Markdown
197 lines
No EOL
9.2 KiB
Markdown
# 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)$.
|
|
|
|
<br>
|
|
|
|
> *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}$.
|
|
|
|
<br>
|
|
|
|
> *Theorem*: $\mathrm{Sym}_n$ has exactly $n!$ elements.
|
|
|
|
??? note "*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.
|
|
|
|
<br>
|
|
|
|
> *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\}$.
|
|
|
|
<br>
|
|
|
|
> *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)$.
|
|
|
|
<br>
|
|
|
|
> *Theorem*: every permutation in $\mathrm{Sym}_n$ is a product of disjoint cycles. This product is unique up to rearrangement of the factors.
|
|
|
|
??? note "*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)$.
|
|
|
|
<br>
|
|
|
|
> *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}$.
|
|
|
|
??? note "*Proof*:"
|
|
|
|
Will be added later.
|
|
|
|
Conjugation is similar to basis transformation in linear algebra.
|
|
|
|
<br>
|
|
|
|
> *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}$.
|
|
|
|
??? note "*Proof*:"
|
|
|
|
Will be added later.
|
|
|
|
<br>
|
|
|
|
> *Corollary*: being conjugate is an equivalence relation on $\mathrm{Sym}_n$.
|
|
|
|
??? note "*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)$.
|
|
|
|
<br>
|
|
|
|
> *Theorem*: let $n \geq 2$. Every permutation of $\mathrm{Sym}_n$ is the product of transpositions.
|
|
|
|
??? note "*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.
|
|
|
|
??? note "*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$.
|
|
|
|
<br>
|
|
|
|
> *Theorem*: for all permutations $g,h$ in $\mathrm{Sym}_n$, we have
|
|
>
|
|
> $$
|
|
> \mathrm{sign}(g \cdot h) = \mathrm{sign}(g) \cdot \mathrm{sign}(h).
|
|
> $$
|
|
|
|
??? note "*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)$.
|
|
|
|
<br>
|
|
|
|
> *Theorem*: for $n > 1$ the alternating group $\mathrm{Alt}_n$ contains precisely $\frac{n!}{2}$ permutations.
|
|
|
|
??? note "*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. |