Symmetric group
![](http://s9.addthis.com/button1-share.gif)
In mathematics, the symmetric group is the group of all permutations of a set, that is, of all invertible maps from a set to itself. It is a central object of study in group theory.
Definition
If is a positive integer, the symmetric group on "letters" (often denoted ) is the group formed by all bijections from a set to itself (under the operation of function composition), where is an -element set. It is customary to take to be the set of integers from to , but this is not strictly necessary. The bijections which are elements of the symmetric group are called permutations.
Note that this means the identity element of the group is the identity map on , which is the map sending each element of to itself.
The order of is given by the factorial function .
Cycle Decomposition
Any permutation of a finite set can be written as a product of permutations called cycles. A cycle acting on fixes all the elements of S outside a nonempty subset of . On , the action of is as follows: for some indexing of the elements of , sends to for all and sends to . Then one writes
(Sometimes the commas are omitted.) If k > 1, such a is called a k-cycle.
For example, the permutation of the integers from 1 to 4 sending to for all can be denoted .
If is a one-element set, then its element is a fixed point of the permutation. Fixed points are often omitted from permutations written in cycle notation, since any cycling the elements of as discussed above would be the identity permutation.
Permutational Parity
A 2-cycle is called a transposition. Every permutation in , for n > 1, can be written as a product of transpositions. A permutation of n points is then called even if it can be written as the product of an even number of transpositions and odd if it can be written as the product of an odd number of transpositions. The nontrivial fact about this terminology is that it is well-defined; that is, no permutation is both even and odd.
The even permutations in form a subgroup of . This subgroup is called the alternating group on n letters and denoted . In fact, is always a normal subgroup of .
The order of is .
Notes on the Structure of the Symmetric Group
has proper normal subgroups if and only if n >= 3. Then the only proper normal subgroup of is , unless n=4. When n=4, there is an additional proper normal subgroup, often denoted V, consisting of the identity permutation and the permutations (1,2)(3,4), (1,3)(2,4), and (1,4)(2,3).
The conjugacy classes of are in one-to-one correspondence with the partitions of the integer n. Two permutations in are conjugate in if and only the have the same lengths of cycles. These cycle lengths, including fixed points as cycles of length 1, add up to n and so form a partition of n.