mindevice
Discrete Structures

Sign of a Permutation

Determines the sign sgn(π) = (−1)^(n−z) of a permutation from its disjoint cycle decomposition — even (+1) or odd (−1).

Two-line notation — π(i) below each position i.

π=\pi =
Degreen = 3

Explanation

Motivation

A permutation π\pi of {1,…,n}\{1, \dots, n\} is a bijection of that set onto itself. Every permutation can be written as a product of transpositions (swaps of two elements) — in many ways, but the parity of the number of transpositions is invariant. The sign (signum) sgn⁡(π)∈{+1,−1}\operatorname{sgn}(\pi) \in \{+1, -1\} records exactly that parity: +1+1 for an even permutation, −1-1 for an odd one.

The sign is everywhere: it defines the determinant through the Leibniz formula, the alternating group AnA_n (the kernel of the sign map), and the signs in countless combinatorial identities.

Formal definition

Write π\pi in one-line notation, i.e. as the list of images (π(1),π(2),…,π(n))\big(\pi(1), \pi(2), \dots, \pi(n)\big). Classically the sign is defined via inversions:

sgn⁡(π)≔∏1≤i<j≤nπ(i)−π(j)i−j=(−1)#{(i,j) : i<j, π(i)>π(j)}.\operatorname{sgn}(\pi) \coloneqq \prod_{1 \le i < j \le n} \frac{\pi(i) - \pi(j)}{i - j} = (-1)^{\#\{(i,j)\,:\, i < j,\ \pi(i) > \pi(j)\}}.

More practical — and the route this calculator takes — is the cycle decomposition. Every permutation factors uniquely into disjoint cycles. If zz is their number (fixed points count as 1-cycles), then

sgn⁡(π)=(−1) n−z.\operatorname{sgn}(\pi) = (-1)^{\,n - z}.

The exponent k=n−zk = n - z is the minimum number of transpositions whose product is π\pi: a cycle of length ℓ\ell is a product of ℓ−1\ell - 1 transpositions, and the cycle lengths sum to nn.

Worked example

Take π=(2,1,3)\pi = (2, 1, 3) in one-line notation — that is, π(1)=2\pi(1) = 2, π(2)=1\pi(2) = 1, π(3)=3\pi(3) = 3 (the calculator's preset above).

Find the cycles. Start at 11: 1↦2↦11 \mapsto 2 \mapsto 1 closes the cycle (1 2)(1\ 2). That leaves 33: 3↦33 \mapsto 3 is the fixed point (3)(3). So

π=(1 2)(3),z=2.\pi = (1\ 2)(3), \qquad z = 2.

Compute the sign. With n=3n = 3 and z=2z = 2:

sgn⁡(π)=(−1) n−z=(−1) 3−2=(−1)1=−1.\operatorname{sgn}(\pi) = (-1)^{\,n - z} = (-1)^{\,3 - 2} = (-1)^{1} = -1.

So π\pi is odd — as is plain to see: π=(1 2)\pi = (1\ 2) is a single transposition.

Common mistakes

  • Forgetting fixed points: zz counts all cycles, including 1-cycles. Drop the fixed points and the exponent n−zn - z comes out wrong.
  • Mixing one-line and cycle notation: (2,1,3)(2, 1, 3) as one-line notation is the permutation with π(1)=2\pi(1) = 2 — not the cycle (2 1 3)(2\ 1\ 3).
  • Not a valid permutation: each of 1,…,n1, \dots, n must appear exactly once. Duplicate or missing values are not a permutation — the calculator rejects such input.
  • Confusing parity with the value: the sign is always +1+1 or −1-1, never the exponent itself.