Let $A=\lbrace a_0,a_1,\ldots, a_{n-1}\rbrace$ 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=\lbrace 1,2,\ldots,m\rbrace$ such that $a_i=i+1$ . Then a cyclic permutation $\pi$ on $A$ has the form \begin{eqnarray*} \pi(1) &=& r \\ \pi(2) &=& r+1 \\ &\vdots & \\ \pi(m-r+1) &=& m \\ \pi(m-r+2) &=& 1 \\ &\vdots & \\ \pi(m) &=& r-1. \end{eqnarray*} In the usual permutation notation, it looks like

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_1a_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 $\lbrace a_1,\ldots, a_n\rbrace$ . 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 $\lbrace a,b\rbrace$ are $$baba^2,\quad aba^2b,\quad ba^2ba,\quad a^2bab,\quad\mbox{and itself}.$$ Strictly speaking, $\pi$ is a cyclic permutation on the multiset $A=\lbrace a_1,\ldots, a_n\rbrace$ , which can be thought of as a cyclic permutation on the set $A'=\lbrace (1,a_1),\ldots, (n,a_n)\rbrace$ . 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_1a_2\cdots a_n$ on $\Sigma$ , two cyclic permutations $\pi_1,\pi_2$ on $\lbrace a_1,\ldots, a_n\rbrace$ are said to be the same if $\pi_1(w)=\pi_2(w)$ . For example, with the word $abab$ , then the cyclic permutation

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.