# Difference between revisions of "Symmetric group"

(added material on notation, generating systems, and parity of permutations) |
(every group is a permutation group) |
||

Line 1: | Line 1: | ||

The '''symmetric group''' <math>S_{n}</math> is defined to be the [[group]] of all [[permutation]]s of <math>n</math> objects. More generally, the symmetric group of a [[set]] <math>M</math>, denoted <math>S_M</math>, <math>\mathfrak{S}_M</math>, or <math>\text{Sym}(M)</math>, is the group of permutations on <math>M</math>. A [[subgroup]] of the symmetric group on <math>M</math> is sometimes called a '''permutation group''' on <math>M</math>. In this context, a permutation is to be thought of as a [[bijective]] [[function]] from a [[set]] of size <math>n</math> to itself, and the group operation is [[composition]] of functions. | The '''symmetric group''' <math>S_{n}</math> is defined to be the [[group]] of all [[permutation]]s of <math>n</math> objects. More generally, the symmetric group of a [[set]] <math>M</math>, denoted <math>S_M</math>, <math>\mathfrak{S}_M</math>, or <math>\text{Sym}(M)</math>, is the group of permutations on <math>M</math>. A [[subgroup]] of the symmetric group on <math>M</math> is sometimes called a '''permutation group''' on <math>M</math>. In this context, a permutation is to be thought of as a [[bijective]] [[function]] from a [[set]] of size <math>n</math> 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 [[cycle]]s, as [[sequence]]s or [[word]]s, etc.) Knowledge of the symmetric group <math>S_{n}</math> 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 <math>n</math> is <math>S_{n}</math>, and this can be used to prove that [[polynomial]] [[equation]]s of degree five and higher are unsolvable through the use of elementary arithmetic and root extractions. | + | 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 [[cycle]]s, as [[sequence]]s or [[word]]s, etc.) Knowledge of the symmetric group <math>S_{n}</math> 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 <math>n</math> is <math>S_{n}</math>, and this can be used to prove that [[polynomial]] [[equation]]s 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 <math>G</math> is a group, then for <math>a \in G</math>, the mapping <math>x \mapsto ax</math> is a permutation of <math>G</math>. Thus symmetric groups can be considered universal with respect to subgroups, just as [[free group]]s can be considered universal with respect to [[quotient group]]s. | ||

== Representations of Finite Permutations == | == Representations of Finite Permutations == |

## Latest revision as of 15:33, 25 May 2008

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.

## Contents

## 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 a mapping from to , and suppose . Let be the mapping so that Then evidently .

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.

This is what we wanted to prove. The kernel of is the set of even permutations on , called the alternating group of . It is usually denoted as , , or .