Permutation

From Groupprops
Jump to: navigation, search

Definition

A permutation on a set is defined as a bijective function from the set to itself.

The set of all permutations on a set forms a group with the group operation being function composition, the identity element being the identity function, and the inverse of a permutation being the inverse function. This group is termed the symmetric group on the set. A permutation on a set can thus also be defined as an element of the symmetric group on the set.

Notation

Two-line notation for permutations

Further information: two-line notation for permutations

Suppose S is a finite set and \sigma is a permutation of S. A two-line notation for \sigma is a two-line description that uniquely determines \sigma. The first row lists the elements of S. In the second row, we list, below each element of S, its image under \sigma.

For instance, consider the permutation on \{1,2,3,4,5 \} that sends x to 6 - x. The two-line notation for this permutation is:

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

One-line notation for permutations

Further information: one-line notation for permutations

The one-line notation for a permutation is an abbreviated form of the two-line notation where we write only the second line, because the first line is understood. This happens, for instance, when the elements of S come with a standard ordering and it is understood that the first line, if written, would have the elements in that order.

Cycle decomposition for permutations

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

The cycle decomposition of a permutation is an expression of the permutation as a product of disjoint cycles. For instance, the permutation on \{ 1,2,3,4,5 \} has three cycles: (1,5), (2,4) and (3). The cycle decomposition is this (1,5)(2,4)(3).