1 Definition

An odd permutation is a permutation that can be written as a product of an odd number of transpositions. It belongs to one of the two parity classes of permutations, the other being the even permutations. Although a particular permutation may admit many different decompositions into transpositions, the parity of the number of transpositions is always the same.

1.1 Permutations and transpositions

A permutation rearranges the elements of a finite set. In the symmetric group on \(n\) objects, every permutation can be expressed as a product of transpositions, where each transposition swaps two elements and leaves the rest fixed. This makes transpositions a basic building block for studying permutation structure.

1.2 Odd parity criterion

A permutation is odd when any transposition decomposition uses an odd number of swaps. The parity does not depend on the chosen decomposition. This invariant provides a simple way to classify permutations into odd and even types.

1.3 Equivalent characterizations

Odd permutations can be identified in several equivalent ways. These descriptions are often used interchangeably in group theory and combinatorics.

1.3.1 Product of an odd number of swaps

The most direct definition is that an odd permutation is a product of an odd number of transpositions. For example, a single transposition is odd, while a product of three transpositions is also odd.

1.3.2 Sign of a permutation

Each permutation has a sign, written \(+1\) for even permutations and \(-1\) for odd permutations. The sign is a multiplicative invariant that records the parity class of the permutation. An odd permutation has sign \(-1\).

1.3.3 Inversion count parity

For a permutation written in one-line notation, an inversion is a pair of entries that appear in the wrong order. A permutation is odd exactly when its number of inversions is odd. This criterion is especially useful in combinatorial calculations.

2 Properties

Odd permutations have several structural properties that follow from permutation parity. These properties connect them to the algebraic behavior of symmetric and alternating groups.

2.1 Closure relations with even permutations

The set of even permutations forms a subgroup, while odd permutations do not form a subgroup by themselves. Multiplying two odd permutations yields an even permutation, and multiplying an odd permutation by an even permutation yields an odd permutation. Thus the odd permutations form a coset of the even subgroup.

2.2 Multiplication of permutation signs

The sign of a product equals the product of the signs. If two permutations are composed, their parities combine according to the usual multiplication rule for \(\pm 1\). This makes the sign a homomorphism from the symmetric group to a two-element group.

2.3 Inverse permutations

A permutation and its inverse always have the same parity. In particular, the inverse of an odd permutation is odd. This follows because taking inverses reverses the order of transpositions without changing how many appear.

2.4 Parity invariance

Parity is invariant under the choice of transposition decomposition. This means that any two ways of writing the same permutation as a product of transpositions must have the same parity of length. That fact is a foundational result in the theory of permutations.

3 Examples

Odd permutations appear naturally in small symmetric groups, in cycle notation, and in matrix form. These examples illustrate how parity is recognized in practice.

3.1 Odd permutations in small symmetric groups

In the symmetric group on two objects, the nontrivial swap is odd. In the symmetric group on three objects, each transposition is odd, while a 3-cycle is even. Such small cases help show how parity behaves across different permutation sizes.

3.2 Cycle notation examples

A transposition written in cycle notation, such as \((1\ 2)\), is odd. A 3-cycle such as \((1\ 2\ 3)\) can be expressed as two transpositions and is therefore even. More complicated permutations can be tested by decomposing them into cycles and then into transpositions.

3.3 Permutation matrices

A permutation matrix is obtained by permuting the rows or columns of an identity matrix. The determinant of a permutation matrix is \(+1\) for an even permutation and \(-1\) for an odd permutation. Thus matrix determinants provide another way to detect parity.

4 Counting odd permutations

Odd permutations are evenly distributed among all permutations of a fixed finite set. This symmetry is one reason permutation parity is so useful.

4.1 Equal distribution in symmetric groups

For \(n \ge 2\), exactly half of the permutations in the symmetric group on \(n\) objects are odd and half are even. The sign map partitions the group into two sets of equal size, one corresponding to each parity class.

4.2 Relation to factorial size

Since the symmetric group on \(n\) objects has \(n!\) elements, there are \(n!/2\) odd permutations when \(n \ge 2\). This count reflects the fact that the alternating group has index two in the symmetric group.

5 Connections to group theory

Permutation parity plays a central role in the internal structure of symmetric groups and in the definition of alternating groups. It is one of the simplest examples of a nontrivial group homomorphism.

5.1 Symmetric groups

The symmetric group contains both even and odd permutations. The sign function divides the group into two parity classes and reveals a natural quotient of size two. This makes parity a basic tool for analyzing symmetric-group structure.

5.2 Alternating groups

The alternating group is the set of even permutations. It is a normal subgroup of the symmetric group and captures the permutations of sign \(+1\). Odd permutations are precisely those outside this subgroup.

5.2.1 Index two subgroup structure

Because the alternating group has index two, every permutation is either even or odd, and the two classes form complementary cosets. Any odd permutation represents the nontrivial coset of the alternating group.

5.2.2 Generating sets and parity

Many generating sets for symmetric groups include odd permutations, since at least one odd element is needed to move beyond the alternating subgroup. Transpositions are a common example, and their odd parity makes them especially useful in generating the full symmetric group.

6 Applications

Permutation parity appears in algebra, counting arguments, and practical sorting problems. It provides a compact invariant that often simplifies analysis.

6.1 Determinants and linear algebra

The determinant of a matrix can be expanded as a sum over permutations, with each term weighted by the sign of the permutation. Odd permutations contribute negative terms. This sign pattern is essential in determinant formulas and in understanding how determinants change under row swaps.

6.2 Combinatorics and inversion statistics

In combinatorics, inversion counts are a standard way to study permutation order. Parity of the inversion number determines whether the permutation is odd or even. This link is used in enumeration, pattern analysis, and related statistics on permutation sets.

6.3 Puzzle and sorting interpretations

In sorting processes, each swap changes the parity of a permutation. This leads to simple observations about whether a target arrangement can be reached using a prescribed number of swaps. Similar ideas appear in puzzles where legal moves preserve or alter permutation parity.

Odd permutations are best understood alongside a few closely related notions. These concepts provide the surrounding framework for parity in symmetric groups.

7.1 Even permutations

Even permutations are those with sign \(+1\), or equivalently those expressible as a product of an even number of transpositions. They form the alternating group.

7.2 Transpositions

A transposition is a swap of two elements. Transpositions are the basic operations used to build arbitrary permutations and to define parity.

7.3 Permutation sign

The sign of a permutation is the map that assigns \(+1\) to even permutations and \(-1\) to odd permutations. It is a central invariant linking group theory and linear algebra.

7.4 Parity in algebraic structures

Parity also appears in broader algebraic settings, where objects may be classified as even or odd according to a grading or sign rule. In the case of permutations, this classification is one of the oldest and most familiar examples.