You are here
Homecyclic permutation
Primary tabs
cyclic permutation
Let $A=\{a_{0},a_{1},\ldots,a_{{n1}}\}$ be a finite set indexed by $i=0,\ldots,n1$. A cyclic permutation on $A$ is a permutation $\pi$ on $A$ such that, for some integer $k$,
$\pi(a_{i})=a_{{(i+k)\!\!\!\!\!\!\;\;(\mathop{{\rm mod}}n)}},$ 
where $a\!\!\;\;(\mathop{{\rm mod}}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(mr+1)$  $\displaystyle=$  $\displaystyle m$  
$\displaystyle\pi(mr+2)$  $\displaystyle=$  $\displaystyle 1$  
$\displaystyle\vdots$  
$\displaystyle\pi(m)$  $\displaystyle=$  $\displaystyle r1.$ 
In the usual permutation notation, it looks like
$\pi=\left(\begin{array}[]{ccccccc}1&2&\cdots&mr+1&mr+2&\cdots&m\\ r&r+1&\cdots&m&1&\cdots&r1\end{array}\right)$ 
Remark. For every finite set of cardinality $n$, there are $n$ cyclic permutations. Each nontrivial 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 $ababa$ 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 $abab$, 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 onetoone 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.
Mathematics Subject Classification
94B15 no label found20B99 no label found0300 no label found05A05 no label found11Z05 no label found94A60 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections