Symmetric group

Encyclopedia : S : SY : SYM : 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, although not here, as gf).

Of particular importance is the symmetric group on the finite set X = , denoted as S_n . The permutations of X form the set of bijective functions. The group S_n has order n! and is not abelian for n > 2. Similarly, the group S_n is solvable if and only if n ≤ 4. The remainder of this article will discuss S_n.

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 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 1 & 5 & 4\end ]

and

[ g = (1\ 2\ 5)(3\ 4)=\begin 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end ]

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 1 & 2 &3 & 4 & 5 \\ 2 & 4 & 5 & 1 & 3\end ].

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(f)=\left\ +1, & \mboxf\mbox \\ -1, & \mboxf \mbox. \end\right.]

With this definition,

sgn: S_n →

is a group homomorphism ( 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 such that x, f(x), f²(x), ..., f^k(x) = x are the only elements moved by f. The permutation h defined by

[h = \begin 1 & 2 & 3 & 4 & 5 \\ 4 & 2 & 1 & 3 & 5\end]

is a cycle, since h(1) = 4, h(4) = 3 and h(3) = 1, leaving 2 and 5 untouched. 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.

Symmetric groups are Coxeter groups and reflection groups. They can be realized as a group of reflections with respect to hyperplanes [x_i=x_j, 1\leq i < j \leq n]. Braid groups B_n contain symmetric groups S_n as quotient groups.

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

Symmetric group

See also