Parity of a permutation
In group theory, the parity of a permutation refers to the classification of a permutation in the symmetric group S_n (the group of all bijections from a finite set of n elements to itself) as either even or odd, based on the parity of the number of transpositions required to decompose it.[1] 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 sign function \operatorname{sgn}: S_n \to \{1, -1\} where even permutations map to 1 and odd to -1.[1] This sign is a multiplicative group homomorphism, meaning \operatorname{sgn}(\sigma \tau) = \operatorname{sgn}(\sigma) \operatorname{sgn}(\tau) for any permutations \sigma, \tau \in S_n, and it remains unchanged under inversion (\operatorname{sgn}(\sigma^{-1}) = \operatorname{sgn}(\sigma)) or conjugation.[1] For cycles, the parity follows a simple rule: a k-cycle has sign (-1)^{k-1}, so odd-length cycles are even permutations while even-length cycles are odd.[1] These properties divide S_n (for n \geq 2) into two equal-sized classes of even and odd permutations, each comprising half of the n! total elements. The even permutations form a normal subgroup of S_n known as the alternating group A_n, which has index 2 and order n!/2; it is simple for n \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 \times n matrix A = (a_{ij}), given by \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.[2] 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).[1][3] 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."[1][4]Basic Concepts
Definition
A permutation of a finite set X with n elements is a bijective function from X to itself, rearranging the elements of the set. The collection of all such permutations, denoted S_n when X = \{1, 2, \dots, n\}, forms the symmetric group under the operation of function composition, which serves as the foundational structure for studying permutations in group theory.[5] The parity of a permutation \sigma \in S_n refers to whether \sigma is even or odd, determined intuitively by its decomposition 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 sign of the permutation, is independent of the specific decomposition used.[1] In group theory, the parity induces a sign homomorphism \delta: S_n \to \{\pm 1\}, where even permutations map to +1 and odd ones to -1, partitioning S_n into cosets. The kernel of this homomorphism is the alternating group A_n, the normal subgroup of all even permutations, which has index 2 in S_n and plays a central role in the structure of symmetric groups.[6] The notion of permutation signs originated with early investigations by Joseph-Louis Lagrange around 1770 in the context of polynomial equations, and was systematically developed by Augustin-Louis Cauchy in papers from 1815 and 1844–45 on permutation groups. The specific term "parity," emphasizing the even-odd character, arose in the 19th century amid these foundational studies.[7][4]Examples
To illustrate the concept of parity, consider the symmetric group S_3, which consists of all permutations of the set \{1, 2, 3\}. There are six elements in S_3, which can be expressed in cycle notation as follows: the identity permutation (1), the transpositions (1\,2), (1\,3), and (2\,3), and the 3-cycles (1\,2\,3) and (1\,3\,2).[8] The even permutations are the identity and the two 3-cycles, while the odd permutations are the three transpositions.[1][8]| Permutation (Cycle Notation) | Parity |
|---|---|
| (1) (identity) | Even |
| (1\,2\,3) | Even |
| (1\,3\,2) | Even |
| (1\,2) | Odd |
| (1\,3) | Odd |
| (2\,3) | Odd |
Definitions
Inversion Count
An inversion in a permutation \pi of \{1, 2, \dots, n\}, written in one-line notation as \pi = (\pi(1), \pi(2), \dots, \pi(n)), is a pair of indices (i, j) such that i < j but \pi(i) > \pi(j).[11] This captures instances where a larger element appears before a smaller one in the sequence. The inversion count, denoted \inv(\pi), is the total number of such inversions in \pi, formally given by \inv(\pi) = \sum_{1 \leq i < j \leq n} \mathbf{1}_{\pi(i) > \pi(j)}, where \mathbf{1} is the indicator function that equals 1 if the condition holds and 0 otherwise.[11] The parity of the permutation is then determined by the parity of this count: \pi is even if \inv(\pi) is even and odd if \inv(\pi) is odd, with the sign function defined as \sgn(\pi) = (-1)^{\inv(\pi)}.[11] Equivalently, the parity is \inv(\pi) \mod 2.[12] To compute the inversion count, examine all pairs (i, j) with i < j and check if \pi(i) > \pi(j). Consider the example \pi = (2, 1, 3):- For i=1, j=2: \pi(1)=2 > \pi(2)=1, so one inversion.
- For i=1, j=3: \pi(1)=2 < \pi(3)=3, no inversion.
- For i=2, j=3: \pi(2)=1 < \pi(3)=3, no inversion.