Symmetric group

In mathematics, the symmetric group on a set X, denoted by S_X 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, S_X 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 S_n. The remainder of this article will discuss S_n. The elements of S_n are called permutations; there are n of them. The group S_n is abelian if and only if n ≤ 2.

Subgroups of S_n 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: S_n → {+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 A_n. It is a normal subgroup of S_n and has n! / 2 elements. The group S_n is the semidirect product of A_n 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), f²(x), ..., f^k(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 S₆ we have (3 1 4)(2 5 6) = (2 5 6)(3 1 4). Every element of S_n can be written as a product of disjoint cycles; this representation is unique up to the order of the factors.

The conjugacy classes of S_n correspond to the cycle structures of permutations; that is, two elements of S_n are conjugate if and only if they consist of the same number of disjoint cycles of the same lengths. For instance, in S₅, (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

Help build the largest human-edited directory on the web.

Submit a Site - Open Directory Project - Become an Editor