cyclic permutation

Let $A=\{a_{0},a_{1},\ldots,a_{n-1}\}$ be a finite set indexed by $i=0,\ldots,n-1$ . A cyclic permutation on $A$ is a permutation $\pi$ on $A$ such that, for some integer $k$ ,

\pi(a_{i})=a_{(i+k)\!\!\!\!\!\!\pmod{n}},

where $a\!\!\pmod{b}:=a-\lfloor a/b\rfloor b$ , the remainder of $a$ when divided by $b$ , and $\lfloor\cdot\rfloor$ is the floor function.

For example, if $A=\{1,2,\ldots,m\}$ such that $a_{i}=i+1$ . Then a cyclic permutation $\pi$ on $A$ has the form

$\displaystyle\pi(1)$	$\displaystyle=$	$\displaystyle r$
$\displaystyle\pi(2)$	$\displaystyle=$	$\displaystyle r+1$
	$\displaystyle\vdots$
$\displaystyle\pi(m-r+1)$	$\displaystyle=$	$\displaystyle m$
$\displaystyle\pi(m-r+2)$	$\displaystyle=$	$\displaystyle 1$
	$\displaystyle\vdots$
$\displaystyle\pi(m)$	$\displaystyle=$	$\displaystyle r-1.$

In the usual permutation notation, it looks like

\pi=\left(\begin{array}[]{ccccccc}1&2&\cdots&m-r+1&m-r+2&\cdots&m\\ r&r+1&\cdots&m&1&\cdots&r-1\end{array}\right)

Remark. For every finite set of cardinality $n$ , there are $n$ cyclic permutations. Each non-trivial cyclic permutation has order $n$ . Furthermore, if $n$ is a prime number, the set of cyclic permutations forms a cyclic group.

Cyclic permutations on words

Given a word $w=a_{1}a_{2}\cdots a_{n}$ on a set $\Sigma$ (may or may not be finite), a cyclic conjugate of $w$ is a word $v$ derived from $w$ based on a cyclic permutation. In other words, $v=\pi(a_{1})\pi(a_{2})\cdots\pi(a_{n})$ for some cyclic permutation $\pi$ on $\{a_{1},\ldots,a_{n}\}$ . Equivalently, $v$ and $w$ are cyclic conjugates of one another iff $w=st$ and $v=ts$ for some words $s, t$ .

For example, the cyclic conjugates of the word $a b a b a$ over $\{a,b\}$ are

baba^{2},\quad aba^{2}b,\quad ba^{2}ba,\quad a^{2}bab,\quad\mbox{and itself}.

Strictly speaking, $\pi$ is a cyclic permutation on the multiset $A=\{a_{1},\ldots,a_{n}\}$ , which can be thought of as a cyclic permutation on the set $A^{\prime}=\{(1,a_{1}),\ldots,(n,a_{n})\}$ . Furthermore, $\pi$ can be extended to a function on $A^{*}$ : for every word $w=a_{\phi(1)}\cdots a_{\phi(m)}$ , $\pi(w):=\pi(a_{\phi(1)})\cdots\pi(a_{\phi(m)})$ , where $\phi$ is a permutation on $A$ .

Given any word $w=a_{1}a_{2}\cdots a_{n}$ on $\Sigma$ , two cyclic permutations $\pi_{1},\pi_{2}$ on $\{a_{1},\ldots,a_{n}\}$ are said to be the same if $\pi_{1}(w)=\pi_{2}(w)$ . For example, with the word $a b a b$ , then the cyclic permutation

\left(\begin{array}[]{cccc}1&2&3&4\\ 3&4&1&2\end{array}\right)

is the same as the identity permutation. There is a one-to-one correspondence between the set of all cyclic conjugates of $w$ and the set of all distinct cyclic permutations on $\{a_{0},a_{1},\ldots,a_{n}\}$ .

Remarks.

•

In a group $G$ , if two elements $u, v$ are cyclic conjugates of one another, then they are conjugates: for if $u=st$ and $v=ts$ , then $v=t(st)t^{-1}=tut^{-1}$ .
•

Cyclic permutations were used as a ciphering scheme by Julius Caesar. Given an alphabet with letters, say $a,b,c,\ldots,x,y,z$ , messages in letters are encoded so that each letter is shifted by three places. For example, the name

“Julius Caesar” becomes “Mxolxv Fdhvdu”.

A ciphering scheme based on cyclic permutations is therefore also known as a Caesar shift cipher.

Title	cyclic permutation
Canonical name	CyclicPermutation
Date of creation	2013-03-22 17:33:54
Last modified on	2013-03-22 17:33:54
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	13
Author	CWoo (3771)
Entry type	Definition
Classification	msc 94B15
Classification	msc 20B99
Classification	msc 03-00
Classification	msc 05A05
Classification	msc 11Z05
Classification	msc 94A60
Synonym	Caesar cipher
Related topic	CyclicCode
Related topic	SubgroupsWithCoprimeOrders
Defines	Caesar shift cipher
Defines	cyclic conjugate