Hubbry Logo
Parity of a permutationParity of a permutationMain
Open search
Parity of a permutation
Community hub
Parity of a permutation
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Parity of a permutation
Parity of a permutation
Parity of a permutation
View on Wikipedia
from Wikipedia
Permutations of 4 elements

Odd permutations have a green or orange background. The numbers in the right column are the inversion numbers (sequence A034968 in the OEIS), which have the same parity as the permutation.

In mathematics, when X is a finite set with at least two elements, the permutations of X (i.e. the bijective functions from X to X) fall into two classes of equal size: the even permutations and the odd permutations. If any total ordering of X is fixed, the parity (oddness or evenness) of a permutation of X can be defined as the parity of the number of inversions for σ, i.e., of pairs of elements x, y of X such that x < y and σ(x) > σ(y).

The sign, signature, or signum of a permutation σ is denoted sgn(σ) and defined as +1 if σ is even and −1 if σ is odd. The signature defines the alternating character of the symmetric group Sn. Another notation for the sign of a permutation is given by the more general Levi-Civita symbol (εσ), which is defined for all maps from X to X, and has value zero for non-bijective maps.

The sign of a permutation can be explicitly expressed as

sgn(σ) = (−1)N(σ)

where N(σ) is the number of inversions in σ.

Alternatively, the sign of a permutation σ can be defined from its decomposition into the product of transpositions as

sgn(σ) = (−1)m

where m is the number of transpositions in the decomposition. Although such a decomposition is not unique, the parity of the number of transpositions in all decompositions is the same, implying that the sign of a permutation is well-defined.[1]

Example

[edit]

Consider the permutation σ of the set {1, 2, 3, 4, 5} defined by and In one-line notation, this permutation is denoted 34521. It can be obtained from the identity permutation 12345 by three transpositions: first exchange the numbers 2 and 4, then exchange 3 and 5, and finally exchange 1 and 3. This shows that the given permutation σ is odd. Following the method of the cycle notation article, this could be written, composing from right to left, as

There are many other ways of writing σ as a composition of transpositions, for instance

σ = (1 5)(3 4)(2 4)(1 2)(2 3),

but it is impossible to write it as a product of an even number of transpositions.

Properties

[edit]

The identity permutation is an even permutation.[1] An even permutation can be obtained as the composition of an even number (and only an even number) of exchanges (called transpositions) of two elements, while an odd permutation can be obtained by (only) an odd number of transpositions.

The following rules follow directly from the corresponding rules about addition of integers:[1]

  • the composition of two even permutations is even
  • the composition of two odd permutations is even
  • the composition of an odd and an even permutation is odd

From these it follows that

  • the inverse of every even permutation is even
  • the inverse of every odd permutation is odd

Considering the symmetric group Sn of all permutations of the set {1, ..., n}, we can conclude that the map

sgn: Sn → {−1, 1} 

that assigns to every permutation its signature is a group homomorphism.[2]

Furthermore, we see that the even permutations form a subgroup of Sn.[1] This is the alternating group on n letters, denoted by An.[3] It is the kernel of the homomorphism sgn.[4] The odd permutations cannot form a subgroup, since the composite of two odd permutations is even, but they form a coset of An (in Sn).[5]

If n > 1, then there are just as many even permutations in Sn as there are odd ones;[3] consequently, An contains n!/2 permutations. (The reason is that if σ is even then (1  2)σ is odd, and if σ is odd then (1  2)σ is even, and these two maps are inverse to each other.)[3]

A cycle is even if and only if its length is odd. This follows from formulas like

In practice, in order to determine whether a given permutation is even or odd, one writes the permutation as a product of disjoint cycles. The permutation is odd if and only if this factorization contains an odd number of even-length cycles.

Another method for determining whether a given permutation is even or odd is to construct the corresponding permutation matrix and compute its determinant. The value of the determinant is the same as the parity of the permutation.

Every permutation of odd order must be even. The permutation (1 2)(3 4) in A4 shows that the converse is not true in general.

Equivalence of the two definitions

[edit]

This section presents proofs that the parity of a permutation σ can be defined in two equivalent ways:

  • as the parity of the number of inversions in σ (under any ordering); or
  • as the parity of the number of transpositions that σ can be decomposed to (however we choose to decompose it).
Proof 1

Let σ be a permutation on a ranked domain S. Every permutation can be produced by a sequence of transpositions (2-element exchanges). Let the following be one such decomposition

σ = T1 T2 ... Tk

We want to show that the parity of k is equal to the parity of the number of inversions of σ.

Every transposition can be written as a product of an odd number of transpositions of adjacent elements, e.g.

(2 5) = (2 3) (3 4) (4 5) (4 3) (3 2).

Generally, we can write the transposition (i i+d) on the set {1,...,i,...,i+d,...} as the composition of 2d−1 adjacent transpositions by recursion on d:

  • The base case d=1 is trivial.
  • In the recursive case, first rewrite (i, i+d) as (i, i+1) (i+1, i+d) (i, i+1). Then recursively rewrite (i+1, i+d) as adjacent transpositions.

If we decompose in this way each of the transpositions T1 ... Tk above, we get the new decomposition:

σ = A1 A2 ... Am

where all of the A1...Am are adjacent. Also, the parity of m is the same as that of k.

This is a fact: for all permutation τ and adjacent transposition a, aτ either has one less or one more inversion than τ. In other words, the parity of the number of inversions of a permutation is switched when composed with an adjacent transposition.

Therefore, the parity of the number of inversions of σ is precisely the parity of m, which is also the parity of k. This is what we set out to prove.

We can thus define the parity of σ to be that of its number of constituent transpositions in any decomposition. And this must agree with the parity of the number of inversions under any ordering, as seen above. Therefore, the definitions are indeed well-defined and equivalent.
Proof 2

An alternative proof uses the Vandermonde polynomial

So for instance in the case n = 3, we have

Now for a given permutation σ of the numbers {1, ..., n}, we define

Since the polynomial has the same factors as except for their signs, it follows that sgn(σ) is either +1 or −1. Furthermore, if σ and τ are two permutations, we see that

It can be shown that any transposition of two elements has signature −1, and thus we do indeed recover the signature as defined earlier.
Proof 3

A third approach uses the presentation of the group Sn in terms of generators τ1, ..., τn−1 and relations

  •   for all i
  •   for all i < n − 1
  •   if
[Here the generator represents the transposition (i, i + 1).] All relations keep the length of a word the same or change it by two. Starting with an even-length word will thus always result in an even-length word after using the relations, and similarly for odd-length words. It is therefore unambiguous to call the elements of Sn represented by even-length words "even", and the elements represented by odd-length words "odd".
Proof 4

Recall that a pair x, y such that x < y and σ(x) > σ(y) is called an inversion. We want to show that the count of inversions has the same parity as the count of 2-element swaps. To do that, we can show that every swap changes the parity of the count of inversions, no matter which two elements are being swapped and what permutation has already been applied. Suppose we want to swap the ith and the jth element. Clearly, inversions formed by i or j with an element outside of [i, j] will not be affected. For the n = j − i − 1 elements within the interval (i, j), assume vi of them form inversions with i and vj of them form inversions with j. If i and j are swapped, those vi inversions with i are gone, but n − vi inversions are formed. The count of inversions i gained is thus n − 2vi, which has the same parity as n.

Similarly, the count of inversions j gained also has the same parity as n. Therefore, the count of inversions gained by both combined has the same parity as 2n or 0. Now if we count the inversions gained (or lost) by swapping the ith and the jth element, we can see that this swap changes the parity of the count of inversions, since we also add (or subtract) 1 to the number of inversions gained (or lost) for the pair (i,j).

Note that initially when no swap is applied, the count of inversions is 0. Now we obtain equivalence of the two definitions of parity of a permutation.
Proof 5

Consider the elements that are sandwiched by the two elements of a transposition. Each one lies completely above, completely below, or in between the two transposition elements.

An element that is either completely above or completely below contributes nothing to the inversion count when the transposition is applied. Elements in-between contribute .

As the transposition itself supplies inversion, and all others supply 0 (mod 2) inversions, a transposition changes the parity of the number of inversions.

Other definitions and proofs

[edit]

The parity of a permutation of points is also encoded in its cycle structure.

Let σ = (i1 i2 ... ir+1)(j1 j2 ... js+1)...(ℓ1 ℓ2 ... ℓu+1) be the unique decomposition of σ into disjoint cycles, which can be composed in any order because they commute. A cycle (a b c ... x y z) involving k + 1 points can always be obtained by composing k transpositions (2-cycles):

so call k the size of the cycle, and observe that, under this definition, transpositions are cycles of size 1. From a decomposition into m disjoint cycles we can obtain a decomposition of σ into k1 + k2 + ... + km transpositions, where ki is the size of the ith cycle. The number N(σ) = k1 + k2 + ... + km is called the discriminant of σ, and can also be computed as

if we take care to include the fixed points of σ as 1-cycles.

Suppose a transposition (a b) is applied after a permutation σ. When a and b are in different cycles of σ then

,

and if a and b are in the same cycle of σ then

.

In either case, it can be seen that N((a b)σ) = N(σ) ± 1, so the parity of N((a b)σ) will be different from the parity of N(σ).

If σ = t1t2 ... tr is an arbitrary decomposition of a permutation σ into transpositions, by applying the r transpositions after t2 after ... after tr after the identity (whose N is zero) observe that N(σ) and r have the same parity. By defining the parity of σ as the parity of N(σ), a permutation that has an even length decomposition is an even permutation and a permutation that has one odd length decomposition is an odd permutation.

Remarks
  • A careful examination of the above argument shows that r ≥ N(σ), and since any decomposition of σ into cycles whose sizes sum to r can be expressed as a composition of r transpositions, the number N(σ) is the minimum possible sum of the sizes of the cycles in a decomposition of σ, including the cases in which all cycles are transpositions.
  • This proof does not introduce a (possibly arbitrary) order into the set of points on which σ acts.

Generalizations

[edit]

Parity can be generalized to Coxeter groups: one defines a length function ℓ(v), which depends on a choice of generators (for the symmetric group, adjacent transpositions), and then the function v ↦ (−1)ℓ(v) gives a generalized sign map.

See also

[edit]

Notes

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Parity of a permutation

View on Grokipedia
from Grokipedia
In group theory, the parity of a permutation refers to the classification of a permutation in the SnS_n (the group of all bijections from a of nn elements to itself) as either even or odd, based on the parity of the number of transpositions required to decompose it. A permutation is even if it can be expressed as a product of an even number of transpositions (2-cycles), and odd if the number is odd; this parity is invariant regardless of the specific decomposition chosen, ensuring a well-defined sgn⁡:Sn→{1,−1}\operatorname{sgn}: S_n \to \{1, -1\} where even permutations map to 1 and odd to -1. This is a , meaning sgn⁡(στ)=sgn⁡(σ)sgn⁡(τ)\operatorname{sgn}(\sigma \tau) = \operatorname{sgn}(\sigma) \operatorname{sgn}(\tau) for any permutations σ,τ∈Sn\sigma, \tau \in S_n, and it remains unchanged under inversion (sgn⁡(σ−1)=sgn⁡(σ)\operatorname{sgn}(\sigma^{-1}) = \operatorname{sgn}(\sigma)) or conjugation. For cycles, the parity follows a simple rule: a kk-cycle has sign (−1)k−1(-1)^{k-1}, so odd-length cycles are even permutations while even-length cycles are odd. These properties divide SnS_n (for n≥2n \geq 2) into two equal-sized classes of even and odd permutations, each comprising half of the n!n! total elements. The even permutations form a normal subgroup of SnS_n known as the alternating group AnA_n, which has index 2 and order n!/2n!/2; it is simple for n≥5n \geq 5, making it a fundamental object in the study of finite groups. Beyond group theory, permutation parity is central to linear algebra, appearing in the Leibniz formula for the determinant of an n×nn \times n matrix A=(aij)A = (a_{ij}), given by det⁡(A)=∑σ∈Snsgn⁡(σ)∏i=1nai,σ(i)\det(A) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) \prod_{i=1}^n a_{i,\sigma(i)}, where the sign weights each permutation term to capture the matrix's invertibility and orientation-preserving properties. It also arises in combinatorics (e.g., counting inversions), topology, and physics (e.g., distinguishing bosons and fermions in quantum mechanics via even and odd representations). Historically, the concept of permutation parity originated in the late 18th century with observations by Vandermonde and was proven by Cauchy in 1815; early 20th-century terminology referred to even permutations as "positive" and odd as "negative."

Basic Concepts

Definition

A permutation of a finite set XX with nn elements is a bijective function from XX to itself, rearranging the elements of the set. The collection of all such permutations, denoted SnS_n when X={1,2,…,n}X = \{1, 2, \dots, n\}, forms the under the operation of , which serves as the foundational structure for studying permutations in group theory. The parity of a permutation σ∈Sn\sigma \in S_n refers to whether σ\sigma is even or odd, determined intuitively by its into transpositions (2-cycles): σ\sigma is even if it can be written as a product of an even number of transpositions, and odd if an odd number. This even-odd distinction, known as the of the permutation, is independent of the specific used. In group theory, the parity induces a homomorphism δ:Sn→{±1}\delta: S_n \to \{\pm 1\}, where even permutations map to +1+1 and odd ones to −1-1, partitioning SnS_n into cosets. The kernel of this homomorphism is the AnA_n, the normal subgroup of all even permutations, which has index 2 in SnS_n and plays a central role in the structure of symmetric groups. The notion of permutation signs originated with early investigations by around 1770 in the context of polynomial equations, and was systematically developed by in papers from 1815 and 1844–45 on permutation groups. The specific term "parity," emphasizing the even-odd character, arose in the amid these foundational studies.

Examples

To illustrate the concept of parity, consider the S3S_3, which consists of all of the set {1,2,3}\{1, 2, 3\}. There are six elements in S3S_3, which can be expressed in cycle notation as follows: the identity permutation (1)(1), the transpositions (1 2)(1\,2), (1 3)(1\,3), and (2 3)(2\,3), and the 3-cycles (1 2 3)(1\,2\,3) and (1 3 2)(1\,3\,2). The even permutations are the identity and the two 3-cycles, while the odd permutations are the three transpositions.
Permutation (Cycle Notation)Parity
(1)(1) (identity)Even
(1 2 3)(1\,2\,3)Even
(1 3 2)(1\,3\,2)Even
(1 2)(1\,2)Odd
(1 3)(1\,3)Odd
(2 3)(2\,3)Odd
This classification can be visualized by considering how permutations rearrange the positions of 1, 2, and 3, akin to reflecting or rotating objects in space. Even permutations, such as the 3-cycle (1 2 3)(1\,2\,3), preserve the overall "" or orientation of the arrangement, similar to a , while odd permutations, like the transposition (1 2)(1\,2), reverse it, like a reflection. In the larger symmetric group S4S_4, which permutes {1,2,3,4}\{1, 2, 3, 4\}, parity applies similarly without needing to enumerate all 24 elements. For instance, the 4-cycle (1 2 3 4)(1\,2\,3\,4) is an odd permutation, the double transposition (1 2)(3 4)(1\,2)(3\,4) is even, and the single transposition (1 2)(1\,2) is odd. A common misconception is that the parity of a cycle matches its length's parity directly; in reality, even-length cycles like the 4-cycle are odd permutations, as their parity is determined by the number of transpositions needed to express them (an odd number in this case). The assigns +1+1 to even and −1-1 to odd ones, capturing this distinction succinctly.

Definitions

Inversion Count

An inversion in a π\pi of {1,2,…,n}\{1, 2, \dots, n\}, written in one-line notation as π=(π(1),π(2),…,π(n))\pi = (\pi(1), \pi(2), \dots, \pi(n)), is a pair of indices (i,j)(i, j) such that i<ji < j but π(i)>π(j)\pi(i) > \pi(j). This captures instances where a larger element appears before a smaller one in the sequence. The inversion count, denoted \inv(π)\inv(\pi), is the total number of such inversions in π\pi, formally given by \inv(π)=∑1≤i<j≤n1π(i)>π(j),\inv(\pi) = \sum_{1 \leq i < j \leq n} \mathbf{1}_{\pi(i) > \pi(j)}, where 1\mathbf{1} is the that equals 1 if the condition holds and 0 otherwise. The parity of the permutation is then determined by the parity of this count: π\pi is even if \inv(π)\inv(\pi) is even and odd if \inv(π)\inv(\pi) is odd, with the sign function defined as \sgn(π)=(−1)\inv(π)\sgn(\pi) = (-1)^{\inv(\pi)}. Equivalently, the parity is \inv(π)mod  2\inv(\pi) \mod 2. To compute the inversion count, examine all pairs (i,j)(i, j) with i<ji < j and check if π(i)>π(j)\pi(i) > \pi(j). Consider the example π=(2,1,3)\pi = (2, 1, 3):
  • For i=1,j=2i=1, j=2: π(1)=2>π(2)=1\pi(1)=2 > \pi(2)=1, so one inversion.
  • For i=1,j=3i=1, j=3: π(1)=2<π(3)=3\pi(1)=2 < \pi(3)=3, no inversion.
  • For i=2,j=3i=2, j=3: π(2)=1<π(3)=3\pi(2)=1 < \pi(3)=3, no inversion.
Thus, \inv(π)=1\inv(\pi) = 1, which is odd, so π\pi has odd parity and \sgn(π)=−1\sgn(\pi) = -1. This approach offers a direct combinatorial method to determine parity by pairwise comparisons, avoiding the need for decomposition into transpositions or cycles, and finds extensive use in enumerative combinatorics, such as in generating functions that track inversions across permutations.

Transposition Decomposition

Any permutation π\pi in the symmetric group SnS_n can be expressed as a product of transpositions. The parity of π\pi is defined to be even if the number of transpositions in such a decomposition is even, and odd if odd; the sign function is then sgn⁡(π)=(−1)k\operatorname{sgn}(\pi) = (-1)^k, where kk is the number of transpositions. This parity is independent of the choice of decomposition, as any two decompositions into transpositions have lengths congruent modulo 2. The symmetric group SnS_n is generated by the set of adjacent transpositions {(i i+1)∣i=1,…,n−1}\{(i\, i+1) \mid i=1,\dots,n-1\}, meaning every permutation can be written as a product of these generators. The parity of π\pi is thus the parity of the number of adjacent transpositions in such an expression. For example, algorithms like restore a permuted sequence to identity by swapping adjacent out-of-order elements, and the total number of such swaps determines the parity via the even or odd count. The cycle decomposition provides a direct way to compute this parity. A kk-cycle decomposes into k−1k-1 transpositions, so its sign is (-1)^{k-1}. For a permutation π\pi whose disjoint cycle decomposition consists of cycles of lengths k1,…,kmk_1, \dots, k_m (including 1-cycles for fixed points), the sign is the product over the cycle signs: sgn⁡(π)=∏i=1m(−1)ki−1=(−1)∑i=1m(ki−1).\operatorname{sgn}(\pi) = \prod_{i=1}^m (-1)^{k_i - 1} = (-1)^{\sum_{i=1}^m (k_i - 1)}. Since ∑ki=n\sum k_i = n, this simplifies to ∑(ki−1)=n−m\sum (k_i - 1) = n - m, where m=c(π)m = c(\pi) is the total number of cycles including fixed points. Thus, sgn⁡(π)=(−1)n−c(π).[](https://kconrad.math.uconn.edu/blurbs/grouptheory/sign.pdf)\operatorname{sgn}(\pi) = (-1)^{n - c(\pi)}.[](https://kconrad.math.uconn.edu/blurbs/grouptheory/sign.pdf) As an example, the 3-cycle π=(1 2 3)\pi = (1\, 2\, 3) in S3S_3 decomposes as (1 2 3)=(1 3)(1 2)(1\, 2\, 3) = (1\, 3)(1\, 2), a product of two transpositions, confirming even parity with sgn⁡(π)=1\operatorname{sgn}(\pi) = 1. In cycle terms, it has one cycle of length 3 (c(π)=1c(\pi) = 1), so sgn⁡(π)=(−1)3−1=1\operatorname{sgn}(\pi) = (-1)^{3-1} = 1. This definition via transpositions is equivalent to the parity of the inversion count of the permutation.

Equivalence and Proofs

Equivalence Proof

The equivalence between the two definitions of the parity of a permutation is established by the following theorem: for any permutation π∈Sn\pi \in S_n, the sign sgn⁡(π)\operatorname{sgn}(\pi) defined as (−1)inv⁡(π)(-1)^{\operatorname{inv}(\pi)}, where inv⁡(π)\operatorname{inv}(\pi) is the number of inversions of π\pi, equals the sign defined as (−1)k(-1)^k, where kk is the number of transpositions in any decomposition of π\pi into a product of transpositions. To prove this, first consider adjacent transpositions, which are transpositions of the form τi,i+1=(i i+1)\tau_{i,i+1} = (i \ i+1). A key lemma states that multiplying a permutation by an adjacent transposition changes the number of inversions by exactly 1. Specifically, for any π∈Sn\pi \in S_n and adjacent transposition τ=(k k+1)\tau = (k \ k+1), ∣inv⁡(τπ)−inv⁡(π)∣=1|\operatorname{inv}(\tau \pi) - \operatorname{inv}(\pi)| = 1. This holds because the inversions of τπ\tau \pi differ from those of π\pi only in pairs involving the images under π\pi of positions that interact with kk and k+1k+1; if π(k)<π(k+1)\pi(k) < \pi(k+1), then τπ\tau \pi introduces exactly one new inversion, and vice versa. Next, note that every transposition (not necessarily adjacent) can be expressed as a product of an odd number of adjacent transpositions. For example, the transposition (i j)(i \ j) with j>i+1j > i+1 decomposes into 2(j−i)−12(j-i)-1 adjacent transpositions, which is odd. Thus, any general transposition is an odd permutation in the sense of adjacent transpositions, and the parity remains consistent. The full proof proceeds by induction on the number mm of (general) transpositions in a π=τ1τ2⋯τm\pi = \tau_1 \tau_2 \cdots \tau_m. For the base case m=0m=0, π\pi is the identity, which has zero inversions (even) and even parity. Assume the result holds for decompositions with fewer than mm transpositions. Each τi\tau_i can be written as an odd product of adjacent transpositions, so π\pi is a product of an odd total number of adjacent transpositions if mm is odd, and even if mm is even. By iterated application of the adjacent transposition lemma, each such multiplication changes the inversion count by an odd amount (specifically, ±1, which is odd), so the total change in inversions from the identity has the same parity as mm. Thus, inv⁡(π)\operatorname{inv}(\pi) and mm have the same parity. A supporting lemma confirms that under multiplication by an odd permutation (such as a transposition), the number of inversions changes by an odd amount overall. This ensures consistency across decompositions. Therefore, both definitions yield the same from the SnS_n to {±1}\{ \pm 1 \}, where even permutations map to +1+1 and odd to −1-1.

Alternative Proofs

One alternative definition of the parity of a permutation π∈Sn\pi \in S_n is given by the of its associated PπP_\pi, where (Pπ)i,j=1(P_\pi)_{i,j} = 1 if j=π(i)j = \pi(i) and 0 otherwise. This matrix represents the linear transformation that permutes the vectors according to π\pi. The det⁡(Pπ)\det(P_\pi) equals +1+1 if π\pi is even and −1-1 if π\pi is odd, providing a well-defined parity independent of decomposition into transpositions or inversions. To see this equivalence, apply the Leibniz formula for the : det⁡(Pπ)=∑σ∈Sn\sgn(σ)∏i=1n(Pπ)i,σ(i),\det(P_\pi) = \sum_{\sigma \in S_n} \sgn(\sigma) \prod_{i=1}^n (P_\pi)_{i, \sigma(i)}, where \sgn(σ)\sgn(\sigma) is the sign from the standard transposition definition. The product ∏i=1n(Pπ)i,σ(i)\prod_{i=1}^n (P_\pi)_{i, \sigma(i)} is nonzero only when σ=π\sigma = \pi, as it requires 11s exactly on the positions defined by π\pi; otherwise, it includes a 0. Thus, the sum reduces to a single term \sgn(π)⋅1=\sgn(π)\sgn(\pi) \cdot 1 = \sgn(\pi), confirming that the determinant matches the transposition-based sign. This approach leverages properties of to verify the parity's consistency, as the determinant is uniquely defined via row reduction or cofactor expansion, yielding ±1\pm 1 for permutation matrices. Another perspective uses exponential generating functions to demonstrate that the number of even permutations equals the number of odd permutations for n≥2n \geq 2, reinforcing the bipartition implied by any consistent parity definition. The exponential generating function for the signed sum over permutations is derived from the , where the of a permutation equals (−1)n−c(π)(-1)^{n - c(\pi)} and c(π)c(\pi) is the number of cycles (equivalent to the transposition parity via the relation that a kk-cycle has (−1)k−1(-1)^{k-1}). The relevant exponent is ∑k=1∞(−1)k−1xkk=log⁡(1+x)\sum_{k=1}^\infty (-1)^{k-1} \frac{x^k}{k} = \log(1 + x), so the generating function is exp⁡(log⁡(1+x))=1+x\exp(\log(1 + x)) = 1 + x. The coefficients imply ∑π∈Snsgn⁡(π)=0\sum_{\pi \in S_n} \operatorname{sgn}(\pi) = 0 for n>1n > 1, hence ∣An∣=n!/2|A_n| = n!/2. This approach confirms the balanced count without direct , assuming the cycle-based aligns with transpositions. A topological interpretation views the parity through braid diagrams, offering an invariant geometric proof of its well-definedness. Represent π\pi as a on nn strands by connecting the top endpoint ii to the bottom π(i)\pi(i) with straight lines in the plane, then count the crossings modulo 2. Each crossing corresponds to an inversion, and the total crossing parity equals the permutation's . Reidemeister moves, which preserve the class, change the crossing number by an even amount, ensuring the parity is invariant across equivalent diagrams. Closing the braid to a link further ties this to invariants, but the finite crossing flip (one change alters parity by 1) limits the argument to the permutation case. This homomorphism to Z/2Z\mathbb{Z}/2\mathbb{Z} (forgetting information) proves the 's independence from presentation. Historically, Augustin-Louis Cauchy provided an early 19th-century proof of parity equivalence in his 1815 memoir, using cycle decompositions and fixed-point-free involutions to count even and odd permutations separately. Cauchy showed that every permutation decomposes into disjoint cycles, with the sign determined by the parity of the sum of (cycle length minus one) over cycles, equivalent to the number of even-length cycles modulo 2. For fixed-point-free involutions (pairings without 1-cycles), he paired even and odd cases via conjugation or substitution, demonstrating equal counts without relying on inversions. This argument, predating modern group theory, established the sign homomorphism's consistency by induction on cycle structure, influencing later algebraic developments.

Properties

Algebraic Properties

The sign function, denoted sgn⁡:Sn→{±1}\operatorname{sgn}: S_n \to \{\pm 1\}, maps each to +1+1 if it is even and −1-1 if it is odd, and it is a satisfying sgn⁡(πτ)=sgn⁡(π)sgn⁡(τ)\operatorname{sgn}(\pi \tau) = \operatorname{sgn}(\pi) \operatorname{sgn}(\tau) for all π,τ∈Sn\pi, \tau \in S_n. The kernel of this homomorphism is precisely the AnA_n, consisting of all even permutations, while the image is the {±1}\{\pm 1\}. Consequently, AnA_n is a of SnS_n of index 2. For n≥5n \geq 5, the AnA_n is simple, meaning it has no nontrivial normal other than itself and the trivial . This underscores the fundamental role of parity in the structure of s, as AnA_n captures the "even" half of SnS_n without further normal decomposition. In the SnS_n, conjugacy classes are determined by cycle type, and since the parity of a permutation depends on its cycle structure—specifically, sgn⁡(π)=(−1)n−c(π)\operatorname{sgn}(\pi) = (-1)^{n - c(\pi)} where c(π)c(\pi) is the number of cycles (including fixed points)—conjugate permutations share the same parity. Thus, each lies entirely within either the even or odd permutations, preserving parity under conjugation. Equivalently, in additive notation, the parity⁡:Sn→Z/2Z\operatorname{parity}: S_n \to \mathbb{Z}/2\mathbb{Z} (where even permutations map to 0 and odd to 1) satisfies parity⁡(π∘τ)=parity⁡(π)+parity⁡(τ)(mod2)\operatorname{parity}(\pi \circ \tau) = \operatorname{parity}(\pi) + \operatorname{parity}(\tau) \pmod{2} for all π,τ∈Sn\pi, \tau \in S_n, reflecting the property modulo 2. The parity homomorphism also influences solvability: SnS_n is solvable n≤4n \leq 4, as for n≥5n \geq 5, the normal series {e}⊴An⊴Sn\{e\} \trianglelefteq A_n \trianglelefteq S_n features a simple non-abelian factor AnA_n (not solvable) and a Z/2Z\mathbb{Z}/2\mathbb{Z}, preventing overall solvability. Similarly, AnA_n itself is not solvable for n≥5n \geq 5 due to its simplicity.

Combinatorial Properties

The parity of a permutation, defined as the parity of its number of inversions, leads to a balanced partition of the SnS_n into even and odd permutations for n≥2n \geq 2. Combinatorially, this equality arises from the inversion Pn(q)=∑π∈Snqinv⁡(π)P_n(q) = \sum_{\pi \in S_n} q^{\operatorname{inv}(\pi)}, which equals the qq-factorial q!=∏k=1n1−qk1−q_q! = \prod_{k=1}^n \frac{1 - q^k}{1 - q}. Evaluating at q=−1q = -1 yields Pn(−1)=0P_n(-1) = 0 for n≥2n \geq 2, since the numerator includes the factor 1−(−1)2=01 - (-1)^2 = 0; thus, the alternating sum over inversion counts is zero, implying the number of permutations with even inversions equals those with odd inversions, each n!/2n!/2. Let I(n,k)I(n,k) denote the Mahonian number, the count of permutations in SnS_n with exactly kk inversions; then the number of even permutations is ∑k≡0(mod2)I(n,k)\sum_{k \equiv 0 \pmod{2}} I(n,k). Every permutation π∈Sn\pi \in S_n corresponds uniquely to an inversion table I(π)=(a1,a2,…,an)I(\pi) = (a_1, a_2, \dots, a_n), where aja_j is the number of entries to the left of jj in the one-line notation of π\pi that exceed jj, satisfying 0≤aj≤j−10 \leq a_j \leq j-1. The total number of inversions is the ∑j=1naj\sum_{j=1}^n a_j, so the parity of π\pi is the parity of this modulo 2. This representation facilitates enumerative studies, as the for inversion tables tracks the distribution of these entries, directly linking to Mahonian statistics where qq enumerates inversions. The Mahonian numbers I(n,k)I(n,k) form the coefficients of the qq-analog of the , providing a refined count that incorporates inversion parity through evaluation techniques like the one at q=−[1](/page/−1)q = -[1](/page/−1). For instance, the sign homomorphism, which assigns +1+1 to even permutations and −[1](/page/−1)-[1](/page/−1) to odd ones, can be viewed combinatorially as extracting the parity imbalance from these generating functions, confirming the equality without . In sorting applications, the parity manifests in algorithms like bubble sort, where each adjacent swap resolves exactly one inversion, so the total number of swaps equals the inversion count and thus has the same parity as the permutation. For an odd permutation, bubble sort requires an odd number of such swaps to reach the identity.

Applications and Generalizations

Relation to Determinants

The determinant of an n×nn \times n matrix A=(aij)A = (a_{ij}) is given by the Leibniz formula: det⁡(A)=∑π∈Snsign⁡(π)∏i=1nai,π(i),\det(A) = \sum_{\pi \in S_n} \operatorname{sign}(\pi) \prod_{i=1}^n a_{i, \pi(i)}, where the sum is over all permutations π\pi in the SnS_n, and sign⁡(π)\operatorname{sign}(\pi) is the parity of π\pi. This formula incorporates the parity to ensure the alternating multilinear properties of the determinant, distinguishing it from the permanent, which omits the sign factor. A permutation matrix PπP_\pi corresponding to π∈Sn\pi \in S_n is the n×nn \times n matrix with entries (Pπ)i,j=δi,π(j)(P_\pi)_{i,j} = \delta_{i, \pi(j)}, where δ\delta is the (1 if indices match, 0 otherwise). The of such a matrix equals the of the : det⁡(Pπ)=sign⁡(π)\det(P_\pi) = \operatorname{sign}(\pi). For example, in the case n=2n=2, the identity yields Pid=(1001),det⁡(Pid)=1=sign⁡(id),P_{id} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad \det(P_{id}) = 1 = \operatorname{sign}(id), while the transposition (1 2)(1\ 2) gives P(1 2)=(0110),det⁡(P(1 2))=−1=sign⁡((1 2)).P_{(1\ 2)} = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \quad \det(P_{(1\ 2)}) = -1 = \operatorname{sign}((1\ 2)). This relation follows from the Leibniz formula applied to PπP_\pi, where only the identity product contributes without sign alternation except for the parity effect. In linear algebra, the parity of a determines whether the associated linear transformation preserves or reverses orientation. For a via an even ( +1), the transformation has positive and preserves the orientation of the ; an odd ( -) reverses it. This is evident in row operations: swapping two rows of a matrix, an odd , multiplies the by -, flipping the and thus reversing orientation. For a 2×2 matrix (abcd)\begin{pmatrix} a & b \\ c & d \end{pmatrix} with det⁡=ad−bc>0\det = ad - bc > 0, swapping rows yields (cdab)\begin{pmatrix} c & d \\ a & b \end{pmatrix} with det⁡=cb−da=−(ad−bc)<0\det = cb - da = -(ad - bc) < 0./08%3A_Permutations_and_the_Determinant/8.02%3A_Determinants) The Leibniz formula traces its origins to around 1693, who developed early expressions for 3×3 in the context of solving linear systems. advanced the theory in 1812, providing a general treatment and introducing the permanent as the signless analogue per⁡(A)=∑π∈Sn∏i=1nai,π(i)\operatorname{per}(A) = \sum_{\pi \in S_n} \prod_{i=1}^n a_{i, \pi(i)} to contrast with the alternating . This distinction highlights the role of permutation parity in capturing antisymmetry essential to .

Generalizations to Other Structures

The concept of parity extends naturally to signed permutations, which form the hyperoctahedral group BnB_n, consisting of all bijections of {1,…,n}\{1, \dots, n\} that may include sign changes on elements. In this setting, the sign of a signed permutation σ\sigma is defined as sgn⁡(σ)=sgn⁡(π)∏i=1nsgn⁡(σ(i))\operatorname{sgn}(\sigma) = \operatorname{sgn}(\pi) \prod_{i=1}^n \operatorname{sgn}(\sigma(i)), where π\pi is the underlying unsigned permutation obtained by ignoring signs, and the product accounts for the number of negative signs. This total sign equals (−1)ℓ(σ)(-1)^{\ell(\sigma)}, where ℓ(σ)\ell(\sigma) is the Coxeter length of σ\sigma with respect to the standard generators of BnB_n. More broadly, parity generalizes to arbitrary s via the function ℓ(w)\ell(w) relative to a fixed set of simple reflections. The parity of an element ww is ℓ(w)mod  2\ell(w) \mod 2, which defines a nontrivial from the to {±1}\{\pm 1\}, known as the sign representation, where ε(w)=(−1)ℓ(w)\varepsilon(w) = (-1)^{\ell(w)}. In Weyl groups, which are finite s arising in , this parity plays a key role in distinguishing even and odd elements, analogous to the subgroup in the symmetric case. In the context of Young tableaux, the Robinson–Schensted–Knuth (RSK) correspondence maps a σ∈Sn\sigma \in S_n to a pair of standard Young tableaux (P,Q)(P, Q) of the same shape. The of σ\sigma equals the product of the signs of the row-reading permutations of PP and QQ, where the sign of a tableau is that of the permutation obtained by reading entries row by row. This relation preserves the parity under the , linking combinatorial structures to the . Modular generalizations adapt parity to settings over finite fields or via q-analogs. Over characteristic not 2, the homomorphism persists in general linear groups, but in characteristic 2, parity collapses as even and odd permutations coincide. q-Analogs replace the with representations of Hecke algebras, where the q-sign sends the generator TiT_i to −q-q, yielding a deformation that recovers the classical parity at q=1; this appears in q-analogs of the via Schur-Weyl duality over quantum groups. In , parity distinguishes irreducible characters of the AnA_n from those of SnS_n: the sign representation of SnS_n restricts to the trivial representation on AnA_n, splitting characters into even and odd types, with applications in decomposing tensor products and computing branching rules.

References

  1. https://kconrad.math.uconn.edu/blurbs/grouptheory/sign.pdf
  2. https://gubner.ece.wisc.edu/notes/PermutationsAndDeterminants.pdf
  3. https://phys.libretexts.org/Bookshelves/Quantum_Mechanics/Quantum_Mechanics_III_(Chong)/04:_Identical_Particles/4.02:_Symmetric_and_Antisymmetric_States
  4. https://www.jstor.org/stable/2316272
  5. https://math.libretexts.org/Courses/Mount_Royal_University/Abstract_Algebra_I/Chapter_3%253A_Permutation_Groups/3.1%253A_Symmetric_Groups
  6. http://ramanujan.math.trinity.edu/rdaileda/teach/s19/m3362/alternating.pdf
  7. https://nonagon.org/ExLibris/cauchy-permutations-origin-group-theory
  8. https://www.math.uwaterloo.ca/~snew/pmath336-2024-S/Notes/Chap3SymmetricGroup.pdf
  9. https://math.stackexchange.com/questions/883539/intuitive-explanation-of-even-odd-permutation
  10. http://www.sfu.ca/~jtmulhol/math302/notes/302notes-Sep06-2019.pdf
  11. https://www.math.ucdavis.edu/~linear/old/notes12.pdf
  12. https://dlmf.nist.gov/26.13
  13. https://www.math.purdue.edu/~arapura/algebra/algebra11.pdf
  14. https://www.math.clemson.edu/~macaule/classes/m20_math4120/slides/math4120_lecture-2-03_h.pdf
  15. http://buzzard.ups.edu/courses/2021spring/transcripts/390-2021-04-22.pdf
  16. https://people.tamu.edu/~yvorobets/MATH433-2010B/Lect2-03web.pdf
  17. http://web.stanford.edu/class/math51h/permutations.pdf
  18. https://web.mit.edu/18.06/www/Spring16/lecture23.pdf
  19. https://math.berkeley.edu/~mhaiman/math172-spring10/exponential.pdf
  20. https://math.ou.edu/~nbrady/teaching/s16-2513/perm.pdf
  21. https://gallica.bnf.fr/ark:/12148/bpt6k90193x/f73.item
  22. https://kconrad.math.uconn.edu/blurbs/grouptheory/Ansimple.pdf
  23. https://kconrad.math.uconn.edu/blurbs/grouptheory/conjclass.pdf
  24. https://www.math.mcgill.ca/goren/AlgebraII/permutations.pdf
  25. https://resources.saylor.org/wwwresources/archived/site/wp-content/uploads/2011/04/Symmetric-group.pdf
  26. http://ramanujan.math.trinity.edu/rdaileda/teach/s23/m3362/alternating.pdf
  27. https://web.stanford.edu/~lindrew/18.212.pdf
  28. https://users.math.msu.edu/users/bsagan/Books/Aoc/final.pdf
  29. https://www.geeksforgeeks.org/dsa/number-swaps-sort-adjacent-swapping-allowed/
  30. https://www.sciencedirect.com/science/article/pii/S0047259X12001765
  31. https://www.math.ucdavis.edu/~anne/WQ2007/mat67-Lm-Determinant.pdf
  32. https://people.computing.clemson.edu/~goddard/texts/linearMatrix/chap4.pdf
  33. https://files.vipulnaik.com/math-196/geometryoflineartransformations.pdf
  34. https://mathshistory.st-andrews.ac.uk/HistTopics/Matrices_and_determinants/
  35. https://www.math.purdue.edu/~iswanso/GriecoGuerrieriS.pdf
  36. https://www-users.cse.umn.edu/~reiner/Papers/SignedPermStats2_EJC.pdf
  37. https://arxiv.org/abs/math/0601607
Add your contribution
Related Hubs
User Avatar
No comments yet.