Tour:Symmetric group

From Groupprops
Jump to: navigation, search

This article adapts material from the main article: symmetric group

This page is part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Introduction five (beginners)| UP: Introduction five (beginners)| NEXT: Understanding the cycle decomposition
Expected time for this page: 20 minutes
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part
WHAT YOU NEED TO DO: This is a rather heavy article, introducing the concept of symmetric group.
  • Read and understand the definition of symmetric group.
  • Convince yourself that this is a group, i.e., that it satisfies the group axioms.
  • Try to convince yourself that a bijection of sets induces an isomorphism of their symmetric groups.
  • Understand the two-line and one-line notations.

Definition

Symbol-free definition

The symmetric group on a set is defined as follows:

  • The elements of the group are permutations on the given set (i.e., bijective maps from the set to itself).
  • The product of two elements is their composite as permutations, i.e., function composition.
  • The identity element of the group is the identity function from the set to itself.
  • The inverse of an element in the group is its inverse as a function.

A group is said to be a symmetric group if it is isomorphic to the symmetric group on some set. The symmetric group of degree n is defined as the symmetric group on a set of size n.

Definition with symbols

The symmetric group over a set S (denoted as \operatorname{Sym}(S)) is defined as follows:

  • The elements of the group are permutations on S, (i.e., bijective maps from S to itself).
  • The product of two permutations \sigma, \tau: S \to S is the permutation \sigma \circ \tau:S \to S, i.e., the permutation given by x \mapsto \sigma(\tau(x)).
  • The identity element of the group is the identity map of S.
  • The inverse of a permutation \sigma is the permutation that sends each element x \in S to the unique y such that \sigma(y) = x.

A group G is termed a symmetric group if G \cong \operatorname{Sym}(S) for some set S.

A bijection between sets gives rise to an isomorphism of the corresponding symmetric groups. Thus, there is only one symmetric group, upto isomorphism, on a set of given cardinality. The symmetric group on a set of cardinality n is denoted \operatorname{Sym}(n), or sometimes S_n, and is also sometimes termed the symmetric group of degree n.

Elements

The elements of the symmetric group on a set are the permutations of that set. The permutations can be described in a number of ways. Two most common ways of describing permutations are the one-line notation and the cycle decomposition.

Two-line notation and one-line notation

Further information: two-line notation for permutations, one-line notation for permutations

The two-line notation for a permutation on a finite set of size n is described as follows. It is a matrix with two rows and n columns. The first row contains the elements of the set (in any arbitrary order). The element in the second row equals the image of the element above it, under the permutation.

For instance, consider the two-line notation for a permutation on the set \{ 1,2,3,4,5\}:

\begin{pmatrix}
1 & 3 & 2 & 5 & 4\\
2 & 5 & 1 & 4 & 3
\end{pmatrix}

Here, the image of 1 under the permutation is 2, the image of 3 is 5, the image of 2 is 1, the image of 5 is 4, and the image of 4 is 3.

The two-line notation for a permutation is not unique, because the order of elements in the first row is arbitrary.

It is easy to multiply permutations written in the two-line notation, but hard to determine the order of such a permutation.

If we fix, once and for all, the order of elements in the first row of the permutation, then we can omit the first row of the permutation and simply write the second row. This is termed the one-line notation for permutations. For instance, for the set \{ 1, 2, 3, 4, 5 \}, we can decide that the first row will always have 1,2,3,4,5 in that order. In this case, the two-line notation is:

\begin{pmatrix}
1 & 2 & 3 & 4 & 5\\
2 & 1 & 5 & 3 & 4\\\end{pmatrix}

Thus, the one-line notation for the above permutation is:

2, 1, 5, 3, 4


Order

For a finite set

The symmetric group on a finite set of size n, has order equal to the factorial of n, denoted n!, where:

n! = \prod_{i=1}^n i = 1 \cdot 2 \cdot 3 \cdots n.

This is proved by a simple counting argument: for a permutation on a finite set, there are n possibilities for the image of the first element, (n-1) possibilities for the image of the second element, and so on. The product rule yields that the total number of permutations is n!.

WHAT'S MORE: Some more things about the symmetric group, based on material seen later in the tour. Skip if reading for the first time.


Cycle decomposition for permutations

Further information: cycle decomposition for permutations, cycle decomposition theorem for permutations, understanding the cycle decomposition

Any permutation can be expressed uniquely as a product of disjoint cycles. A cycle (a_1, a_2, \ldots, a_n) being in a permutation means that under the permutation, a_j gets mapped to a_{j+1}, and a_n gets mapped to a_1. Two cycles are disjoint if they do not have any element in common. Note that the cycles (a_1, a_2, \ldots, a_n) and (a_n, a_1, \ldots, a_{n-1}) are the same.

For instance, the cycle decomposition of the permutation discussed in the previous example is:

(1, 2)(3,5,4)

In other words, the permutation sends 1 to 2, 2 to 1. It sends 3 to 5, 5 to 4, and 4 to 3. It turns out that, for the symmetric group on a finite set, every permutation can be uniquely expressed as a product of disjoint cycles (upto the order of the cycles). This is the cycle decomposition theorem for permutations. Permutations written in terms of cycle decompositions are easy to multiply and invert, and their order can also be determined easily.

The cycle decomposition:

(2,5)

refers to a permutation that interchanges 2 and 5 and does not move any of the other elements. In other words, it is short for:

(2,5)(1)(3)(4)

where we omit writing the cycles of size one.

A cycle of size two is termed a transposition.

Upto conjugacy

The elements of the symmetric group on a set are divided into a number of conjugacy classes. It turns out that, for a finite group, the conjugacy class of a permutation is completely characterized by the sizes of the cycles in its cycle decomposition. In other words, if two permutations have an equal number of cycles of each size in their cycle decomposition, they are conjugate; conversely, if they are conjugate, they have an equal number of cycles of each size in their cycle decomposition.

Further information: cycle type determines conjugacy class, element structure of symmetric groups

Upto automorphism

Except for the symmetric group of degree six, the cycle type of a permutation also determines it uniquely upto automorphism. In the symmetric group of order six, the cycle type of transpositions (a single cycle of size two), and triple transpositions (product of three disjoint cycles of size two) are related by an outer automorphism.

For an infinite set

The symmetric group on an infinite set has order equal to the cardinality of the power set of that set. In particular, no symmetric group on an infinite set is countable.

The finitary symmetric group on an infinite set (i.e., the group of those permutations that move only finitely many elements) has order equal to the cardinality of that infinite set. In particular, it is always a proper subgroup of the whole symmetric group on that infinite set.

This page is part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Introduction five (beginners)| UP: Introduction five (beginners)| NEXT: Understanding the cycle decomposition
Expected time for this page: 20 minutes
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part