Symmetric group
In mathematics, the symmetric group on a set X, denoted by SX or Sym(X), is the group whose underlying set is the set of all bijective functionss from X to X, in which the group operation is that of composition of functions, i.e., two such functions f and g can be composed to yield a new bijective function f o g, defined by (f o g)(x) = f(g(x)) for all x in X. Using this operation, SX forms a group. The operation is also written as fg (and sometimes, but not in Wikipedia, as gf). Of particular importance is the case of a finite set X = {1,...,n}, which we write as Sn. The remainder of this article will discuss Sn. The elements of Sn are called permutations; there are n of them. The group Sn is abelian if and only if n ≤ 2. Subgroups of Sn are called permutation groups. The rule of composition in the symmetric group is demonstrated below:
Let
:
and
:
Applying f after g maps 1 to 2, and then to itself; 2 to 5 to 4; 3 to 4 to 5, and so on. So composing f and g gives
: . A transposition is a permutation which exchanges two elements and keeps all others fixed; for example (1 3) is a transposition. Every permutation can be written as a product of transpositions; for instance, the permutation g from above can be written as g = (1 2)(2 5)(3 4).
Since g can be written as a product of an odd number of transpositions, it is then called an odd permutation, whereas f is an even permutation. The representation of a permutation as a product of transpositions is not unique; however, the number of transpositions needed to represent a given permutation is either always even or always odd. To see this, consider the function which maps a permutation to an integer corresponding to the number of pairs (i,j), i The product of two even permutations is even, the product of two odd permutations is even, and all other products are odd. Thus we can define the signature of a permutation:
With this definition,
:sgn: Sn → {+1,-1}
is a group homomorphism ({+1,-1} is a group under multiplication, where +1 is e, the neutral element). The kernel of this homomorphism, i.e. the set of all even permutations, is called the alternating group An. It is a normal subgroup of Sn and has n! / 2 elements. The group Sn is the semidirect product of An and any subgroup generated by a single transposition. A cycle is a permutation f for which there exists an element x in {1,...,n} such that x, f(x), f2(x), ..., fk(x) = x are the only elements moved by f. The permutation f shown above is a cycle, since f(1) = 4, f(4) = 3 and f(3) = 1. We denote such a cycle by (1 4 3). The length of this cycle is three. The order of a cycle is equal to its length. Cycles of length two are transpositions. Two cycles are disjoint if they move different elements. Disjoint cycles commute, e.g. in S6 we have (3 1 4)(2 5 6) = (2 5 6)(3 1 4). Every element of Sn can be written as a product of disjoint cycles; this representation is unique up to the order of the factors. The conjugacy classes of Sn correspond to the cycle structures of permutations; that is, two elements of Sn are conjugate if and only if they consist of the same number of disjoint cycles of the same lengths.
For instance, in S5, (1 2 3)(4 5) and (1 4 3)(2 5) are conjugate; (1 2 3)(4 5) and (1 2)(4 5) are not. Braid groups are generalizations of symmetric groups.
See also Representation theory of the symmetric group Young tableau Young symmetrizer
|
|
