Definition:Permutation on n Letters/Cycle Notation

From ProofWiki
Jump to navigation Jump to search

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

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Permutation_on_n_Letters/Cycle_Notation&oldid=643830"