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 functions 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).

Related Topics:
Mathematics - Set - Group - Bijective - Function - Composition of functions

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

Related Topics:
Permutation - ''n''! - Abelian

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Subgroups of Sn are called permutation groups.

Related Topics:
Subgroup - Permutation group

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The rule of composition in the symmetric group is demonstrated below:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Let

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: f = (1 3)(2)(4 5)=egin{bmatrix} 1 & 2 & 3 & 4 & 5 \ 3 & 2 & 1 & 5 & 4end{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

and

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: g = (1 2 5)(3 4)=egin{bmatrix} 1 & 2 & 3 & 4 & 5 \ 2 & 5 & 4 & 3 & 1end{bmatrix}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: fg = (1 2 4)(3 5)=egin{bmatrix} 1 & 2 &3 & 4 & 5 \ 2 & 4 & 5 & 1 & 3end{bmatrix} .

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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 sign of a permutation:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:operatorname{sgn}(f)=left{egin{matrix} +1, & mbox{if }fmbox { is even} \ -1, & mbox{if }f mbox{ is odd}. end{matrix} ight.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

Related Topics:
Group homomorphism - Neutral element - Kernel - Alternating group - Normal subgroup - Semidirect product

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

Related Topics:
Cycle - Up to

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

For a list of elements of S4, see Cycle notation. See cube for the proper rotations of a cube, which form a group isomorphic with S4.

Related Topics:
Cycle notation - Cube

~ ~ ~ ~ ~ ~ ~ ~ ~ ~