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 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, 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

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

and

g = (1\ 2\ 5)(3\ 4)=\begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end{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)=\begin{bmatrix} 1 & 2 &3 & 4 & 5 \\ 2 & 4 & 5 & 1 & 3\end{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), isignature of a permutation:

\operatorname{sgn}(f)=\left\{\begin{matrix} +1, & \mbox{if }f\mbox { is even} \\ -1, & \mbox{if }f \mbox{ is odd}. \end{matrix}\right.

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.

Symmetric Group

See also