PlanetMath: cyclic permutation

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (191)
Orphanage
Unclass'd (1)
Unproven (496)
Corrections (7)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

cyclic permutation

(Definition)

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 is a permutation $\pi$ on such that, for some integer ,

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

where $a\!\!\pmod b:= a - \lfloor a/b \rfloor b$ , the remainder of

when divided by

, and $\lfloor \cdot \rfloor$ is the floor function.

For example, if $A=\lbrace 1,2,\ldots,m\rbrace$ such that . Then a cyclic permutation $\pi$ on 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

$\displaystyle \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 , there are cyclic permutations. Each non-trivial cyclic permutation has order . Furthermore, if 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 is a word derived from 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, and are cyclic conjugates of one another iff and for some words .

For example, the cyclic conjugates of the word over $\lbrace a,b\rbrace$ are

$\displaystyle baba^2,\quad aba^2b,\quad ba^2ba,\quad a^2bab,$ and itself $\displaystyle .$

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

: 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

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 , then the cyclic permutation

$\displaystyle \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

and the set of all distinct cyclic permutations on $\lbrace a_0,a_1,\ldots, a_n\rbrace$ .

Remarks.

In a group , if two elements are cyclic conjugates of one another, then they are conjugates: for if and , 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.

"cyclic permutation" is owned by CWoo.

(view preamble)

See Also: cyclic code

Other names:

Caesar cipher

Also defines:

Caesar shift cipher, cyclic conjugate

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: places, alphabet, scheme, conjugates, group, one-to-one correspondence, identity, function, multiset, strictly, iff, finite, word, cyclic group, prime number, order, cardinality, permutation notation, floor function, remainder, integer, permutation, indexed by, finite set
There are 3 references to this entry.

This is version 10 of cyclic permutation, born on 2007-10-01, modified 2007-10-08.
Object id is 9974, canonical name is CyclicPermutation.
Accessed 1008 times total.

Classification:

AMS MSC:	20B99 (Group theory and generalizations :: Permutation groups :: Miscellaneous)
	03-00 (Mathematical logic and foundations :: General reference works )
	05A05 (Combinatorics :: Enumerative combinatorics :: Combinatorial choice problems )
	11Z05 (Number theory :: Miscellaneous applications of number theory)
	94A60 (Information and communication, circuits :: Communication, information :: Cryptography)
	94B15 (Information and communication, circuits :: Theory of error-correcting codes and error-detecting codes :: Cyclic codes)

Pending Errata and Addenda

None.

Discussion

forum policy

No messages.

Interact