CommeUnJeu · L1 MPSI

Symmetric group

⌚ ~43 min ▢ 5 blocks ✓ 17 exercises ➣ Prerequisites : Algebraic structures

Why this chapter

The chapter Algebraic structures introduced $\mathfrak{S}_n$ as the running non-abelian example of a group. We now elaborate the structure of this group: how to decompose any permutation into elementary blocks (cycles, then transpositions), and how to attach a single sign $\pm 1$ --- the signature --- that captures parity. The signature is the key invariant for the construction of determinants in the next chapter, and it appears throughout combinatorics, probability, and geometry whenever a parity argument is needed.
The chapter has two short sections: (a) generalities on $\mathfrak{S}_n$ (cycles, transpositions, cycle decomposition --- the proof of which is admitted), and (b) the signature morphism (the proof of its existence is admitted).

Conventions

Throughout this chapter we use the following conventions, established once and assumed thereafter.

Composition of permutations (right-to-left). For $\sigma, \tau \in \mathfrak{S}_n$, the product $\sigma \tau$ denotes the composition $\sigma \circ \tau$. Equivalently, $(\sigma \tau)(x) = \sigma(\tau(x))$ for every $x$ --- that is, $\tau$ acts first, then $\sigma$.
Identity. The neutral element of $\mathfrak{S}_n$ is the identity map of $\{1, \dots, n\}$, denoted $\operatorname{id}$.
Cycle notation. Cycles are written with a thin space between entries: $(a_1\ a_2\ \dots\ a_p)$. We never use commas inside cycle notation in this chapter.
Setting. Unless otherwise stated, $n \in \mathbb{N}^*$ and we work in $\mathfrak{S}_n$.

These conventions matter: every cycle and signature formula below depends on the right-to-left direction of composition.

I Generalities on $\mathfrak{S}_n$

I.1 The symmetric group $\mathfrak{S}_n$

The symmetric group is the group of all bijections of $\{1, \dots, n\}$ to itself, with composition as the law. We have already seen in Algebraic structures that it is non-abelian for $n \geq 3$ and has cardinal $n!$. Here we recap the definition and introduce a compact notation (the two-row tableau) to describe a permutation by listing its values.

Definition — Symmetric group on n letters

For $n \in \mathbb{N}^*$, the symmetric group on $n$ letters is the set $$ \mathfrak{S}_n = \{\sigma : \{1, \dots, n\} \to \{1, \dots, n\} \mid \sigma \text{ is a bijection}\} $$ equipped with the composition $\circ$. The elements of $\mathfrak{S}_n$ are called permutations. The neutral is $\operatorname{id}$ and the inverse of $\sigma$ is the inverse map $\sigma^{-1}$. We write $\sigma \tau$ for $\sigma \circ \tau$ (recall: $\tau$ acts first).

Definition — Tableau notation

A permutation $\sigma \in \mathfrak{S}_n$ can be written as a two-row (no link with matrix calculus --- this is just a compact list of values): $$ \sigma = \begin{pmatrix} 1 & 2 & \cdots & n \\ \sigma(1) & \sigma(2) & \cdots & \sigma(n) \end{pmatrix}. $$ The first row lists the inputs, the second row lists their images.

Example — The six elements of $\mathfrak{S}_3$

The group $\mathfrak{S}_3$ has $3! = 6$ elements: $$ \operatorname{id} = \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}, $$ $$ \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}, \quad \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}. $$ The first is the identity; the next three swap two entries (transpositions); the last two cyclically rotate the three entries (3-cycles).

Example — Non-commutativity in $\mathfrak{S}_3$

The right-to-left convention is essential to compute products correctly. Two simple products in $\mathfrak{S}_3$ illustrate that the group is non-abelian: $$ (1\ 2)(2\ 3) = (1\ 2\ 3), \qquad (2\ 3)(1\ 2) = (1\ 3\ 2). $$ Verification of the first: applying $(2\ 3)$ first then $(1\ 2)$ to each input, $$ 1 \xmapsto{(2\ 3)} 1 \xmapsto{(1\ 2)} 2, \quad 2 \xmapsto{(2\ 3)} 3 \xmapsto{(1\ 2)} 3, \quad 3 \xmapsto{(2\ 3)} 2 \xmapsto{(1\ 2)} 1. $$ So $(1\ 2)(2\ 3)$ sends $1 \to 2$, $2 \to 3$, $3 \to 1$ --- that is $(1\ 2\ 3)$. The second product is similar; the two results differ, so $(1\ 2)$ and $(2\ 3)$ do not commute.

Example — Computing in tableau form

Let $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 5 & 2 & 4 \end{pmatrix} \in \mathfrak{S}_5$. Then $\sigma(3) = 5$, and:

$\sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{pmatrix}$ (read the tableau bottom-up);
$\sigma \circ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 3 & 4 & 1 & 2 \end{pmatrix}$ (apply $\sigma$ twice: $1 \to 3 \to 5$, $2 \to 1 \to 3$, etc.).

Proposition — Cardinal of $\mathfrak{S}_n$

For all $n \in \mathbb{N}^*$, $|\mathfrak{S}_n| = n!$.

Proof

A permutation $\sigma \in \mathfrak{S}_n$ is determined by the choice of $\sigma(1), \sigma(2), \dots, \sigma(n)$. Since $\sigma$ is a bijection, these values are pairwise distinct elements of $\{1, \dots, n\}$. Counting:

$\sigma(1)$: $n$ choices;
$\sigma(2)$: $n - 1$ choices (any element except $\sigma(1)$);
$\dots$;
$\sigma(n)$: $1$ remaining choice.

By the multiplication principle, $|\mathfrak{S}_n| = n \cdot (n-1) \cdots 1 = n!$.

Skills to practice

Calculating in $\mathfrak{S}_n$

I.2 Cycles$\virgule$ support$\virgule$ transpositions

The richest part of $\mathfrak{S}_n$ is the way each permutation is built from simple pieces called cycles. A cycle "rotates" a small subset of $\{1, \dots, n\}$ and fixes everything else. The simplest cycles, with only two entries, are the transpositions --- they swap two elements. Cycles and transpositions are the elementary building blocks for the rest of the chapter.

Definition — Support of a permutation

The support of $\sigma \in \mathfrak{S}_n$ is the set $$ \operatorname{supp}(\sigma) = \{x \in \{1, \dots, n\} \mid \sigma(x) \neq x\}. $$ The complement of the support is the set of fixed points of $\sigma$.

Definition — $p$-cycle

Let $p \geq 2$ and let $a_1, a_2, \dots, a_p \in \{1, \dots, n\}$ be pairwise distinct. The $p$-cycle $(a_1\ a_2\ \dots\ a_p)$ is the permutation $\sigma \in \mathfrak{S}_n$ defined by: $$ \sigma(a_1) = a_2, \quad \sigma(a_2) = a_3, \quad \dots, \quad \sigma(a_{p-1}) = a_p, \quad \sigma(a_p) = a_1, $$ and $\sigma(x) = x$ for all $x \notin \{a_1, \dots, a_p\}$. The integer $p$ is the length of the cycle. Its support is $\{a_1, \dots, a_p\}$.

Definition — Transposition

A transposition is a $2$-cycle, i.e. a permutation of the form $(a\ b)$ with $a, b \in \{1, \dots, n\}$ distinct. Such a permutation swaps $a$ and $b$ and fixes every other element.

Example — The 3-cycle $(1\ 3\ 5)$ in $\mathfrak{S}_5$

The cycle $(1\ 3\ 5) \in \mathfrak{S}_5$ sends $1 \to 3$, $3 \to 5$, $5 \to 1$, and fixes $2$ and $4$. In tableau form: $$ (1\ 3\ 5) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 5 & 4 & 1 \end{pmatrix}. $$ Its support is $\{1, 3, 5\}$; its fixed points are $2$ and $4$.

Example — The transposition $(2\ 4)$ is involutive

The transposition $(2\ 4) \in \mathfrak{S}_5$ swaps $2$ and $4$ and fixes $1, 3, 5$. Applying it twice: $$ \begin{aligned} (2\ 4)\bigl((2\ 4)(2)\bigr) &= (2\ 4)(4) = 2, \\ (2\ 4)\bigl((2\ 4)(4)\bigr) &= (2\ 4)(2) = 4. \end{aligned} $$ And every other element is fixed by both. Hence $(2\ 4) \circ (2\ 4) = \operatorname{id}$.

Proposition — Cyclic-rotation invariance and cycle inverse

Let $p \geq 2$ and $a_1, \dots, a_p \in \{1, \dots, n\}$ pairwise distinct.

Cyclic rotation: the $p$-cycle is unchanged by cyclic rotation of its entries: $$ (a_1\ a_2\ \dots\ a_p) = (a_2\ a_3\ \dots\ a_p\ a_1) = \dots = (a_p\ a_1\ \dots\ a_{p-1}). $$
Inverse: the inverse of a cycle reverses the order of its entries (after fixing the first): $$ (a_1\ a_2\ \dots\ a_p)^{-1} = (a_1\ a_p\ a_{p-1}\ \dots\ a_2). $$

Proof

Cyclic rotation. The $p$-cycle $\sigma = (a_1\ a_2\ \dots\ a_p)$ acts as $a_i \mapsto a_{i+1}$ for $1 \leq i \leq p-1$ and $a_p \mapsto a_1$, fixing every other element. The cycle $(a_2\ a_3\ \dots\ a_p\ a_1)$ acts the same way: $a_2 \mapsto a_3, \dots, a_{p-1} \mapsto a_p, a_p \mapsto a_1, a_1 \mapsto a_2$, fixing every other element. So the two are equal as functions. The same argument works for any cyclic shift.
Inverse. Define $\tau = (a_1\ a_p\ a_{p-1}\ \dots\ a_2)$. Then $\tau$ acts as $a_1 \mapsto a_p \mapsto a_{p-1} \mapsto \dots \mapsto a_2 \mapsto a_1$. Compose with $\sigma$: $$ (\sigma \circ \tau)(a_1) = \sigma(a_p) = a_1, \quad (\sigma \circ \tau)(a_p) = \sigma(a_{p-1}) = a_p, \quad \dots, \quad (\sigma \circ \tau)(a_2) = \sigma(a_1) = a_2. $$ And every $x$ outside the support is fixed. So $\sigma \circ \tau = \operatorname{id}$. The same verification gives $\tau \circ \sigma = \operatorname{id}$, so $\tau = \sigma^{-1}$.

Proposition — Transpositions are involutive

Every transposition $\tau = (a\ b)$ satisfies $\tau^{-1} = \tau$, i.e. $\tau \circ \tau = \operatorname{id}$.

Proof

Apply $(a\ b)$ twice: $a \mapsto b \mapsto a$ and $b \mapsto a \mapsto b$. Every other element is fixed by $(a\ b)$. So $(a\ b) \circ (a\ b)$ acts as $\operatorname{id}$.

Example — Three notations for the same cycle

By the cyclic-rotation rule: $$ (1\ 3\ 5) = (3\ 5\ 1) = (5\ 1\ 3). $$ By the inverse rule: $$ (1\ 3\ 5)^{-1} = (1\ 5\ 3). $$ Verification on each support element: $(1\ 3\ 5)(1\ 5\ 3)(1) = (1\ 3\ 5)(5) = 1$, $(1\ 3\ 5)(1\ 5\ 3)(3) = (1\ 3\ 5)(1) = 3$, $(1\ 3\ 5)(1\ 5\ 3)(5) = (1\ 3\ 5)(3) = 5$. So the composite fixes $1$, $3$, $5$ (and trivially $2$, $4$). $\checkmark$

Proposition — Number of transpositions in $\mathfrak{S}_n$

The number of transpositions in $\mathfrak{S}_n$ is $$ \binom{n}{2} = \frac{n(n-1)}{2}. $$

Proof

A transposition is determined by an unordered pair $\{a, b\} \subset \{1, \dots, n\}$ with $a \neq b$ --- note that $(a\ b) = (b\ a)$, so the order does not matter. The number of such pairs is $\binom{n}{2}$.

Example — Counting transpositions in small $\mathfrak{S}_n$

In $\mathfrak{S}_3$: $\binom{3}{2} = 3$ transpositions, namely $(1\ 2)$, $(1\ 3)$, $(2\ 3)$.
In $\mathfrak{S}_4$: $\binom{4}{2} = 6$ transpositions.
In $\mathfrak{S}_5$: $\binom{5}{2} = 10$ transpositions.

Skills to practice

Manipulating cycles and transpositions

I.3 Disjoint cycle decomposition

Two cycles whose supports are disjoint commute (they act on different parts of $\{1, \dots, n\}$). The fundamental result of this subsection is that every permutation, except the identity, factors uniquely as a product of cycles with pairwise disjoint supports. The proof is admitted by the program; we focus on using the decomposition rather than proving it.

Proposition — Disjoint cycle decomposition

Every $\sigma \in \mathfrak{S}_n$ with $\sigma \neq \operatorname{id}$ factors as a product $$ \sigma = c_1 c_2 \cdots c_k $$ of cycles $c_1, \dots, c_k$ of length $\geq 2$ with pairwise disjoint supports. The decomposition is unique up to the order of the factors (since disjoint cycles commute) and up to cyclic rotation inside each cycle. Fixed points are usually omitted from the notation.
Disjoint cycles commute: if $c, c'$ have disjoint supports then $c c' = c' c$.
By convention, the identity permutation $\operatorname{id}$ is the empty product of disjoint cycles (it has no cycle of length $\geq 2$ in its decomposition; every element is a fixed point).

Proof

Admitted; an idea of proof is sketched in the Text block below.

Idea of the proof

For $\sigma \in \mathfrak{S}_n$, define the orbit of $x$ as $\{x, \sigma(x), \sigma^2(x), \dots\}$. The orbits partition $\{1, \dots, n\}$. Each orbit of size $\geq 2$ gives a cycle (read by following $\sigma$); orbits of size $1$ are the fixed points. The disjoint-support claim follows because orbits are disjoint. Uniqueness comes from the fact that the orbits are determined by $\sigma$.

Method — Decomposing a permutation into disjoint cycles

Given $\sigma \in \mathfrak{S}_n$ in tableau form:

Step 1. Pick the smallest $a \in \{1, \dots, n\}$ with $\sigma(a) \neq a$.
Step 2. Follow the orbit: $a \to \sigma(a) \to \sigma^2(a) \to \dots$ until you return to $a$. This gives the first cycle $(a\ \sigma(a)\ \sigma^2(a)\ \dots)$.
Step 3. Pick the smallest unused element $b$ with $\sigma(b) \neq b$ (skipping fixed points). Repeat Step 2 from $b$ to get the next cycle.
Step 4. Iterate until every non-fixed element is used. The product of the cycles obtained, in any order, is $\sigma$.

Example — Decomposition of a permutation in $\mathfrak{S}_7$

Decompose $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 5 & 7 & 4 & 2 & 6 & 1 \end{pmatrix}$ into disjoint cycles.

Answer

Apply the method.

Step 1. The smallest non-fixed element is $1$ (since $\sigma(1) = 3 \neq 1$).
Step 2. Orbit of $1$: $1 \to 3 \to 7 \to 1$. First cycle: $(1\ 3\ 7)$.
Step 3. Smallest unused non-fixed element: $2$ (since $\sigma(2) = 5 \neq 2$). Orbit: $2 \to 5 \to 2$. Second cycle: $(2\ 5)$.
Step 4. Remaining elements: $4$ and $6$ are fixed by $\sigma$ (since $\sigma(4) = 4$, $\sigma(6) = 6$). All non-fixed elements have been used.

Conclusion: $\sigma = (1\ 3\ 7)(2\ 5)$, with $4$ and $6$ as fixed points (omitted from the notation).

Example — From cycle form back to tableau

Recover the tableau form of $\sigma = (1\ 2\ 3)(4\ 5) \in \mathfrak{S}_5$.

Answer

The two cycles have disjoint supports $\{1, 2, 3\}$ and $\{4, 5\}$, so they commute. Apply each: $$ 1 \to 2, \quad 2 \to 3, \quad 3 \to 1, \quad 4 \to 5, \quad 5 \to 4. $$ Tableau form: $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{pmatrix}$.

Proposition — Order of a cycle

A cycle $c$ of length $p$ has order $p$ in $\mathfrak{S}_n$, that is, $c^p = \operatorname{id}$ and $p$ is the smallest positive integer with this property.

Proof

Write $c = (a_1\ a_2\ \dots\ a_p)$. For any $a_i$ in the support and any $k \in \mathbb{N}$, $$ c^k(a_i) = a_{((i - 1 + k) \bmod p) + 1}, $$ where the modular reduction is taken in the residue system $\{0, 1, \dots, p - 1\}$. So $c^k(a_i) = a_i$ iff $(i - 1 + k) \equiv (i - 1) \pmod p$ iff $p \mid k$. For $x$ outside the support, $c^k(x) = x$ trivially. Hence $c^k = \operatorname{id}$ iff $p \mid k$. The smallest positive such $k$ is $p$.

Proposition — Order of a permutation via cycle decomposition

Let $\sigma \in \mathfrak{S}_n$ with disjoint-cycle decomposition $\sigma = c_1 c_2 \cdots c_k$, where $c_i$ has length $p_i \geq 2$. Then $$ \operatorname{ord}(\sigma) = \operatorname{lcm}(p_1, p_2, \dots, p_k). $$

Proof

Using the admitted commutativity of disjoint cycles, the cycles $c_1, \dots, c_k$ commute pairwise, so for every $m \in \mathbb{N}$, $$ \sigma^m = c_1^m c_2^m \cdots c_k^m. $$ Then, for $m \in \mathbb{N}^*$: $$ \begin{aligned} \sigma^m = \operatorname{id} &\iff c_1^m c_2^m \cdots c_k^m = \operatorname{id} && \text{(power of $\sigma$)} \\ &\iff c_i^m = \operatorname{id} \text{ for every } i && \text{(disjoint supports)} \\ &\iff p_i \mid m \text{ for every } i && \text{(order of a cycle)} \\ &\iff \operatorname{lcm}(p_1, \dots, p_k) \mid m && \text{(definition of lcm)}. \end{aligned} $$ The smallest such $m > 0$ is $\operatorname{lcm}(p_1, \dots, p_k)$.

Example — Order via lcm

The permutation $\sigma = (1\ 3\ 7)(2\ 5) \in \mathfrak{S}_7$ has cycle lengths $3$ and $2$, so $\operatorname{ord}(\sigma) = \operatorname{lcm}(3, 2) = 6$.
The permutation $\rho = (1\ 2\ 3\ 4)(5\ 6\ 7) \in \mathfrak{S}_7$ has cycle lengths $4$ and $3$, so $\operatorname{ord}(\rho) = \operatorname{lcm}(4, 3) = 12$.

Skills to practice

Decomposing into disjoint cycles

II Signature

II.1 Decomposition into transpositions

Beyond cycles, the truly elementary building blocks of $\mathfrak{S}_n$ are the transpositions: every permutation can be written as a product of transpositions. The decomposition is not unique --- different products can give the same permutation. We shall see in the next subsection that, despite this non-uniqueness, the parity of the number of transpositions is an invariant of the permutation. That parity is captured by the signature.

Proposition — A cycle as a product of transpositions

Every cycle is a product of transpositions. Specifically, for $p \geq 2$ and $a_1, \dots, a_p$ pairwise distinct, $$ (a_1\ a_2\ \dots\ a_p) = (a_1\ a_2)(a_2\ a_3) \cdots (a_{p-1}\ a_p), $$ a product of $p - 1$ transpositions (with our right-to-left composition convention).

Proof

Apply the right-hand side to each $a_i$, remembering that the rightmost transposition $(a_{p-1}\ a_p)$ acts first.

For $a_p$: $(a_{p-1}\ a_p)(a_p) = a_{p-1}$. Then $(a_{p-2}\ a_{p-1})(a_{p-1}) = a_{p-2}$, and so on, finally $(a_1\ a_2)(a_2) = a_1$. Net result: $a_p \mapsto a_1$.
For $a_{p-1}$: $(a_{p-1}\ a_p)(a_{p-1}) = a_p$. The next transposition $(a_{p-2}\ a_{p-1})$ does not move $a_p$. Subsequent transpositions $(a_i\ a_{i+1})$ for $i < p - 1$ also fix $a_p$. Net result: $a_{p-1} \mapsto a_p$.
For $a_i$ with $1 \leq i \leq p - 2$: only $(a_i\ a_{i+1})$ moves $a_i$ (it sends $a_i$ to $a_{i+1}$); the transpositions $(a_j\ a_{j+1})$ with $j < i$ appear to the left of $(a_i\ a_{i+1})$ in the written product and hence apply after, but they all fix $a_{i+1}$ (since $a_{i+1} \notin \{a_j, a_{j+1}\}$ when $j < i$). Net result: $a_i \mapsto a_{i+1}$.
For $x \notin \{a_1, \dots, a_p\}$: every transposition fixes $x$.

This is exactly the action of $(a_1\ a_2\ \dots\ a_p)$.

Alternative formula -- remark

Another decomposition of the same cycle is also valid: $$ (a_1\ a_2\ \dots\ a_p) = (a_1\ a_p)(a_1\ a_{p-1}) \cdots (a_1\ a_2), $$ again using $p - 1$ transpositions. We adopt the form of the previous proposition as canonical in this chapter; the alternative is sometimes more convenient (e.g. when one wants every transposition to share a common letter).

Proposition — $\mathfrak{S}_n$ is generated by transpositions

Every $\sigma \in \mathfrak{S}_n$ is a product of transpositions.

Proof

Assuming the admitted disjoint-cycle decomposition of the previous subsection, write $\sigma = c_1 c_2 \cdots c_k$ as a product of cycles. By the previous proposition, each cycle $c_i$ is a product of transpositions. Concatenating the decompositions, $\sigma$ is itself a product of transpositions.
The case $\sigma = \operatorname{id}$ is handled by the convention that the empty product equals $\operatorname{id}$. When $n \geq 2$, one may also write concretely $\operatorname{id} = (1\ 2)(1\ 2)$.

Caveat -- non-uniqueness

The decomposition of a permutation as a product of transpositions is not unique. For example, $$ (1\ 2\ 3) = (1\ 2)(2\ 3) = (1\ 3)(1\ 2), $$ two different products of $2$ transpositions giving the same $3$-cycle. We will see in the Signature subsection that, although the number of factors can vary, its parity is invariant.

Example — $(1\ 4)(2\ 5)(3\ 6)$ already in transposition form

The permutation $\sigma = (1\ 4)(2\ 5)(3\ 6) \in \mathfrak{S}_6$ is already a product of $3$ transpositions (with disjoint supports, so they commute). No further decomposition is needed.

Example — Decomposing $(1\ 3\ 5)(2\ 4)$ into transpositions

Take $\sigma = (1\ 3\ 5)(2\ 4) \in \mathfrak{S}_5$. Apply the canonical formula to each cycle: $$ (1\ 3\ 5) = (1\ 3)(3\ 5), \qquad (2\ 4) = (2\ 4). $$ The two cycles have disjoint supports, so they commute, and we can concatenate: $$ \sigma = (1\ 3)(3\ 5)(2\ 4), $$ a product of $3$ transpositions in total.

Skills to practice

Decomposing into transpositions

II.2 Signature

Different transposition decompositions of the same permutation can use different numbers of transpositions, but the parity of that number is fixed by the permutation. The signature is the function $\mathfrak{S}_n \to \{-1, 1\}$ that reads $-1$ for an odd number of transpositions and $+1$ for an even number. Its existence and uniqueness --- which encode the parity invariance --- are admitted by the program.

Proposition — Existence and uniqueness of the signature

There exists a unique group morphism, denoted later by $\varepsilon$, $$ \varepsilon : \mathfrak{S}_n \longrightarrow \{-1, 1\} $$ sending every transposition to $-1$. Equivalently: for any $\sigma \in \mathfrak{S}_n$ written as a product of transpositions $\sigma = \tau_1 \tau_2 \cdots \tau_p$, the value $(-1)^p$ depends only on $\sigma$ --- not on the chosen decomposition.

Proof

Admitted; an idea of proof is sketched in the Text block below.

Idea of the proof

Existence. One can verify that the explicit formula $$ \varepsilon(\sigma) = \prod_{1 \leq i < j \leq n} \frac{\sigma(j) - \sigma(i)}{j - i} $$ defines a multiplicative map $\mathfrak{S}_n \to \{-1, 1\}$ that takes the value $-1$ on every transposition.
Uniqueness. Any morphism $\mathfrak{S}_n \to \{-1, 1\}$ is determined by its values on the transpositions, since every $\sigma$ is a product of transpositions. Imposing $-1$ on every transposition fixes the morphism.

Definition — Signature -- even and odd permutations

The unique morphism above is called the signature and is denoted $\varepsilon$: $$ \varepsilon : \mathfrak{S}_n \to \{-1, 1\}. $$ A permutation $\sigma$ is even if $\varepsilon(\sigma) = 1$, and odd if $\varepsilon(\sigma) = -1$.

Proposition — Basic properties of $\varepsilon$

The signature satisfies, for all $\sigma, \sigma' \in \mathfrak{S}_n$:

$\varepsilon(\operatorname{id}) = 1$;
$\varepsilon(\sigma \sigma') = \varepsilon(\sigma) \varepsilon(\sigma')$ (multiplicativity);
$\varepsilon(\sigma^{-1}) = \varepsilon(\sigma)$.

Proof

The first two are immediate from the fact that $\varepsilon$ is a group morphism. For the third: applying the morphism to $\sigma \sigma^{-1} = \operatorname{id}$ gives $\varepsilon(\sigma) \varepsilon(\sigma^{-1}) = 1$. Since $\varepsilon$ takes values in $\{-1, 1\}$, every element is its own inverse in $\{-1, 1\}$ under multiplication, so $\varepsilon(\sigma^{-1}) = \varepsilon(\sigma)^{-1} = \varepsilon(\sigma)$.

Example — Signatures of $\operatorname{id}$ and a transposition

By the definition: $\varepsilon(\operatorname{id}) = 1$, and $\varepsilon(\tau) = -1$ for any transposition $\tau$. Hence $\operatorname{id}$ is even and any transposition is odd.

Proposition — Signature of a p-cycle

For $p \geq 2$, the signature of a $p$-cycle is $$ \varepsilon\bigl((a_1\ a_2\ \dots\ a_p)\bigr) = (-1)^{p-1}. $$ In particular, transpositions ($p = 2$) have signature $-1$ (consistent with the definition), $3$-cycles are even, $4$-cycles are odd, etc.

Proof

By the canonical formula in the Decomposition into transpositions subsection above, $(a_1\ a_2\ \dots\ a_p) = (a_1\ a_2)(a_2\ a_3) \cdots (a_{p-1}\ a_p)$, a product of $p - 1$ transpositions. By multiplicativity of $\varepsilon$ and $\varepsilon(\tau) = -1$ for every transposition, $$ \varepsilon\bigl((a_1\ a_2\ \dots\ a_p)\bigr) = (-1)^{p-1}. $$

Method — Computing the signature of a permutation

Two practical approaches.

Via cycle decomposition (usually fastest). Decompose $\sigma$ into disjoint cycles of lengths $p_1, \dots, p_k$. Then $$ \varepsilon(\sigma) = (-1)^{(p_1 - 1) + (p_2 - 1) + \cdots + (p_k - 1)}. $$
Via transposition decomposition. Write $\sigma$ as a product of $p$ transpositions; then $\varepsilon(\sigma) = (-1)^p$.

The cycle-length formula above assumes the cycles have disjoint supports. If $\sigma$ is given as a product of cycles whose supports overlap, two options are available:

re-decompose $\sigma$ into disjoint cycles, then apply the length formula (slower in general);
or, often faster, use the multiplicativity of $\varepsilon$ directly and multiply the signatures of the given cycles: $\varepsilon(c_1 c_2 \cdots c_k) = \varepsilon(c_1) \varepsilon(c_2) \cdots \varepsilon(c_k)$, with each $\varepsilon(c_i) = (-1)^{\ell_i - 1}$ for $c_i$ of length $\ell_i$.

The worked example below illustrates both --- re-decomposition gives the same answer as multiplicativity.

Example — Disjoint case -- simple

Compute $\varepsilon(\sigma)$ for $\sigma = (1\ 3\ 7)(2\ 5) \in \mathfrak{S}_7$.

Answer

The cycles $(1\ 3\ 7)$ and $(2\ 5)$ have disjoint supports $\{1, 3, 7\}$ and $\{2, 5\}$. Lengths $p_1 = 3$ and $p_2 = 2$. Apply the cycle-length formula: $$ \varepsilon(\sigma) = (-1)^{(3 - 1) + (2 - 1)} = (-1)^{2 + 1} = (-1)^3 = -1. $$ Cross-check via transpositions: $\sigma = (1\ 3)(3\ 7)(2\ 5)$ --- three transpositions --- so $\varepsilon(\sigma) = (-1)^3 = -1$. $\checkmark$

Example — Non-disjoint case -- fully worked

Compute the signature of $\sigma = (1\ 5\ 3)(2\ 4\ 6\ 1) \in \mathfrak{S}_6$.

Answer

Step 1 -- the cycles share an element. The supports $\{1, 5, 3\}$ and $\{2, 4, 6, 1\}$ share $1$ --- the cycles are not disjoint. So the cycle-length formula does not apply directly; we must first re-express $\sigma$ in disjoint-cycle form.
Step 2 -- compute the tableau by applying the right factor first. Following $(\sigma\tau)(x) = \sigma(\tau(x))$, the right-hand factor $(2\ 4\ 6\ 1)$ acts first, then $(1\ 5\ 3)$. Track each $x \in \{1, \dots, 6\}$ through both: $$ \begin{aligned} 1 &\overset{(2\ 4\ 6\ 1)}{\longmapsto} 2 \overset{(1\ 5\ 3)}{\longmapsto} 2, \\ 2 &\overset{(2\ 4\ 6\ 1)}{\longmapsto} 4 \overset{(1\ 5\ 3)}{\longmapsto} 4, \\ 3 &\overset{(2\ 4\ 6\ 1)}{\longmapsto} 3 \overset{(1\ 5\ 3)}{\longmapsto} 1, \\ 4 &\overset{(2\ 4\ 6\ 1)}{\longmapsto} 6 \overset{(1\ 5\ 3)}{\longmapsto} 6, \\ 5 &\overset{(2\ 4\ 6\ 1)}{\longmapsto} 5 \overset{(1\ 5\ 3)}{\longmapsto} 3, \\ 6 &\overset{(2\ 4\ 6\ 1)}{\longmapsto} 1 \overset{(1\ 5\ 3)}{\longmapsto} 5. \end{aligned} $$ Tableau form: $\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 1 & 6 & 3 & 5 \end{pmatrix}$.
Step 3 -- decompose into disjoint cycles by following orbits. Start with $1$: $1 \to 2 \to 4 \to 6 \to 5 \to 3 \to 1$. All six elements are in this orbit. So $$ \sigma = (1\ 2\ 4\ 6\ 5\ 3), $$ a single $6$-cycle.
Step 4 -- apply the cycle-length formula. $$ \varepsilon(\sigma) = (-1)^{6 - 1} = (-1)^5 = -1. $$ Cross-check via the morphism property. The original factored form has $\varepsilon\bigl((1\ 5\ 3)\bigr) \cdot \varepsilon\bigl((2\ 4\ 6\ 1)\bigr) = (-1)^{3 - 1} \cdot (-1)^{4 - 1} = 1 \cdot (-1) = -1$. $\checkmark$

Example — The 5-cycle is even

$\varepsilon\bigl((1\ 2\ 3\ 4\ 5)\bigr) = (-1)^{5 - 1} = (-1)^4 = 1$. So $(1\ 2\ 3\ 4\ 5)$ is an even permutation.
More generally, the parity of a $p$-cycle is opposite to the parity of $p$: $p$ even gives an odd cycle, $p$ odd gives an even cycle.

Going further: the alternating group $\mathfrak{A}_n$

The signature $\varepsilon : \mathfrak{S}_n \to \{-1, 1\}$ is a group morphism, so its kernel $$ \operatorname{Ker} \varepsilon = \{\sigma \in \mathfrak{S}_n \mid \varepsilon(\sigma) = 1\} $$ is a subgroup of $\mathfrak{S}_n$. It is called the alternating group and is denoted $\mathfrak{A}_n$. Its elements are the even permutations.
For $n \geq 2$, $\varepsilon$ is surjective (any transposition maps to $-1$, $\operatorname{id}$ maps to $1$), and one can show that exactly half of the permutations are even --- i.e. $|\mathfrak{A}_n| = n!/2$. The argument is left as a Going Further exercise.

Skills to practice

Computing signatures