The symmetric group is defined to be the group of all permutations of objects. More generally, the symmetric group of a set , denoted , , or , is the group of permutations on . A subgroup of the symmetric group on is sometimes called a permutation group on . In this context, a permutation is to be thought of as a bijective function from a set of size to itself, and the group operation is composition of functions.
The symmetric group is of interest in many different branches of mathematics, especially combinatorics. (This is in part due to the various different representations of permutations: as functions, as products of cycles, as sequences or words, etc.) Knowledge of the symmetric group can also be crucial in such areas as Galois theory. For example, an important theorem in Galois theory is that the Galois group of the general polynomial equation of degree is , and this can be used to prove that polynomial equations of degree five and higher are unsolvable through the use of elementary arithmetic and root extractions.
The study of symmetric groups is also interesting because every group is isomorphic to a permutation group, i.e., a subgroup of a symmetric group. Indeed, if is a group, then for , the mapping is a permutation of . Thus symmetric groups can be considered universal with respect to subgroups, just as free groups can be considered universal with respect to quotient groups.
Representations of Finite Permutations
Let be an element of . One way to denote is as So for instance, with , we might have In the more concise cycle notation, we represent a cycle of order as for some arbitrary in the support of ; and we write an arbitrary permutation as a composition of cycles. Thus we may have This notation is concise; it lends itself to easy computation of products and inverses.
Finally, we may represent a permutation as a permutation matrix, i.e., the matrix that maps to . An matrix is a permutation matrix if and only if all its entries are zeros and ones, each column has exactly one 1, and each row has exactly one 1. In this instance, we have
In the next two sections, will represent a finite set.
Transpositions and Generators
A transposition is a cycle whose support has two elements. A transposition whose support is may be denoted . Evidently, every transposition is its own inverse.
In this section and the next one, will represent a finite set.
Theorem 1. The symmetric group is generated by its transpositions.
Proof. We induct on . For our base case, , the theorem is trivial. Now, suppose that is an element of . Let be an arbitrary element of . Let be the subgroup of elements of for which is a fixed point. Evidently, is isomorphic to by restrictions of mappings, so by inductive hypothesis, it is generated by its transpositions. Then , for some permutation . Since can be expressed as a product of transpositions, it follows that can be expressed as a product of transpositions.
Note that in general this theorem is not true on infinite sets without permitting infinite compositions of functions.
Theorem 2. The symmetric group is generated by the transpositions .
Proof. By theorem 1, it is enough to prove that any transposition is generated by . Without loss of generality, suppose . We induct on . Our base case, , is trivial. For the inductive step, we note that Since is in the subgroup generated by , it follows that is, as well.
Theorem 3. Let be a cycle whose orbit is , let be an element of , and let be a transposition on . Then and generate .
Proof. Let be an arbitrary element of . Then we may denote every element of as , where is an integer. Suppose . By Theorem 2, it is enough to show that lies in the subgroup generated by and , for each integer . But this follows from the observation Thus and generate , as desired.
Even and Odd Permutations; Alternating Groups
For an element , an inversion is an ordered pair of integers such that and . We will let denote the number of inversions of . A permutation is called odd if it has an odd number of inversions, and even if it contains an even number of inversions. We wish to show that the mapping is a homomorphism; this would imply that even permutations form a normal subgroup of .
Let be the mapping
Lemma. The function is not the zero function, and .
Proof. If are distinct, then . Let denote 1 if is a -inversion, and 0, otherwise. Then by rearranging terms, as desired.
Theorem 4. There exists a unique homomorphism from to the multiplicative group such that , for any transposition .
Proof. To show the existance of , it suffices to show its existance for . We will show that is such a homomorphism. Indeed, if are elements of , then by the lemma, On the other hand, Since (from the lemma), it follows that i.e., is a homomorphism, as desired, and evidently for every transposition .
Since is generated by its transpositions (Theorem 1), it follows that is unique.