Definition:Permutation on n Letters

Definition

Let $\N^*_k$ be defined as the subset of natural numbers $\N^*_k = \left[{1 .. k}\right] = \left\{{1, 2, 3, \ldots, k}\right\}$.

A permutation of $n$ letters is a permutation $\pi: \N^*_n \to \N^*_n$.

The usual symbols for denoting a general permutation are $\pi$ (not to be confused with the famous circumference over diameter), $\rho$ and $\sigma$.

Set of All Permutations

The set of all permutations of $n$ letters is denoted $S_n$.

Two-Row Notation

Let $\pi$ be a permutation on $n$ letters.

The two-row notation for $\pi$ is written as two rows of elements of $\N^*_n$, as follows:

$\pi = \begin{bmatrix} 1 & 2 & 3 & \ldots & n \\ \pi \left({1}\right) & \pi \left({2}\right) & \pi \left({3}\right) & \ldots & \pi \left({n}\right) \end{bmatrix}$

The bottom row contains the effect of $\pi$ on the corresponding entries in the top row.

Cycle Notation

The two-row notation is a cumbersome way of defining a permutation.

Instead, the cycle notation is usually used instead.

The $k$-cycle $\rho$ is denoted $\begin{bmatrix} i & \rho \left({i}\right) & \ldots & \rho^{k-1} \left({i}\right) \end{bmatrix}$.

From Cycle Decomposition, all permutations can be defined as the product of disjoint cycles, and it doesn't matter in what order as Disjoint Permutations Commute.

So, for a given permutation $\rho$, the cycle notation for $\rho$ consists of all the disjoint cycles into which $\rho$ can be decomposed, concatenated as a product.

It is conventional to omit 1-cycles from the expression, and to write those cycles with lowest starting number first.

Canonical Representation

The permutation:

$\begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 4 & 3 & 5 \end{bmatrix} $

can be expressed in cycle notation as:

$\begin{bmatrix} 1 & 2 \end{bmatrix} \begin{bmatrix} 3 & 4 \end{bmatrix}$

or as:

$\begin{bmatrix} 3 & 4 \end{bmatrix} \begin{bmatrix} 5 \end{bmatrix} \begin{bmatrix} 1 & 2 \end{bmatrix}$

or as:

$\begin{bmatrix} 4 & 3 \end{bmatrix} \begin{bmatrix} 2 & 1 \end{bmatrix}$

etc.

However, only the first is conventional. This is known as the canonical representation.

Alternative Notation

Some sources use $S \left({n}\right)$ for $S_n$.

Some sources use round brackets for the cycle notation: $\begin{pmatrix} 1 & 2 \end{pmatrix} \begin{pmatrix} 3 & 4 \end{pmatrix}$

Also see

• Symmetric Group

Sources

• J.A. Green: Sets and Groups (1965)... (previous)... (next): $\S 3.6$: Example $54$
• Seth Warner: Modern Algebra (1965): $\S 8$
• Richard A. Dean: Elements of Abstract Algebra (1966): $\S 1.6$
• Ian D. Macdonald: The Theory of Groups (1968): Appendix
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 29 \delta$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 34 \ (4)$
• John F. Humphreys: A Course in Group Theory (1996): $\S 9$