LESSWRONG
LW

Wikitags

Symmetric group

Edited by Patrick Stevens last updated 17th Jun 2016
Requires:

The notion that group theory captures the idea of "symmetry" derives from the notion of the symmetric group, and the very important theorem due to Cayley that every group is a subgroup of a symmetric group.

Definition

Let X be a . A f:X→X is a permutation of X. Write Sym(X) for the set of permutations of the set X (so its elements are functions).

Then Sym(X) is a group under the operation of composition of functions; it is the symmetric group on X. (It is also written Aut(X), for the automorphism group.)

We write Sn for Sym({1,2,…,n}), the symmetric group on n elements.

Elements of Sn

We can represent a permutation of {1,2,…,n} in two different ways, each of which is useful in different situations.

Double-row notation

Let σ∈Sn, so σ is a function {1,2,…,n}→{1,2,…,n}. Then we write (12…nσ(1)σ(2)…σ(n)) for σ. This has the advantage that it is immediately clear where every element goes, but the disadvantage that it is quite hard to see the properties of an element when it is written in double-row notation (for example, "σ cycles round five elements" is hard to spot at a glance), and it is not very compact.

Cycle notation

is a different notation, which has the advantage that it is easy to determine an element's order and to get a general sense of what the element does. Every element of Sn .

Product of transpositions

It is a useful fact that every permutation in a (finite) symmetric group as a product of .

Examples

  • The group S1 is the group of permutations of a one-point set. It contains the identity only, so S1 is the trivial group.
  • The group S2 is isomorphic to the of order 2. It contains the identity map and the map which interchanges 1 and 2.

Those are the only two symmetric groups. Indeed, in cycle notation, (123) and (12) do not commute in Sn for n≥3, because (123)(12)=(13) while (12)(123)=(23).

  • The group S3 contains the following six elements: the identity, (12),(23),(13),(123),(132). It is isomorphic to the D6 on three vertices. ()

Why we care about the symmetric groups

A very important (and rather basic) result is , which states the link between group theory and symmetry.

Relationship to the

The An is defined as the collection of elements of Sn which can be made by an even number of . This does form a group ().

Parents:
Children:
and 7 more
Function
may be expressed
bijection
can be expressed in (disjoint) cycle notation in an essentially unique way
set
dihedral group
3
3
transpositions
transpositions
Cycle notation
Cycle notation in symmetric groups
Discussion4
Discussion4
abelian
cyclic group
proof
Proof.
Cayley's Theorem
Cayley's Theorem on symmetric groups
alternating group
alternating group
Group