signature of a permutation

this entry is about the signature of a permutation. For other notions of signature see there.


For Aut({1,,n})S nAut(\{1, \cdots , n\}) \simeq S_n the symmetric group on nn \in \mathbb{N} elements, the signature is the unique group homomorphism

sign:S n 2={1,1} sign : S_n \to \mathbb{Z}_2 = \{1, -1\}

that sends each transposition s i,i+1:{1,,n}{1,,n}s_{i, i+1} : \{1, \cdots, n\} \to \{1, \cdots, n\}, which interchanges the iith element with its neighbour and leaves the other elements fixed, to the nontrivial element (1) 2(-1) \in \mathbb{Z}_2.

Permutations in the kernel of signsign are called even permutations, and the rest are called odd permutations.


The signature is well-defined.


One way of seeing this is invoking a standard group presentation of S nS_n where generators σ i\sigma_i for i=1i = 1 to n1n-1 (representing s i,i+1s_{i, i+1}) are subject to relations

σ i 2=1,(σ iσ i+1) 3=1,σ iσ j=σ jσ i(|ij|>1),\sigma_{i}^2 = 1, \qquad (\sigma_i \sigma_{i+1})^3 = 1, \qquad \sigma_i \sigma_j = \sigma_j \sigma_i \; ({|i-j|} \gt 1),

and checking that the sign applied to both sides of a relation equation gives the same result.

Another is by invoking a tautological representation of S nS_n on a polynomial algebra [x 1,,x n]\mathbb{Z}[x_1, \ldots, x_n],

S nSet core({x 1,,x n},{x 1,,x n})CRing core([x 1,,x n],[x 1,,x n])S_n \stackrel{\cong}{\to} Set_{core}(\{x_1, \ldots, x_n\}, \{x_1, \ldots, x_n\}) \to CRing_{core}(\mathbb{Z}[x_1, \ldots, x_n], \mathbb{Z}[x_1, \ldots, x_n])

(where core refers to the groupoid of invertible morphisms) and recognizing that for the special polynomial

D i<j(x ix j)D \coloneqq \prod_{i \lt j} (x_i - x_j)

we have, for each permutation τ\tau, either τD=D\tau \cdot D = D or τD=D\tau \cdot D = -D. (The polynomial ΔD 2\Delta \coloneqq D^2, which is invariant under the action, is called the discriminant.)


There are various means for computing the signature (also called sign) of a permutation.

The definition itself suggests one method: if we linearly order the set {x 1,,x n}\{x_1, \ldots, x_n\} by x 1<<x nx_1 \lt \ldots \lt x_n, then we can exhibit a permutation τ\tau by a string diagram and simply count the number of crossings I(τ)I(\tau); then we have

sign(τ)=(1) I(τ).sign(\tau) = (-1)^{I(\tau)}.

Each crossing corresponds to a pair of elements x i<x jx_i \lt x_j such that τ(x i)>τ(x j)\tau(x_i) \gt \tau(x_j), called an inversion.

Another method which does not depend on choosing a total order is to exhibit a permutation through its cycle decomposition. Each cycle of period kk contributes a sign (1) k1(-1)^{k-1}, and the overall sign is the product of these contributions taken over all the cycles. Thus the signature is given by the parity of the number of cycles of even length.

This cycle description can actually be used to give an independent definition of the signature. It is manifestly well-defined and invariant on conjugacy classes. To check that it defines a homomorphism to {1,1}\{1, -1\}, it suffices to check that multiplication by a transposition changes the parity of the number of even-length cycles by one. This is easy if we note that transposing two elements belonging to different cycles merges two cycles into one, whereas transposing two elements belonging to the same cycle splits one cycle into two.

Revised on September 28, 2015 10:09:08 by Todd Trimble (