Definition:Permutation on n Letters/Cycle Notation
Definition
Let $\N_k$ be used to denote the initial segment of natural numbers:
- $\N_k = \closedint 1 k = \set {1, 2, 3, \ldots, k}$
Let $\rho: \N_n \to \N_n$ be a permutation of $n$ letters.
The $k$-cycle $\rho$ is denoted:
- $\begin {pmatrix} i & \map \rho i & \ldots & \map {\rho^{k - 1} } i \end{pmatrix}$
From Existence and Uniqueness of Cycle Decomposition, all permutations can be defined as the product of disjoint cycles.
As Disjoint Permutations Commute, the order in which they are performed does not matter.
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{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 1 & 4 & 3 & 5 \end{pmatrix}$
can be expressed in cycle notation as:
- $\begin{pmatrix} 1 & 2 \end{pmatrix} \begin{pmatrix} 3 & 4 \end{pmatrix}$
or as:
- $\begin{pmatrix} 3 & 4 \end{pmatrix} \begin{pmatrix} 5 \end{pmatrix} \begin{pmatrix} 1 & 2 \end{pmatrix}$
or as:
- $\begin{pmatrix} 4 & 3 \end{pmatrix} \begin{pmatrix} 2 & 1 \end{pmatrix}$
etc.
However, only the first is conventional. This is known as the canonical representation.
Also denoted as
Some sources use square brackets for the cycle notation:
- $\begin{bmatrix} 1 & 2 \end{bmatrix} \begin{bmatrix} 3 & 4 \end{bmatrix}$
There may be instances in $\mathsf{Pr} \infty \mathsf{fWiki}$ of this convention being used.
Examples
Permutations in $S_8$
Consider the permutations in $S_8$, presented in two-row notation as:
\(\ds \pi\) | \(=\) | \(\ds \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 3 & 4 & 5 & 6 & 7 & 2 & 1 & 8 \end{pmatrix}\) | ||||||||||||
\(\ds \rho\) | \(=\) | \(\ds \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{pmatrix}\) |
These can be expressed in cycle notation as:
\(\ds \pi\) | \(=\) | \(\ds \begin{pmatrix} 1 & 3 & 5 & 7 \end{pmatrix} \begin{pmatrix} 2 & 4 & 6 \end{pmatrix}\) | ||||||||||||
\(\ds \rho\) | \(=\) | \(\ds \begin{pmatrix} 1 & 8 \end{pmatrix} \begin{pmatrix} 2 & 7 \end{pmatrix} \begin{pmatrix} 3 & 6 \end{pmatrix} \begin{pmatrix} 4 & 5 \end{pmatrix}\) |
We have that:
\(\ds \pi \rho\) | \(=\) | \(\ds \begin{pmatrix} 1 & 3 & 5 & 7 \end{pmatrix} \begin{pmatrix} 2 & 4 & 6 \end{pmatrix} \begin{pmatrix} 1 & 8 \end{pmatrix} \begin{pmatrix} 2 & 7 \end{pmatrix} \begin{pmatrix} 3 & 6 \end{pmatrix} \begin{pmatrix} 4 & 5 \end{pmatrix}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \begin{pmatrix} 1 & 8 & 3 & 2 \end{pmatrix} \begin{pmatrix} 4 & 7 \end{pmatrix} \begin{pmatrix} 5 & 6 \end{pmatrix}\) |
\(\ds \rho \pi\) | \(=\) | \(\ds \begin{pmatrix} 1 & 8 \end{pmatrix} \begin{pmatrix} 2 & 7 \end{pmatrix} \begin{pmatrix} 3 & 6 \end{pmatrix} \begin{pmatrix} 4 & 5 \end{pmatrix} \begin{pmatrix} 1 & 3 & 5 & 7 \end{pmatrix} \begin{pmatrix} 2 & 4 & 6 \end{pmatrix}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \begin{pmatrix} 1 & 6 & 7 & 8 \end{pmatrix} \begin{pmatrix} 2 & 5 \end{pmatrix} \begin{pmatrix} 3 & 4 \end{pmatrix}\) |
\(\ds \pi^2 \rho\) | \(=\) | \(\ds \pi \paren {\pi \rho}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \begin{pmatrix} 1 & 3 & 5 & 7 \end{pmatrix} \begin{pmatrix} 2 & 4 & 6 \end{pmatrix} \begin{pmatrix} 1 & 8 & 3 & 2 \end{pmatrix} \begin{pmatrix} 4 & 7 \end{pmatrix} \begin{pmatrix} 5 & 6 \end{pmatrix}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \begin{pmatrix} 1 & 8 & 5 & 2 & 3 & 4 \end{pmatrix} \begin{pmatrix} 6 & 7 \end{pmatrix}\) |
$\pi$ is of order $\lcm {4, 3} = 12$, and is of odd parity
$\rho$ is of order $2$, and is of even parity
$\pi \rho$ and $\rho \pi$ are both of order $\lcm {4, 2} = 4$, and are of odd parity
$\pi^2 \rho$ is of order $\lcm {6, 2} = 6$, and is of even parity.
Also see
Technical Note
The $\LaTeX$ code for \(\begin{pmatrix} 1 & 4 & 2 & 3 \end{pmatrix}\) is \begin{pmatrix} 1 & 4 & 2 & 3 \end{pmatrix}
.
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {II}$: New Structures from Old: $\S 8$: Compositions Induced on Subsets
- 1966: Richard A. Dean: Elements of Abstract Algebra ... (previous) ... (next): $\S 1.6$: Exercise $4.5$
- 1968: Ian D. Macdonald: The Theory of Groups ... (previous) ... (next): Appendix: Elementary set and number theory
- 1996: John F. Humphreys: A Course in Group Theory ... (previous) ... (next): Chapter $9$: Permutations