Permutation

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)$.

Permutation matrix of a permutation

Further information: permutation matrix

The permutation matrix of a permutation $\sigma \in S_{n}$ is the $n\times n$ matrix $A$ such that $A_{ij}=1$ for $j=\sigma (i)$, $A_{ij}=0$ elsewhere. (Here, $S_{n}$ is the symmetric group on $n$ letters.)