Symmetric group

of the symmetric group S 4 using the generators (red) a right circular shift of all four set elements, and (blue) a left circular shift of the first three set elements.

Uses your system voice; voice and rate in settings.

≈ 12 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

of the symmetric group S 4 using the generators (red) a right circular shift of all four set elements, and (blue) a left circular shift of the first three set elements. In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions.

In particular, the finite symmetric group \mathrm{S}_n defined over a finite set of n symbols consists of the permutations that can be performed on the n symbols. Since there are n! ( n factorial) such permutation operations, the order (number of elements) of the symmetric group \mathrm{S}_n is n! . Although symmetric groups can be defined on infinite sets, this article focuses on the finite symmetric groups: their applications, their elements, their conjugacy classes, a finite presentation, their subgroups, their automorphism groups, and their representation theory.

For the remainder of this article, "symmetric group" will mean a symmetric group on a finite set. The symmetric group is important to diverse areas of mathematics such as Galois theory, invariant theory, the representation theory of Lie groups, and combinatorics.

Cayley's theorem states that every group G is isomorphic to a subgroup of the symmetric group on (the underlying set of) G . The symmetric group on a finite set X is the group whose elements are all bijective functions from X to X and whose group operation is that of function composition. For finite sets, "permutations" and "bijective functions" refer to the same operation, namely rearrangement.

The symmetric group of degree n is the symmetric group on the set X = \{1, 2, \ldots, n\} . The symmetric group on a set X is denoted in various ways, including \mathrm{S}_X , \mathfrak{S}_X , \Sigma_X , X! , and \operatorname{Sym}(X) . If X is the set \{1, 2, \ldots, n\} then the name may be abbreviated to \mathrm{S}_n , \mathfrak{S}_n , \Sigma_n , or \operatorname{Sym}(n) . Symmetric groups on infinite sets behave quite differently from symmetric groups on finite sets, and are discussed in , , and .

The symmetric group on a set of n elements has order n! (the factorial of n ). It is abelian if and only if n is less than or equal to 2. For n=0 and n=1 (the empty set and the singleton set), the symmetric groups are trivial (they have order 0! = 1! = 1 ). The group S n is solvable if and only if n \leq 4 .

This is an essential part of the proof of the Abel–Ruffini theorem that shows that for every n > 4 there are polynomials of degree n which are not solvable by radicals, that is, the solutions cannot be expressed by performing a finite number of operations of addition, subtraction, multiplication, division and root extraction on the polynomial's coefficients. f = (1~3)(2)(4~5)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 1 & 5 & 4\end{pmatrix}, g = (1~2~5)(3~4)=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end{pmatrix}. Applying after maps 1 first to 2 and then 2 to itself; 2 to 5 and then to 4; 3 to 4 and then to 5, and so on.

So, composing and gives fg = f\circ g = (1\ 2\ 4)(3\ 5)=\begin{pmatrix} 1 & 2 &3 & 4 & 5 \\ 2 & 4 & 5 & 1 & 3\end{pmatrix}. A cycle of length , taken to the th power, will decompose into cycles of length : For example, ( , ), (1~2~3~4~5~6)^2 = (1~3~5) (2~4~6). A transposition is a permutation which exchanges two elements and keeps all others fixed; for example (1 3) is a transposition.

Every permutation can be written as a product of transpositions; for instance, the permutation g from above can be written as g = (1 2)(2 5)(3 4). Since g can be written as a product of an odd number of transpositions, it is then called an odd permutation, whereas f is an even permutation.

The representation of a permutation as a product of transpositions is not unique; however, the number of transpositions needed to represent a given permutation is either always even or always odd. There are several short proofs of the invariance of this parity of a permutation.

The product of two even permutations is even, the product of two odd permutations is even, and the product of one of each is odd. Thus we can define the sign of a permutation: \operatorname{sgn}f = \begin{cases} +1, & \text{if }f\mbox { is even} \\ -1, & \text{if }f \text{ is odd}. \end{cases} With this definition, \operatorname{sgn}\colon \mathrm{S}_n \rightarrow \{+1, -1\}\ is a group homomorphism ({+1, −1} is a group under multiplication, where +1 is e, the neutral element).

The kernel of this homomorphism, that is, the set of all even permutations, is called the alternating group A n . It is a normal subgroup of S n , and for it has elements. The group S n is the semidirect product of A n and any subgroup generated by a single transposition.

Furthermore, every permutation can be written as a product of adjacent transpositions, that is, transpositions of the form . For instance, the permutation g from above can also be written as . The sorting algorithm bubble sort is an application of this fact.

The representation of a permutation as a product of adjacent transpositions is also not unique. A cycle of length k is a permutation f for which there exists an element x in {1, ..., n} such that x, f(x), f 2 (x), ..., f k (x) = x are the only elements moved by f; it conventionally is required that since with the element x itself would not be moved either.

The permutation h defined by h = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 1 & 3 & 5\end{pmatrix} is a cycle of length three, since , and , leaving 2 and 5 untouched. We denote such a cycle by , but it could equally well be written or by starting at a different point. The order of a cycle is equal to its length.

Cycles of length two are transpositions. Two cycles are disjoint if they have disjoint subsets of elements. Disjoint cycles commute: for example, in S 6 there is the equality .

Every element of S n can be written as a product of disjoint cycles; this representation is unique up to the order of the factors, and the freedom present in representing each individual cycle by choosing its starting point. Cycles admit the following conjugation property with any permutation \sigma , this property is often used to obtain its generators and relations. \sigma\begin{pmatrix} a & b & c & \ldots \end{pmatrix}\sigma^{-1}=\begin{pmatrix}\sigma(a) & \sigma(b) & \sigma(c) & \ldots\end{pmatrix} (1\,n)(2\,n-1)\cdots,\text{ or }\sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}\text{ adjacent transpositions: } (n\,n-1)(n-1\,n-2)\cdots(2\,1)(n-1\,n-2)(n-2\,n-3)\cdots, so it thus has sign: \mathrm{sgn}(\rho_n) = (-1)^{\lfloor n/2 \rfloor} =(-1)^{n(n-1)/2} = \begin{cases} +1 & n \equiv 0,1 \pmod{4}\\ -1 & n \equiv 2,3 \pmod{4} \end{cases} which is 4-periodic in n. In S 2n , the perfect shuffle is the permutation that splits the set into 2 piles and interleaves them.

Its sign is also (-1)^{\lfloor n/2 \rfloor}. Note that the reverse on n elements and perfect shuffle on 2n elements have the same sign; these are important to the classification of Clifford algebras, which are 8-periodic. k = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 & 2 & 5\end{pmatrix}, which can be written as the product of cycles as (2 4).

This permutation then relates (1 2 3)(4 5) and (1 4 3)(2 5) via conjugation, that is, (2~4)\circ(1~2~3)(4~5)\circ(2~4)=(1~4~3)(2~5). It is clear that such a permutation is not unique. Conjugacy classes of S n correspond to integer partitions of n: to the partition with n=\sum_{i=1}^k \mu_i and , is associated the set C μ of permutations with cycles of lengths .

Then C μ is a conjugacy class of S n , whose elements are said to be of cycle-type \mu . The symmetric group on letters is generated by the adjacent transpositions \sigma_i = (i, i + 1) that swap and .

The collection \sigma_1, \ldots, \sigma_{n-1} generates subject to the following relations: \sigma_i^2 = 1, \sigma_i\sigma_j = \sigma_j\sigma_i for |i-j| > 1 , and (\sigma_i\sigma_{i+1})^3 =1, where 1 represents the identity permutation. This representation endows the symmetric group with the structure of a Coxeter group (and so also a reflection group).

Other possible generating sets include the set of transpositions that swap and for , or more generally any set of transpositions that forms a connected graph, and a set containing any -cycle and a -cycle of adjacent elements in the -cycle.

Transitive subgroups

A transitive subgroup of S n is a subgroup whose action on {1, 2, ,..., n} is transitive. For example, the Galois group of a (finite) Galois extension is a transitive subgroup of S n , for some n.

Young subgroups

A subgroup of that is generated by transpositions is called a Young subgroup. They are all of the form S_{a_1} \times \cdots \times S_{a_\ell} where (a_1, \ldots, a_\ell) is an integer partition of . These groups may also be characterized as the parabolic subgroups of when it is viewed as a reflection group.

Cayley's theorem

Cayley's theorem states that every group G is isomorphic to a subgroup of some symmetric group. In particular, one may take a subgroup of the symmetric group on the elements of G, since every group acts on itself faithfully by (left or right) multiplication.

H_1(\mathrm{S}_n,\mathbf{Z}) = \begin{cases} 0 & n The first homology group is the abelianization, and corresponds to the sign map S n → S 2 which is the abelianization for n ≥ 2; for n n is generated by involutions (2-cycles, which have order 2), so the only non-trivial maps are to S 2 and all involutions are conjugate, hence map to the same element in the abelianization (since conjugation is trivial in abelian groups). Thus the only possible maps send an involution to 1 (the trivial map) or to −1 (the sign map).

One must also show that the sign map is well-defined, but assuming that, this gives the first homology of S n . The second homology (concretely, the Schur multiplier) is: H_2(\mathrm{S}_n,\mathbf{Z}) = \begin{cases} 0 & n This was computed in , and corresponds to the double cover of the symmetric group, 2 · S n . Note that the exceptional low-dimensional homology of the alternating group ( H_1(\mathrm{A}_3)\cong H_1(\mathrm{A}_4) \cong \mathrm{C}_3, corresponding to non-trivial abelianization, and H_2(\mathrm{A}_6)\cong H_2(\mathrm{A}_7) \cong \mathrm{C}_6, due to the exceptional 3-fold cover) does not change the homology of the symmetric group;

the alternating group phenomena do yield symmetric group phenomena – the map \mathrm{A}_4 \twoheadrightarrow \mathrm{C}_3 extends to \mathrm{S}_4 \twoheadrightarrow \mathrm{S}_3, and the triple covers of A 6 and A 7 extend to triple covers of S 6 and S 7 – but these are not homological – the map \mathrm{S}_4 \twoheadrightarrow \mathrm{S}_3 does not change the abelianization of S 4 , and the triple covers do not correspond to homology either. The homology "stabilizes" in the sense of stable homotopy theory: there is an inclusion map , and for fixed k, the induced map on homology is an isomorphism for sufficiently high n. This is analogous to the homology of families Lie groups stabilizing.

The homology of the infinite symmetric group is computed in , with the cohomology algebra forming a Hopf algebra.

Marcus du Sautoy: Symmetry, reality's riddle (video of a talk) OEIS Entries dealing with the Symmetric Group

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373607912 under CC BY-SA 4.0; modifications have been made.

Words in each sectionCayley's theoremCayley's theoremCayley's theorem: 402 words402Young subgroupsYoung subgroupsYoung subgroups: 58 words58Transitive subgroupsTransitive subgroupsTransitive subgroups: 37 words37
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001373607912 · captured 2026-09-06 · ledger · version history

Cite this page as: encyclopegia.org, “Symmetric group”, snapshot enwiki-001373607912. https://encyclopegia.org/a/symmetric-group

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.