Symmetric group

From Groupprops
Jump to: navigation, search
This article is about a basic definition in group theory. The article text may, however, contain advanced material.
VIEW: Definitions built on this | Facts about this: (facts closely related to Symmetric group, all facts related to Symmetric group) |Survey articles about this | Survey articles about definitions built on this
VIEW RELATED: Analogues of this | Variations of this | Opposites of this |[SHOW MORE]
This article defines a group property: a property that can be evaluated to true/false for any given group, invariant under isomorphism
View a complete list of group properties
VIEW RELATED: Group property implications | Group property non-implications |Group metaproperty satisfactions | Group metaproperty dissatisfactions | Group property satisfactions | Group property dissatisfactions


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



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.


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!.


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.


Subgroups

Every group is a subgroup of a symmetric group

Further information: Cayley's theorem

Every group can be embedded as a subgroup of a symmetric group, namely, the symmetric group on itself as a set. We do this by making the group act on itself by left multiplication (this is the regular group action).

Finitary symmetric group

Symmetric groups on infinite sets in general behave very differently from symmetric groups on finite sets. For one, the permutation may not break up as a product of cycles. For instance, the symmetric group on the set of integers, contains the permutation that adds 1 to every integer.

To imitate the theory of symmetric groups on finite sets for infinite sets, we can use the finitary symmetric group. The finitary symmetric group on any set is the subgroup of the symmetric group comprising those permutations that move only finitely many elements (called finitary permutations). Cycle decomposition still holds for finitary permutations.

Alternating group

Further information: even permutation, alternating group, finitary alternating group

An important subgroup of the symmetric group on a finite set (or, the finitary symmetric group on any set is the alternating group. This is defined as the subgroup comprising the even permutations. To understand the notion of even permutation, we note that:

  • Every (finitary) permutation can be expressed as a product of transpositions. For full proof, refer: Transpositions generate finitary symmetric group
  • The number of transpositions needed to express a finitary permutation may depend on the way we choose to express the product. However, the parity of the number of transpositions needed is independent of the choice of product.
  • Thus, we can define an even permutation as a permutation expressible as a product of evenly many transpositions, and an odd transposition as a permutation expressible as a product of an odd number of transpositions.

The (finitary) alternating group is the subgroup comprising the even permutations. It is clearly a subgroup, and is normal with index two. The map that sends a permutation to its sign (whether or not it is even or odd) can be viewed as a homomorphism to the cyclic group of order two, and the alternating group is the kernel of this homomorphism.

Group properties

Generating sets and presentations

Generating sets

Presentations

IAPS structure

Further information: Permutation IAPS

The permutation IAPS is an IAPS of groups whose m^{th} member is the symmetric group on the set \{ 1,2,3, \dots, m \}, with the concatenation map given by making the left permutation act on the first m elements and the right permutation act on the last n elements.

Particular cases

Of particular note are:

Small finite values

Since alternating groups are simple for degree at least five, all symmetric groups of degree at least five are not solvable. Also, all symmetric groups of degree greater than two are centerless, and among them, the one of degree six is the only one that is not complete.

Cardinality of set, n Common name for symmetric group of that degree, S_n Order, n! Prime factorization of order Comments
0 trivial group 1 Trivial
1 trivial group 1 Trivial
2 cyclic group:Z2 2 2 group of prime order. In particular, abelian
3 symmetric group:S3 6 2 \cdot 3 supersolvable but not nilpotent. Also, complete
4 symmetric group:S4 24 2^3 \cdot 3 solvable but not supersolvable or nilpotent. Also, complete
5 symmetric group:S5 120 2^3 \cdot 3 \cdot 5 not solvable. Has simple non-abelian subgroup of index two. Also, complete
6 symmetric group:S6 720 2^4 \cdot 3^2 \cdot 5 not solvable, and not complete.
7 symmetric group:S7 5040 2^4 \cdot 3^2 \cdot 5 \cdot 7 not solvable. Has simple non-abelian subgroup of index two. Also, complete
8 symmetric group:S8 40320 2^7 \cdot 3^2 \cdot 5 \cdot 7 not solvable. Has simple non-abelian subgroup of index two. Also, complete
9 symmetric group:S9 362880 2^7 \cdot 3^4 \cdot 5 \cdot 7 not solvable. Has simple non-abelian subgroup of index two. Also, complete
10 symmetric group:S10 3628800 2^8 \cdot 3^4 \cdot 5^2 \cdot 7 not solvable. Has simple non-abelian subgroup of index two. Also, complete

Specific information

Here are articles with specific information about symmetric groups: