# Symmetric group

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: (factscloselyrelated 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 propertiesVIEW 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 is defined as the symmetric group on a set of size .

### Definition with symbols

The **symmetric group** over a set (denoted as ) is defined as follows:

- The elements of the group are permutations on , (i.e., bijective maps from to itself).
- The product of two permutations is the permutation , i.e., the permutation given by .
- The identity element of the group is the identity map of .
- The inverse of a permutation is the permutation that sends each element to the unique such that .

A group is termed a **symmetric group** if for some set .

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 is denoted , or sometimes , and is also sometimes termed the *symmetric group of degree* .

## 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 is described as follows. It is a matrix with two rows and 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 :

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

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

### 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 being in a permutation means that under the permutation, gets mapped to , and gets mapped to . Two cycles are disjoint if they do not have any element in common. Note that the cycles and are the same.

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

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:

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:

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 , has order equal to the factorial of , denoted , where:

.

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

### 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 permutation*s). 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

- Centerless group: All except the symmetric group on two elements are centerless.
`Further information: Symmetric groups are centerless` - Complete group: All the finite ones except the symmetric group on two elements and the symmetric group on six elements.
`Further information: Symmetric groups on finite sets are complete, Symmetric groups on infinite sets are complete` - Rational group: All the finite ones are rational.
`Further information: Symmetric groups are rational`. See also linear representation theory of symmetric groups.

## Generating sets and presentations

### Generating sets

- Transpositions generate the finitary symmetric group: For symmetric groups on finite sets, and more generally, for the finitary symmetric group on any set, the transpositions form a generating set.
- Transpositions of adjacent elements generate the symmetric group on a finite set
- All transpositions involving one element generate the finitary symmetric group
- Symmetric group on a finite set is 2-generated

### Presentations

- Symmetric group on a finite set is a Coxeter group: The symmetric groups on finite sets have a presentation of a certain form, called a Coxeter presentation, where all the generators have order two, and their products have order either two or four.

## IAPS structure

`Further information: Permutation IAPS`

The permutation IAPS is an IAPS of groups whose member is the symmetric group on the set , with the concatenation map given by making the left permutation act on the first elements and the right permutation act on the last 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, | Common name for symmetric group of that degree, | Order, | 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 | supersolvable but not nilpotent. Also, complete | |

4 | symmetric group:S4 | 24 | solvable but not supersolvable or nilpotent. Also, complete | |

5 | symmetric group:S5 | 120 | not solvable. Has simple non-abelian subgroup of index two. Also, complete | |

6 | symmetric group:S6 | 720 | not solvable, and not complete. | |

7 | symmetric group:S7 | 5040 | not solvable. Has simple non-abelian subgroup of index two. Also, complete | |

8 | symmetric group:S8 | 40320 | not solvable. Has simple non-abelian subgroup of index two. Also, complete | |

9 | symmetric group:S9 | 362880 | not solvable. Has simple non-abelian subgroup of index two. Also, complete | |

10 | symmetric group:S10 | 3628800 | not solvable. Has simple non-abelian subgroup of index two. Also, complete |

## Specific information

Here are articles with specific information about symmetric groups: