Definition:Cyclic Permutation

From ProofWiki
(Redirected from Definition:K-Cycle)
Jump to navigation Jump to search

Definition

Let $S_n$ denote the symmetric group on $n$ letters.

Let $\rho \in S_n$ be a permutation on $S$.


Then $\rho$ is a cyclic permutation of length $k$ if and only if there exists $k \in \Z: k > 0$ and $i \in \Z$ such that:

$(1): \quad k$ is the smallest such that $\map {\rho^k} i = i$
$(2): \quad \rho$ fixes each $j$ not in $\set {i, \map \rho i, \ldots, \map {\rho^{k - 1} } i}$.


$\rho$ is usually denoted using cycle notation as:

$\begin{pmatrix} i & \map \rho i & \ldots & \map {\rho^{k - 1} } i \end{pmatrix}$

but some sources introduce it using two-row notation:

$\begin{pmatrix} a_1 & a_2 & \cdots & a_k & \cdots & i & \cdots \\ a_2 & a_3 & \cdots & a_1 & \cdots & i & \cdots \end{pmatrix}$


Also known as

A cyclic permutation of length $k$ is also known as:

a cycle of length $k$
a $k$-cycle
generally, just a cycle.

Some sources give it as circular permutation.


Examples

Symmetric Group on $3$ Letters

Each of the non-identity elements of the Symmetric Group on 3 Letters is a cyclic permutation.

Expressed in cycle notation, they are as follows:

\(\ds e\) \(:=\) \(\ds \text { the identity mapping}\)
\(\ds p\) \(:=\) \(\ds \tuple {1 2 3}\)
\(\ds q\) \(:=\) \(\ds \tuple {1 3 2}\)


\(\ds r\) \(:=\) \(\ds \tuple {2 3}\)
\(\ds s\) \(:=\) \(\ds \tuple {1 3}\)
\(\ds t\) \(:=\) \(\ds \tuple {1 2}\)


Non-Cyclic Element of Symmetric Group on $4$ Letters

Not all permutations are cycles.

Here is an example (written in two-row notation) of a permutation of the Symmetric Group on 4 Letters which is not a cycle:

$\begin{pmatrix}

1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix}$


Also see

  • Results about cyclic permutations can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Cyclic_Permutation&oldid=665344"