Permutation group

Permutation group of a type

DefinitionDecomposition into transpositions #

The decomposition into transpositions expresses every permutation of a finite set as a product of transpositions, permutations that exchange two elements and fix all the others. It shows that the transpositions generate the symmetric group, which makes them the basic building blocks for computing with permutations and for proving facts about all of them at once. The decomposition is far from unique, but the parity of the number of factors is determined by the permutation: it is recorded by the signature, which equals $(-1)^m$ for any decomposition into $m$ transpositions.

Statement

Let $X$ be a finite set. A transposition of $X$ is a permutation that exchanges two distinct elements $a \neq b$ and fixes every other element; it is written $(a\ b)$. Then every permutation $\sigma$ of $X$ is a product of transpositions:

\[\sigma = \tau_1 \tau_2 \cdots \tau_m,\]

where each $\tau_i$ is a transposition and products are compositions, so that $\tau_m$ is applied first. The identity is the empty product, with $m = 0$. If $X$ has $n \ge 1$ elements, the factors can be chosen so that $m \le n - 1$.

Examples

A cycle of length $k$ is a product of $k - 1$ transpositions. One choice is $$(a_1\ a_2\ \cdots\ a_k) = (a_1\ a_2)(a_2\ a_3)\cdots(a_{k-1}\ a_k),$$ which can be checked by following each $a_i$ through the factors from right to left.
In the symmetric group on $\{1, 2, 3\}$, the cycle $(1\ 2\ 3)$ equals $(1\ 2)(2\ 3)$, and also $(1\ 3)(1\ 2)$ and $(2\ 3)(1\ 3)$. Since a transposition is its own inverse, one can also insert a pair $(a\ b)(a\ b)$ anywhere, so decompositions of any length $m + 2j$ exist once one of length $m$ does.
On $\{1, \dots, 6\}$, the permutation $(1\ 4\ 2)(3\ 6)$, written as a product of disjoint cycles, equals $(1\ 4)(4\ 2)(3\ 6)$.

Proof

The proof is by induction on the number of points that $\sigma$ moves. If $\sigma$ moves no point, it is the identity and the empty product works. Otherwise pick $x$ with $\sigma(x) \neq x$ and let $\tau = (x\ \sigma(x))$. The permutation $\tau\sigma$ fixes $x$. It also fixes every point $y$ fixed by $\sigma$: such a $y$ differs from $x$, and it differs from $\sigma(x)$ because $\sigma(y) = y$ and $\sigma$ is injective, so $\tau$ fixes $y$. Hence $\tau\sigma$ moves fewer points than $\sigma$, and by induction it is a product $\tau_1 \cdots \tau_m$ of transpositions. Since $\tau^2$ is the identity, $\sigma = \tau \tau_1 \cdots \tau_m$. Each step removes at least one moved point, and no permutation moves exactly one point, so a permutation moving $s \ge 2$ points needs at most $s - 1$ steps. Since $s \le n$, this gives the bound $m \le n - 1$ from the statement.

Alternatively, one can write $\sigma$ as a product of disjoint cycles and decompose each cycle as in the first example.

Consequences

Parity. By multiplicativity of the sign, a product of $m$ transpositions has sign $(-1)^m$. So all decompositions of a given permutation have lengths of the same parity, and the permutation is even or odd accordingly. In particular a cycle moving $k$ points has sign $-(-1)^k = (-1)^{k-1}$. The even permutations form the alternating group.
Generation. For a finite set $X$, the transpositions generate the group of permutations of $X$ (see subgroup generated by a subset). Smaller generating sets follow by expressing transpositions in terms of others: every permutation of $\{0, 1, \dots, k\}$ is a product of transpositions $(i\ \ i+1)$ of consecutive elements, and a cycle $\sigma$ moving every point of $X$ together with a transposition $(x\ \sigma(x))$ generate the whole group. When $X$ has a prime number of elements, a cycle moving every point together with any transposition generate it.
Induction over permutations. For a finite set, a property that holds for the identity and is preserved by composing on the left with a transposition holds for every permutation.
Uniqueness of the sign. Any two transpositions are conjugate, so a homomorphism to $\{\pm 1\}$ takes the same value on all of them and is determined by that value. Hence every surjective homomorphism from the permutations of a finite set onto $\{\pm 1\}$ is the sign.
Minimal length. If $X$ has $n$ elements, the fewest transpositions needed for $\sigma$ is $n - c$, where $c$ is the number of cycles of $\sigma$, fixed points counted as cycles of length $1$.

Infinite sets

On an infinite set $X$ a product of finitely many transpositions moves only finitely many points, so a permutation moving infinitely many points, such as the shift $k \mapsto k + 1$ of the integers, is not such a product. Because each transposition is its own inverse, the subgroup generated by the transpositions consists exactly of their finite products, and a permutation of an arbitrary set lies in this subgroup if and only if it moves only finitely many points.

The decomposition into disjoint cycles is a sharper statement: it is unique up to the order of the factors, once cycles of length $1$ are left out. An analogue in linear algebra is the decomposition of an orthogonal transformation as a product of reflections, in which reflections play the role of transpositions.

In Mathlib

Mathlib states the theorem for a finite type with decidable equality, as a list of permutations whose product is the given permutation and each of whose entries exchanges two distinct elements; the product of a list composes its entries so that the last entry acts first. The result is packaged as a truncation: it computably provides such a list, while treating all such lists as indistinguishable, since the list is not unique. The bare existence statement used in this article is a consequence. When the type is also linearly ordered, Mathlib defines a specific list of transpositions with the given product, obtained by running the procedure of the proof above through the elements in increasing order. The generation statements are phrased with the subgroup or submonoid generated by the given set of permutations, and in the statement for arbitrary types the set of moved points is written as the complement of the set of fixed points.

Written for Trough, under CC BY-SA 4.0.

Sources

MathlibEquiv.Perm.truncSwapFactors

Uses 2 · Used by 2

Statement usesPermutation group of a type · Group

Used byAlternating groups on 5 letters or more are simple · Signature

DefinitionDecomposition into cycles with disjoint support #

The decomposition into cycles with disjoint support says that every permutation of a finite set is a product of cycles that move pairwise disjoint sets of points, and that these cycles are determined by the permutation up to the order in which they are written. It is the basis of cycle notation, the standard way of writing elements of a permutation group, and it reduces questions about an arbitrary permutation (its order, its sign, its conjugacy class) to questions about single cycles.

Definitions

Let $X$ be a finite set and $\sigma$ a permutation of $X$. The support of $\sigma$ is the set of points that $\sigma$ moves, that is, the $x$ with $\sigma(x) \neq x$. Two points lie in the same cycle of $\sigma$ if some integer power of $\sigma$ carries one to the other. A permutation is a cycle if it moves at least one point and any two points it moves lie in the same cycle of it. For distinct points $a_1, \dots, a_\ell$ with $\ell \ge 2$, the cycle $(a_1\,a_2\,\dots\,a_\ell)$ sends $a_i$ to $a_{i+1}$ for $i < \ell$, sends $a_\ell$ to $a_1$, and fixes every other point; every cycle on $X$ has this form, and its length $\ell$ is the size of its support.

Two permutations are disjoint if every point is fixed by at least one of them; equivalently, their supports are disjoint. Disjoint permutations commute, since each acts only on points the other leaves alone.

Statement

Let $\sigma$ be a permutation of a finite set $X$. Then there are cycles $c_1, \dots, c_k$ on $X$, pairwise disjoint, whose product is $\sigma$. The identity is the case $k = 0$, the empty product. The decomposition is unique up to order: any two lists of pairwise disjoint cycles with the same product are rearrangements of each other. So $\sigma$ has a well-defined set of cycle factors, and a cycle $c$ is one of them exactly when $c$ agrees with $\sigma$ at every point that $c$ moves.

Examples

On $\{1, \dots, 7\}$, let $\sigma$ send $1 \mapsto 4$, $4 \mapsto 6$, $6 \mapsto 1$, $2 \mapsto 7$, $7 \mapsto 2$ and fix $3$ and $5$. Following each point until it returns gives $\sigma = (1\,4\,6)(2\,7)$, and $(2\,7)(1\,4\,6)$ is the same permutation.
A cycle is its own decomposition, with $k = 1$.
Disjointness is needed for uniqueness. Composing from right to left, $(1\,2)(2\,3) = (1\,2\,3)$, so a single $3$-cycle is also a product of two overlapping transpositions.

Consequences

The cycle type of $\sigma$ is the multiset of the lengths of its cycle factors; for the example above it is $\{3, 2\}$. Its entries add up to the number of points that $\sigma$ moves.

Order. A cycle's order equals its length, and powers of disjoint factors can be computed separately, so the order of $\sigma$ is the least common multiple of its cycle lengths (see order of an element). The example has order $\operatorname{lcm}(3, 2) = 6$.
Sign. A cycle of length $\ell$ has sign $-(-1)^{\ell}$, that is $(-1)^{\ell - 1}$. Multiplying over the factors, if $\sigma$ moves $m$ points and has $k$ cycle factors (so $m$ is the sum and $k$ the number of entries of its cycle type) then its sign is $(-1)^{m + k}$ (see signature). The example has sign $(-1)^{5 + 2} = -1$.
Conjugacy. For a cycle $c = (a_1\,\dots\,a_\ell)$ and any permutation $\tau$, the conjugate $\tau c \tau^{-1}$ is the cycle $(\tau(a_1)\,\dots\,\tau(a_\ell))$, and from this one gets that two permutations of a finite set are conjugate if and only if they have the same cycle type. Counting fixed points as cycles of length $1$, the conjugacy classes of the symmetric group on $n$ letters therefore correspond to the partitions of $n$; the symmetric group on $4$ letters has $5$ of them.
Transpositions. A cycle of length $\ell$ is a product of $\ell - 1$ transpositions, so the cycle decomposition yields a decomposition into transpositions.
Induction. A property that holds for the identity and for every cycle, and that holds for $\sigma\tau$ whenever $\sigma$ is a cycle disjoint from $\tau$ and it holds for $\sigma$ and for $\tau$, holds for every permutation of a finite set.

Proof

Existence is proved by induction on the number of points moved. If $\sigma$ is the identity, take the empty product. Otherwise choose a point $x$ that $\sigma$ moves, and let $c$ be the permutation that agrees with $\sigma$ on the cycle of $\sigma$ through $x$ and fixes every other point; $c$ is a cycle. The permutation $c^{-1}\sigma$ fixes every point of that cycle and agrees with $\sigma$ elsewhere, so it is disjoint from $c$ and moves fewer points than $\sigma$. By induction it is a product of pairwise disjoint cycles; since each factor of a disjoint decomposition moves only points that the product moves, none of them moves a point of the support of $c$, and adding $c$ to this list gives a decomposition of $\sigma$.

For uniqueness, take any decomposition of $\sigma$ into pairwise disjoint cycles. Each point moved by $\sigma$ is moved by exactly one factor, and that factor acts on its own support as $\sigma$ does. Conversely, if a cycle $c$ agrees with $\sigma$ at every point it moves, pick such a point $a$; the factor $c'$ that moves $a$ also agrees with $\sigma$, hence with $c$, at $a$ and therefore along the whole cycle through $a$, which is the support of both, so $c = c'$. Thus a cycle belongs to the list exactly when it agrees with the product at every point it moves. This condition does not mention the list, so two decompositions have the same factors, and since the factors of a decomposition are distinct, the two lists differ only in order.

In Mathlib

Mathlib states the decomposition for permutations of any type with finitely many elements and decidable equality, with products of permutations composed from right to left. Since the order of the factors is not canonical, Mathlib gives the list in two ways. One version asks for a linear order on the underlying type and uses it to produce a specific list. The version this article is about needs no order and returns the list in truncated form: it asserts that a suitable list exists, and allows a list to be used only to compute values that do not depend on which list was chosen. The uniqueness statement is what makes this usable: it shows that the set of cycle factors is the same for every list, and the cycle type is defined from that set. Disjointness is defined pointwise, so it makes sense for permutations of infinite types as well. Fixed points are not counted as cycles of length $1$, since a cycle must move at least two points; the cycle type therefore lists only lengths of $2$ or more, and the identity has empty cycle type. The statements above on the sum of the cycle type, the order and the sign are proved in Mathlib by the induction principle on disjoint cycles.

Written for Trough, under CC BY-SA 4.0.

Sources

MathlibEquiv.Perm.truncCycleFactors

Uses 3 · Used by 2

Statement usesPermutation group of a type · Finite set · Group

Used byAlternating groups on 5 letters or more are simple · Cauchy's theorem (group theory)

DefinitionSignature #

The signature (also called the sign) of a permutation $\sigma$ of a finite set is the number $\operatorname{sgn}(\sigma) \in \{1, -1\}$ that records whether $\sigma$ is a product of an even or an odd number of transpositions. Permutations of signature $1$ are called even and those of signature $-1$ odd. The signature is a group homomorphism from the symmetric group to the two-element group $\{1, -1\}$. It supplies the signs in the Leibniz formula for the determinant, and its kernel, the set of even permutations, is the alternating group.

Definition

Let $X$ be a finite set and $S_X$ the group of permutations of $X$. For $X = \{1, \dots, n\}$ one writes $S_n$, and later $A_n$ for its alternating group. A transposition is a permutation that exchanges two distinct points and fixes every other point. Every permutation is a product of transpositions (see decomposition into transpositions), though not in a unique way. The key fact is that the parity of the number of factors does not depend on the chosen product. The signature is the homomorphism $\operatorname{sgn} : S_X \to \{1, -1\}$ characterized by this parity: if $\sigma$ is a product of $k$ transpositions, then $\operatorname{sgn}(\sigma) = (-1)^k$.

An equivalent description counts inversions. For a permutation $\sigma$ of $\{1, \dots, n\}$, call a pair $i < j$ an inversion if $\sigma(i) > \sigma(j)$. Then the signature is the product, over all pairs $i < j$, of $1$ when $\sigma(i) < \sigma(j)$ and $-1$ otherwise. Each factor $(\sigma(j) - \sigma(i))/(j - i)$ has exactly that sign, and since $\sigma$ permutes the unordered pairs $\{i, j\}$, the absolute values of these factors multiply to $1$. Hence

\[\operatorname{sgn}(\sigma) = \prod_{i < j} \frac{\sigma(j) - \sigma(i)}{j - i} = (-1)^{\#\{\text{inversions of } \sigma\}}.\]

Examples

In $S_2$ the identity is even and the single transposition is odd.
In $S_3$ the identity and the two $3$-cycles are even, and the three transpositions are odd. In one-line notation the $3$-cycle $231$ has the two inversions $(1,3)$ and $(2,3)$, which confirms that it is even.
A transposition of two distinct points has signature $-1$.
A cycle that moves exactly $k$ points has signature $-(-1)^k = (-1)^{k-1}$, since it is a product of $k - 1$ transpositions: $(a_1\,a_2\,\cdots\,a_k) = (a_1\,a_k)\cdots(a_1\,a_3)(a_1\,a_2)$. In particular every $3$-cycle is even.
Writing a permutation as a product of disjoint cycles (see decomposition into cycles) gives its signature at once: $(1\,2\,3)(4\,5)$ in $S_5$ has signature $1 \cdot (-1) = -1$.

Properties

Multiplicativity. For all permutations $\sigma$ and $\tau$ of $X$, $\operatorname{sgn}(\sigma\tau) = \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)$. Consequently $\operatorname{sgn}(\sigma^{-1}) = \operatorname{sgn}(\sigma)$, and conjugate permutations have the same signature, because the target group is abelian.
Independence of labels. If $e : X \to Y$ is a bijection of finite sets, the permutation $e \sigma e^{-1}$ of $Y$ has the same signature as $\sigma$. So the signature depends only on how $\sigma$ moves points, not on what the points are called.
Disjoint unions. If $\sigma$ permutes $X$ and $\tau$ permutes $Y$, the permutation of the disjoint union $X \sqcup Y$ acting as $\sigma$ on $X$ and as $\tau$ on $Y$ has signature $\operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)$.
Surjectivity and uniqueness. When $X$ has at least two elements, the signature takes both values. Moreover, every surjective homomorphism from $S_X$ onto $\{1, -1\}$ is the signature: all transpositions are conjugate, so such a homomorphism sends them all to the same value, and since they generate $S_X$ that value must be $-1$.
The alternating group. The kernel of the signature is the alternating group $A_X$: a permutation lies in $A_X$ exactly when its signature is $1$. As a kernel, $A_X$ is a normal subgroup (see normal subgroup). When $X$ has at least two elements, it has index $2$ (see index), so for $n \ge 2$ the group $A_n$ has $n!/2$ elements.
Determinants. For a square matrix $M$ over a commutative ring, indexed by a finite set $X$, the Leibniz formula expresses the determinant as a signed sum over permutations:

$$\det M = \sum_{\sigma \in S_X} \operatorname{sgn}(\sigma) \prod_{i \in X} M_{\sigma(i),\, i}.$$

In particular the determinant of the permutation matrix of $\sigma$ is $\operatorname{sgn}(\sigma)$.

The alternating group, as the kernel of the signature, is the starting point for the fact that $A_n$ is simple for $n \ge 5$ (see simple group). The determinant is defined through the signature, as the signed sum above. Alternating maps are the multilinear maps that vanish whenever two arguments coincide; for such a map $f$ in finitely many arguments, with values in a module over a ring, $f(v_{\sigma(1)}, \dots, v_{\sigma(n)}) = \operatorname{sgn}(\sigma) f(v_1, \dots, v_n)$ for every permutation $\sigma$. The abelianization of $S_n$ for $n \ge 2$ is the two-element group, and the signature is the quotient map onto it.

In Mathlib

Mathlib defines the signature for permutations of any type that comes with an explicit finite set containing all of its elements (in no particular order) and decidable equality, so that the definition can be computed. The value lies in the group of units of the integers, which is the two-element multiplicative group $\{1, -1\}$, and the signature is packaged as a bundled group homomorphism, so multiplicativity and the behaviour on the identity and on inverses come with the definition. The construction runs through a list of all the elements, composing with a transposition to fix each point that is not yet fixed and flipping the sign each time it does so; independence from the order of the list, which lets the construction descend to the unordered finite set, is proved by comparison with the inversion count. That inversion formula is stated for permutations of $\{0, 1, \dots, n-1\}$, which differs from $\{1, \dots, n\}$ only by relabelling. On a set with fewer than two elements the signature is the trivial homomorphism, which is why surjectivity and the index and order of the alternating group are stated for sets with at least two elements.

Written for Trough, under CC BY-SA 4.0.

Sources

MathlibEquiv.Perm.sign

Uses 5 · Used by 3

Statement usesGroup · Permutation group of a type · Group morphism · Decomposition into transpositions · Finite set

Used byAlternating group · Alternating groups on 5 letters or more are simple · Determinant

Alternating group

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.

Permutation group

DefinitionDecomposition into transpositions#

Statement

Examples

Proof

Consequences

Infinite sets

Related concepts

In Mathlib

Sources

DefinitionDecomposition into cycles with disjoint support#

Definitions

Statement

Examples

Consequences

Proof

In Mathlib

Sources

DefinitionSignature#

Definition

Examples

Properties

Related concepts

In Mathlib

Sources

DefinitionDecomposition into transpositions #

DefinitionDecomposition into cycles with disjoint support #

DefinitionSignature #