Symmetric Groups, Cycle Decomposition and the Sign Homomorphism

Let $n\in\mathbb N$, so that $n=\{0,1,\dots,n-1\}$ (The natural numbers $\mathbb{N}$ (von Neumann)). The symmetric group on $n$ letters is

$S_n:=\operatorname{Sym}(n)=\operatorname{Sym}(\{0,1,\dots,n-1\}),$

the group of all bijections of $n$ under composition (The symmetric group $\operatorname{Sym}(X)$: the bijections of a set $X$ under composition), with the composition convention

$(\sigma\tau)(i):=(\sigma\circ\tau)(i)=\sigma(\tau(i))\qquad(i\in n),$

so that in a product the right-hand factor acts first. An element of $S_n$ is named by either of the two notations below.

One-line notation. For $\sigma\in S_n$, its one-line form is the list of its values in order of their arguments,

$\sigma=[\sigma(0),\sigma(1),\dots,\sigma(n-1)].$

This list has length $n$ and its entries are $0,1,\dots,n-1$, each occurring once, because $\sigma$ is a bijection of $n$. Conversely, a list $[b_0,b_1,\dots,b_{n-1}]$ whose entries are $0,1,\dots,n-1$ each occurring once is the one-line form of exactly one element of $S_n$, namely the map sending each $i\in n$ to $b_i$: that map is injective because the entries are distinct, and surjective because every element of $n$ occurs among them. So one-line notation is a bijection from $S_n$ to the arrangements of $0,1,\dots,n-1$ in a list. For $n=0$ the one-line form of the unique element of $S_0$ is the empty list.

Cycle notation. For distinct $a_0,a_1,\dots,a_{k-1}\in n$ with $k\ge2$, the symbol $(a_0\,a_1\,\cdots\,a_{k-1})$ denotes the element of $S_n$ that sends $a_i$ to $a_{i+1}$ for each $i<k-1$, sends $a_{k-1}$ to $a_0$, and fixes every element of $n$ outside $\{a_0,\dots,a_{k-1}\}$ (The symmetric group $\operatorname{Sym}(X)$: the bijections of a set $X$ under composition); it is called a $k$-cycle, and a $2$-cycle is a transposition. Writing cycle symbols side by side means composing them, so $(a\,b)(c\,d)$ is $(a\,b)\circ(c\,d)$, and the empty juxtaposition of cycle symbols is the identity $\operatorname{id}$.

Unlike one-line notation, cycle notation does not name each permutation once: the symbol may be started at any of its entries, so

$(a_0\,a_1\,\cdots\,a_{k-1})=(a_1\,\cdots\,a_{k-1}\,a_0)$

and each $k$-cycle is written by exactly $k$ symbols of this shape. A cycle symbol also does not record $n$, which must be supplied by the context.

• The brackets carry the meaning, so the same list of numbers reads two different ways. Square brackets are one-line notation and round brackets are cycle notation. In $S_3$ the one-line form $[1,2,0]$ and the cycle symbol $(0\,1\,2)$ happen to name the same permutation, the one sending $0\mapsto1$, $1\mapsto2$, $2\mapsto0$; but $[0,1,2]$ is the identity while $(0\,1\,2)$ is not, and $[2,1,0]$ is the transposition exchanging $0$ and $2$ while $(2\,1\,0)$ is a $3$-cycle. Inside a cycle symbol this library separates the entries by thin spaces rather than by commas, which keeps the two notations apart on the page.

• Relation to the two-row form. Many texts write a permutation as the array $\sigma=\begin{pmatrix}0&1&\cdots&n-1\\\sigma(0)&\sigma(1)&\cdots&\sigma(n-1)\end{pmatrix}$, whose first row lists the arguments and whose second row lists their images. One-line notation is that array with its first row deleted, which loses nothing because the first row is the same for every $\sigma\in S_n$.

• Why the identity is a product of no cycles rather than a cycle. The cycle symbols are restricted to $k\ge2$, so a fixed point is never written. The identity is therefore the empty product, and a permutation is written by listing only the cycles that move something. Which permutations admit such a factorisation, and in how many ways, is Every permutation of a finite set is a product of pairwise disjoint cycles, uniquely up to reordering and cyclic rotation; the fixed points that cycle notation suppresses are restored as one-cycles when a cycle type is recorded (Support, fixed points, disjoint cycles, cycle length, disjoint-cycle decompositions, and cycle type).

Let $X$ be a finite set and let $\sigma\in\operatorname{Sym}(X)$, with cycle notation and composition as in The symmetric group $\operatorname{Sym}(X)$: the bijections of a set $X$ under composition.

The support and fixed-point set of $\sigma$ are

$\operatorname{supp}(\sigma):=\{x\in X:\sigma(x)\ne x\},\qquad \operatorname{Fix}(\sigma):=\{x\in X:\sigma(x)=x\}.$

A cycle $(a_0\,a_1\,\ldots\,a_{k-1})$ has length $k$ and support $\{a_0,\ldots,a_{k-1}\}$. Two cycles are disjoint when their supports are disjoint. A disjoint-cycle decomposition of $\sigma$ is an expression for $\sigma$ as a product of pairwise disjoint cycles of length at least $2$. One-cycles are omitted, and the empty product is the identity permutation.

When $|X|=n$, the cycle type of $\sigma$ is the list of natural numbers $c_1(\sigma),\ldots,c_n(\sigma)$, where $c_k(\sigma)$ is the number of $k$-element orbits of the action generated by $\sigma$. Thus $c_1(\sigma)$ is the number of fixed points. Equivalently, the cycle type records the lengths of all cycles after each fixed point is inserted as a one-cycle.

Cycles with disjoint supports commute. More precisely, if $X$ is finite and $\alpha$ and $\beta$ are cycles in $\operatorname{Sym}(X)$ and $\operatorname{supp}(\alpha)\cap\operatorname{supp}(\beta)=\varnothing$, then $\alpha\beta=\beta\alpha$.

Every permutation of a finite set is a product of pairwise disjoint cycles, uniquely up to reordering the factors and cyclically rotating the entries within each cycle. The identity permutation has the empty disjoint-cycle decomposition.

Let the nontrivial cycles in the disjoint-cycle decomposition of a permutation $\sigma$ have lengths $d_1,\ldots,d_r$. The order of $\sigma$ is the least positive natural number divisible by every $d_i$. For the identity, where $r=0$, the order is $1$.

Every permutation of a finite set is a product of transpositions. Consequently, for every natural $n$, the transpositions in $S_n=\operatorname{Sym}(n)$ generate $S_n$. The identity, including the only permutations in $S_0$ and $S_1$, is represented by the empty product.

Let $n\in\mathbb N$ and $\sigma\in S_n=\operatorname{Sym}(n)$. An inversion of $\sigma$ is a pair $(i,j)$ with $i<j<n$ and $\sigma(i)>\sigma(j)$. The inversion set and inversion number are

$\operatorname{Inv}(\sigma):=\{(i,j)\in n\times n:i<j\text{ and }\sigma(i)>\sigma(j)\},\qquad \operatorname{inv}(\sigma):=|\operatorname{Inv}(\sigma)|.$

The sign of $\sigma$ is the integer

$\operatorname{sgn}(\sigma):=(-1)^{\operatorname{inv}(\sigma)}\in\{+1,-1\}.$

The permutation is even when its sign is $+1$, equivalently when its inversion number is even, and odd when its sign is $-1$, equivalently when its inversion number is odd. For $n=0$ or $n=1$, every inversion set is empty, so the unique permutation is even.

Let $\sigma\in S_n$ and let $\tau$ be a transposition. Then

$(-1)^{\operatorname{inv}(\sigma\tau)}=-(-1)^{\operatorname{inv}(\sigma)},\qquad (-1)^{\operatorname{inv}(\tau\sigma)}=-(-1)^{\operatorname{inv}(\sigma)}.$

Thus composing on either side with a transposition reverses inversion sign.

If $\sigma=\tau_1\cdots\tau_r$ is any factorisation of a finite permutation into transpositions, then

$(-1)^r=(-1)^{\operatorname{inv}(\sigma)}.$

Consequently any two transposition factorisations of the same permutation have the same parity, and every transposition factorisation of the identity has even length.

For every natural $n$, the function $\operatorname{sgn}:S_n\to\{+1,-1\}$ is a group homomorphism. It is surjective exactly when $n\ge2$; for $n=0$ and $n=1$ its image is $\{1\}$.

A cycle of length $k$ has sign $(-1)^{k-1}$. If $\sigma\in S_n$ and $c(\sigma)$ is the number of cycles after every fixed point is included as a one-cycle, then

$\operatorname{sgn}(\sigma)=(-1)^{n-c(\sigma)}.$

For $n\in\mathbb N$, the alternating group is the kernel of the sign homomorphism,

$A_n:=\ker(\operatorname{sgn}:S_n\to\{+1,-1\})=\{\sigma\in S_n:\operatorname{sgn}(\sigma)=1\}.$

Thus $A_n$ consists exactly of the even permutations. The subgroup and normality assertions implicit in the word “group” follow from The image of a group homomorphism is a subgroup and its kernel is a normal subgroup.

For every natural $n$, $A_n$ is a normal subgroup of $S_n$. If $n\ge2$, then $2|A_n|=n!$. If $n=0$ or $n=1$, then $A_n=S_n$.

For $n\ge2$, the sign homomorphism is the unique nontrivial group homomorphism $S_n\to\{+1,-1\}$.