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