Symmetric group

The symmetric group ( or ) is the group of all permutations ( permutations ) of one - element set is. This is called the degree of the group. The group operation is the composition ( sequential execution ) of permutations; the neutral element is the identity map. The symmetric group is finite and has the order. It is not abelian for.

Notation, notation cycles

There are different ways to write a permutation. Forms, for example, the permutation element which element, etc. in this way can be

. Write ( It is not necessarily required that the numbers are ordered in the top line. ) In this notation we obtain the inverse permutation by interchanging the upper and the bottom line.

Another important notation is the notation cycles:

Are different, goes in, in, ..., in over, and all other elements remain invariant, we write this

And called a cycle of length. Two cycles of length describe exactly what it is the same image, if one is by cyclic permutation of its entries to another. For example, applies

Each permutation can be written as a product of disjoint cycles. (These two hot cycles and disjoint if for all and true. ) This representation as a product of disjoint cycles is even unique up to cyclic permutation of the entries within cycles and order of cycles ( this sequence can be arbitrary: commute disjoint cycles always each other ).

Properties

Generating sets

  • Every permutation can be represented as a product of transpositions (two cycles); depending on whether this number is straight or odd, it is called even or odd permutations. Regardless of how one chooses the product, this number is either always even or always odd and is described by the sign of the permutation. The quantity of the even-numbered permutations forms a subset of the alternating group.
  • The two elements and generate the symmetric group. More generally, an arbitrary cycle can be selected in that cycle together with any transposition of two consecutive elements.
  • If can be at any element (not the identity) a second select such that both elements generate the.

Conjugacy

Two elements of the symmetric group are conjugate to each other if and only if it as a product of disjoint cycles have the same Zykeltyp in the representation, that is, when the number of single, double, triple, etc. cycles coincide. In this illustration, the conjugation means a renumbering of the numbers that are in the Zykeln.

Each conjugacy class therefore corresponds to the reversible clearly a number of partition and the number of conjugacy classes is equal to the value of the partition function at the point

For example, are the elements in the conjugacy class associated with the partition number of 7 and has different conjugacy classes.

Normal subgroup

The symmetric group has non-trivial normal subgroups, and only the alternating group as a normal subgroup, additionally for the Klein four-group.

Cayley

By the theorem of Cayley every finite group is isomorphic to a subgroup of the symmetric group, which is not greater than the order of.

Worked examples

Concatenating two permutations, and is written as: The first permutation is performed, the permutation is applied to the result ( the operations are to be read from right to left).

Example:

In cycle notation is this:

First, the "right" permutation is the 4 from the 1, then forms the "left" the permutation 1 to 2 from; Thus, the entire chain is from 4 to 2.

For the symmetric group is not abelian, as can be seen from the following calculation:

Cayleygraph Permutation matrix Parity of a permutation Cayley's theorem Dihedral group of order 6
758316
de