nLab
signature of a permutation

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

Definition

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.

Lemma

The signature is well-defined.

Proof

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({x 1,,x n},{x 1,,x n})CRing([x 1,,x n],[x 1,,x n])S_n \stackrel{\cong}{\to} Set(\{x_1, \ldots, x_n\}, \{x_1, \ldots, x_n\}) \to CRing(\mathbb{Z}[x_1, \ldots, x_n], \mathbb{Z}[x_1, \ldots, x_n])

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.)

Computations

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.

Revised on November 25, 2012 20:44:24 by Todd Trimble (67.81.93.16)