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:=\mathrm{Sym}(n)=\mathrm{Sym}(\{0,1,\dots ,n-1\}),$

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

$(\sigma \tau )(i):=(\sigma \circ \tau )(i)=\sigma (\tau (i))(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)]\mathrm{.}$

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\ge 2$, 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 $\mathrm{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 $(ab)(cd)$ is $(ab)\circ (cd)$, and the empty juxtaposition of cycle symbols is the identity $\mathrm{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 $(012)$ happen to name the same permutation, the one sending $0\mapsto 1$, $1\mapsto 2$, $2\mapsto 0$; but $[0,1,2]$ is the identity while $(012)$ is not, and $[2,1,0]$ is the transposition exchanging $0$ and $2$ while $(210)$ 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 =\left(\begin{array}{cccc}0& 1& \cdots & n-1\\ \sigma (0)& \sigma (1)& \cdots & \sigma (n-1)\end{array}\right)$, 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\ge 2$, 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 \mathrm{Sym}(X)$, with cycle notation and composition as in The symmetric group $\mathrm{Sym}(X)$: the bijections of a set $X$ under composition.

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

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

A cycle $(a_0{a}_1\dots a_{k-1})$ has length $k$ and support $\{a_0,\dots ,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 $\mathrm{\mid }X\mathrm{\mid }=n$, the cycle type of $\sigma$ is the list of natural numbers $c_1(\sigma ),\dots ,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 $\mathrm{Sym}(X)$ and $\mathrm{supp}(\alpha )\cap \mathrm{supp}(\beta )=\mathrm{\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,\dots ,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=\mathrm{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=\mathrm{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

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

The sign of $\sigma$ is the integer

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

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{)}^{\mathrm{inv}(\sigma \tau )}=-(-1{)}^{\mathrm{inv}(\sigma )},(-1{)}^{\mathrm{inv}(\tau \sigma )}=-(-1{)}^{\mathrm{inv}(\sigma )}\mathrm{.}$

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{)}^{\mathrm{inv}(\sigma )}\mathrm{.}$

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 $\mathrm{sgn}:S_n\to \{+1,-1\}$ is a group homomorphism. It is surjective exactly when $n\ge 2$; 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

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

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

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

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\ge 2$, then $2\mathrm{\mid }{A}_n\mathrm{\mid }=n!$. If $n=0$ or $n=1$, then $A_n=S_n$.

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