# Permutation group

The group consisting of all possible permutations of *N* objects is known as the **permutation group** or **symmetric group**. A permutation is an invertible function from a set to itself. The group is usually denoted by S_{N}. It is a group of order *N*! (*N* factorial) and is a central object of study in group theory.

## Contents |

## [edit] Permutations

Consider a linear array *A* of *N* objects, numbering the positions in the array from 1 to *N*. A permutation π, designated as

is the following map:

That is, π moves the object in position *k* of the linear array *A* into position π(*k*); this is the *active convention*, the objects are moved as the pieces on a chessboard.

This map is surjective (onto) by definition as well as injective, i.e.
*k* ≠ l implies that π(*k*) ≠ π(l). A permutation
can thus be defined as a one-to-one map (bijection) of
{1, 2, ..., *N*} onto itself. Since it is assumed
that the positions in the array *A* are counted from left to right,
there is no need to number the positions of *A* explicitly. Furthermore,
*A* is loosely referred to as a "set" of objects with elements written between braces.^{[1]}
The set obtained from *A* by the action of π is denoted by
π(A).

**Example**

For a set where the objects are numbered, e.g., , the
effect of π on the subscripts (the numbering) is

In order to follow consistently the active convention, the inverse π^{−1} of π appears here. The inverse of π is the permutation that undoes the effect of π (see below). An alternative, yet valid, convention of defining the permutation π is the following (passive) one: an object in position *k* is *replaced* by an object in position
π(*k*), for *k*= 1, ..., *N* successively. In the example above
this would yield the set

or, generally, the passive convention is,

This interpretation clearly gives permutations that are the inverse of the active convention. It is obvious that one must adhere to one chosen convention.

Application of π to *A* followed by application π′ defines a
new permutation π′′, the product—or composition—of π
and π′. This is written as π′′ = π′ π.

**Example**

Start with the rightmost permutation (permutations act to the right):

(The rightmost permutation π moves the object in position 1 to position 3, then second permutation π' moves the object in position 3 to position 1. The object in position 2 goes to position 5 and then stays there, etc.).

It follows immediately from this definition that the multiplication of permutations is associative:

- .

Furthermore, a permutation π, being a one-to-one map of
{1, 2, ..., *N*} onto itself, has a unique inverse, denoted by
π^{−1} , with the property

The identity element *e* is the identity permutation

which is the map sending each element to itself.
The inverse permutation π^{−1} is simply obtained by interchanging
the two rows of π (i.e., interchange of the domain and the range of
π).

**Example**

## [edit] Permutation group

The associativity of the product, the existence of an identity permutation and the existence of a unique inverse of a permutation imply that the set of all permutations forms a group. This is the *permutation* (or *symmetric*) *group*, commonly denoted by
S_{N}. Since there are *N*! different one-to-one maps of {1,2,..., *N*} onto itself, this group has the order *N*! (the factorial function).

## [edit] Cycle notation

Often a more concise notation for permutations is used.
Define a *cycle* *c* of length
λ (a λ-cycle), denoted by

as the permutation π_{c}

which moves an object in position *i*_{1} to position *i*_{2} an object in position *i*_{2} to position *i*_{3}, etc., until finally an object in position *i*_{λ} to position *i*_{1}.

**Example**

Any permutation can be written as a product of disjoint cycles.

**Example**

This example also illustrates the fact that the inverse of is ; simply reverse the order within the cycles, but the number and lengths of cycles is unchanged.

It is common to omit the 1-cycles from a permutation written in cycle notation, except in the case of identity permutation *e* = (1)(2) ⋅ ⋅ (*N*), which in cycle notation is usually denoted by (1). The element appearing in a 1-cycle is sometimes referred to as a *fixed point* of the permutation because it is not moved by the permutation.

The order of a permutation is the least common multiple of the cycle lengths in the cycle decomposition.

## [edit] Permutational parity

One defines the *parity* (also known as *sign* or *signature*) of a λ-cycle as the number (−1)^{λ+1}. If this
number is 1, the cycle has *even parity*, if it is −1, the cycle has *odd parity*. Thus, 1-cycles are of even parity, 2-cycles
(*transpositions*) are of odd parity, and so on. If a permutation
π is factorized into (not necessarily disjoint) cycles,

where *c _{i}* is of length λ

_{i}, then the parity of π, denoted by (−1)

^{π}, is defined by the product of the parities of the constituting cycles,

For example, the permutation π = (1 3 2)(4 5) has the parity

Clearly, π^{−1} has the same parity as π, since the *cycle structure* (the number and lengths of cycles) of π is the same as of π^{−1}. Cycle structure is also known as *cycle shape*.

An alternative and completely equivalent way to define permutational parity is by decomposition of a permutation into 2-cycles (transpositions). A cycle can be written as a product of transpositions,
, and hence every permutation in S_{N}, for *N* > 1, can be written as a product of transpositions.
A permutation of *N* objects is then called *even* if it can be written as the product of an even number of transpositions and *odd* if it can be written as the product of an odd number of transpositions.
The nontrivial fact about this terminology is that it is well-defined; that is, no permutation is both even and odd.
Note that the number of transpositions factoring a permutation is not fixed, it is always possible to multiply by an even number of transpositions that give the identity element. For instance, a cycle *c* is equal to *c*(*i j*)(*j i*)(*k ℓ*)(*ℓ k*).

The even permutations in S_{N} form a subgroup of S_{N}. This subgroup is called the *alternating group on N objects* and denoted by *A*_{N}. In fact, *A*_{N} is always a normal subgroup of S_{N}, all odd permutations being in a coset that is both a left and a right coset of *A*_{N}. The order of *A*_{N} is .

## [edit] Conjugacy classes

From elementary group theory it is known that the conjugacy relation

is an equivalence relation, i.e., the permutations *τ* and *τ ^{π}* belong to the same equivalence class, referred to as a

*conjugacy class*.

There is a simple way to compute *τ ^{π}* from a given

*τ*and

*π*. Consider

*π*:

*k*→ π(

*k*), for

*k*= 1, ...,

*N*, successively, and let

*τ*be written in cycle notation. Then the permutation

*τ*is obtained by replacing in

^{π}*τ*the number

*k*by the number

*π*(

*k*) for all

*k*.

**Example**

For

we have

One can easily verify this rule by computing *π*^{−1} and
by doing the required multiplications.
The rule immediately implies that
any two conjugate permutations have the same *cycle structure* (cycle shape),
i.e., they consist of the same number of cycles of the same length.

Conversely, if two permutations *τ* and *τ*′ have the same
cycle structure, there exists at least one permutation *π* such that

so that equal cycle structure implies conjugacy. The permutation *π* can easily be found from a given pair *τ* and *τ*′ by inverting the recipe given above for the calculation of *τ ^{π}*.

**Example**

For

it follows that

Note, parenthetically, that the permutation *π* is not unique since
*τ′* = (2 6 5)(1 3 4) [is equal to (1 3 4)(2 6 5)] gives by application of the inverse recipe:

so that two different permutations *π* connect *τ* with *τ*′ by a conjugacy relation.

The following summarizes the important result in the theory of the permutation group:

Two permutations are conjugate (belong to the same conjugacy class) if and only if they have the same cycle structure. A cycle structure (cycle shape) is defined uniquely by specifying the lengths λ_{i}of all cycles (including the 1-cycles). These lengths form a partition ofN, i.e., a sequence {λ_{1}, λ_{2}, ..., λ_{k}} of positive integers such that

**Example**

The cycle structure of (1 4 3)(2 6) in S_{7} is given by λ_{1} = 3, λ_{2} = 2,
λ_{3} = λ_{4} = 1
so that λ_{1} + λ_{2} + λ_{3}+ λ_{4} = 7—to determine the cycle structure we must not forget the 1-cycles.

### [edit] Remark

According to elementary group representation theory, the number of conjugacy classes of a finite group equals the number of non-equivalent irreducible representations. Hence it is plausible that the irreducible representations of S_{N} can be labeled by partitions of
*N*. Graphically, partitions may be represented by Young diagrams named for the mathematician Alfred Young (1873 – 1940). Young developed an algorithm that indeed enables the construction of unique irreducible matrix representations of S_{N} from Young diagrams (partitions of *N*).

## [edit] On the structure of the symmetric group

The group S_{N} has proper normal subgroups if and only if *N* ≥ 3. For *N* > 4 the only proper normal subgroup of S_{N} is the alternating group *A*_{N}. When *N* = 4, there is an additional proper normal subgroup, often denoted *V* (isomorphic to Klein's Vierergruppe), consisting of the identity permutation and the permutations (1 2)(3 4), (1 3)(2 4), and (1 4)(2 3).

## [edit] Orbits and Blocks

Let *G* be a subgroup of S_{N}. The elements of *G* act also on {1,...,*N*}. One may define an equivalence relation, indicated by ~, on {1,...,*N*}, where *i*~*j*, *i, j* ∈ {1,...,*N*}, means that some element of *G* maps *i* to *j*. The resulting equivalence classes are called *orbits*. The group*G* is called *transitive* if {1,...,*N*} forms one single orbit.

Let the orbits of *G* be *O*_{1} ... *O*_{k}. The action of *G* on *O*_{i} gives a homomorphism
φ_{i} : *G* →
, where |*O*_{i}| is the order of *O*_{i}. While *G* is isomorphic to a subgroup of the product of the φ_{i}(*G*), this product is not, in general, isomorphic to *G*. For example, any *G* can be made to act on 2*N* points by using two copies of its action on *N* points. Yet no finite *G*, aside from the trivial group, is isomorphic to *G*×*G*.

While an intransitive permutation group may be broken up into orbits, a transitive permutation group has to be analyzed with greater subtlety: it could be *primitive*, or its action will be 'condensable' into an action on a set of *blocks*.

A *primitive* permutation group on the points {1,...,*N*} (it is assumed that *N* > 1 here) is, with only one exception, a group which leaves invariant no proper partition of {1,...,*N*}:
A partition of {1,...,*N*} is an expression of {1,...,*N*} as a union of pairwise disjoint subsets.
Any partition is proper, except for {1,...,*N*} = {1,...,*N*} and the expression of {1,...,*N*} as the union of its one-element subsets.
Permutations of indices naturally induce permutations of partitions: for example, the permutation (1 2 3 4) sends the partition to , sends the partition to the partition , and sends the partition to (i.e., to itself). So the cycle (1 2 3 4) induces the permutation (12 34, 14 23)(13 24) on the partitions of {1,2,3,4} into 2 disjoint 2-element sets.

Since {1,2} has no proper partitions, the trivial subgroup of S_{2} would be considered primitive by the preceding, but it is not considered primitive: this is the sole exception referred to above. This is done for consistency: If *N* ≥ 3, then {1,...,*N*} has proper partitions.
If *G* is trivial, then *G* fixes every partition of {1,...,*N*}, including the proper ones.
If *G* is nontrivial but intransitive, the partition of {1,...,*N*} into orbits for the action of *G* will be proper (the nontriviality of *G* excludes the partition into singletons, while the intransitivity of *G* excludes the one-block partition), and it is a *G*-invariant partition of {1,...,*N*}. Thus primitive permutation groups are transitive, including the case when *N*=2.

## [edit] Note

- ↑ Since some of the objects in the array may be identical and since the objects are ordered by their position in the array, it would be better to speak of a family—or a finite sequence—rather than of a set.