A permutation of a set ( for Menge, the German word for set) is a bijectivefunction.
As an example, consider the set ; now one such permutation might be defined to do the following: . The star is fixed, but the triangle and the circle are permutated.
For a more concrete example, the shape or the nature of the objects in the set is not relevant, all that needs to be known is the number of objects in , called the cardinality of . Let be a set with elements, then the above permutation can then be described by . The third element is left fixed, while the first two are permutated.
Generally, as such permutations are bijective, they are invertible, with their inverse being a, probably different, permutation of as well. The composition of permutations is again a, probably different, permutation of . There also clearly exists a permutation that does nothing, the identity, namely , for each element . Therefore, the set of all the permutations of a set is a group, the so called symmetry group of .
For a finite set , the symmetric group of , or the symmetric group of order , is defined as the permutation group of : . Note that the order of is .
One can consider those permutations to be the symmetries of an object. Imagine a square rotated by , the actual vertices have moved, but the square still looks the same. Can you figure out all the eight symmetries of the square?
If you ever wanted to see the mathematical beauty of symmetry, think about visiting the Qalat Al-Hamra, or the Alhambra, in Grenada, Spain.
Cayley’s Theorem
Arthur Cayley was a British mathematician, and probably the first man to clearly define the concept of a group. One of his famous theorems states that every group is isomorphic to a group of permutations.
Two objects are said to be isomorphic, if there exists an isomorphism, which is a bijective homomorphism (from the ancient Greek words ὁμός (homós), which means equal or similar, and μορφή (morphé), which means form), between the two objects. Homomorphisms are structure preservering maps that identify objects which, although looking differently, are essentially the same.
To prove the theorem, let denote the symmetry group of a group . The basic idea is that each element corresponds to a permutation of :
, with . Since is a group, it is clear that is bijective, thus indeed a permutation of .
Furthermore, being a group ensures that is an injective homomorphism, which means that is indeed isomorphic to a subgroup of . Subgroups of are often called permutation groups and are denoted by .
Group Operations
With Cayley’s theorem, it is now clear how to define a group operation on a set: An operation of a group on a set is a homomorphism of into the symmetry group of defined as above. An operation thus provides a mapping , . We also say that acts on .
Obviously, the following two properties hold:
, where is the unit element of .
.
Conversely, a map satisfying these two properties defines a permutation for each . We thus obtain a homomorphism from into . So an operation of on could also be defined as a mapping with the two properties from above.
The Orbit
Let be arbitrary chosen but fixed. The subset of consisting of the images of under operation by elements of is denoted by and called the orbit of under .
Clearly, all the orbits define a partition of . If an element belongs to the orbit of both and , then there exist such, that . Since is a group, this implies that and , thus belongs to the orbit of and vice versa. In conclusion: , thus, by choosing representatives for each orbit, we can write , where denotes the set of the chosen representatives.
A group operation is called transitive, or G is said to act transitively on , if there is only one orbit: , for any , that is, for all there exists such, that .
The Stabilizer
Let be arbitrarily chosen but fixed. The set of elements which leave fixed, that is , is a subgroup of , the so-called isotropy group of in , or the stabilizer of under the action of , denoted by . An element is called a fixed point of , if , in other words, if it is fixed by each operation.
Obviously, the kernel of a group operation is the intersection of all the isotropy groups: . This is the set of all the elements of which leave all the elements of fixed.
A group operation is said to be faithful, if its kernel is trivial, i.e. if .
The Orbit-Stabilizer Theorem
The size of the orbit of an element is the index, the relative size, of the stabilizer of in :
.
For a finite set , this corresponds to:
.
Note that in particular, the size of any orbit divides the order, or the cardinality, of the group.
For a proof, we must define a bijective map between and , the set of left cosets of in . We can do so as follows: .
The first thing to check is whether is well-defined, as for a given , as above, the choice of in is not unique, as there is no bijection between and in general. Suppose that , then clearly , thus the image of under does not depend on the choice of , since the images are still in the same coset.
By the definition of it is clear that is surjective. To see that it is also injective, assume that , for and . Then, as , i.e. , it follows that , and in conclusion , as desired.
The Orbit-Counting Theorem
In the case of a finite group operating on a finite set, a theorem, probably due to Ferdinand Georg Frobenius, allows us to count the number of orbits :
, where denotes the subset of all the elements of fixed by .
In other words, the number of orbits under a group operation is the average number of points, or elements of , that are left fixed by the elements of .
To prove this, we use the Orbit-Stabilizer Theorem:
Further, using the fact that can be written as a disjoint union of the orbits under the group operation, we get the desired result:
