3
$\begingroup$

"Cyclic" and "Circular" permutations - are these two different concepts? I have been reading about permutation and encountering them in many places. What are the definitions of them, in simple English please. And what are the differences?

Thanks in advance

(Could you please explain in examples please, if not a problem. I read about "cyclic" permutation in Wikipedia but was very difficult to understand. Watched some videos about "circular" permutation (example of seating people around a table) at YouTube, somehow comprehensible. But difference between the concepts is remaining hazy)

$\endgroup$
4
  • 2
    $\begingroup$ I never heard people using "circular" permutation. Is the rotation by $\pi/3$ circular on the 24-th roots of unity, for example? $\endgroup$ Commented Jun 22, 2019 at 15:57
  • $\begingroup$ @user10354138 Is your question to me? $\endgroup$ Commented Jun 22, 2019 at 15:58
  • $\begingroup$ @Bahrom yes. What is a "circular" permutation in $S_n$? $\endgroup$ Commented Jun 22, 2019 at 15:59
  • $\begingroup$ :) Well, That's what I want to find out about more. $\endgroup$ Commented Jun 22, 2019 at 16:00

2 Answers 2

Reset to default
1
$\begingroup$ 
==== Circular Permutations ===

In the context of an linear ordered set $n$ objects, a circular permutation takes the first object to the second, the second to the third, and so on until the last object gets taken to the first object which is precisely what makes the permutation circular. The Wikipedia article Cyclic order states:

A set with a cyclic order is called a cyclically ordered set or simply a cycle.

and later also states

A cyclic order on a set $X$ can be determined by a linear order on $X$, but not in a unique way. Choosing a linear order is equivalent to choosing a first element, so there are exactly $n$ linear orders that induce a given cyclic order. Since there are $n!$ possible linear orders, there are $(n−1)!$ possible cyclic orders

and there is much more interesting information in the article.

In other words a circular permutation on a set makes it circularly ordered in the sense that the permutation maps each element to its immediate successor in the circular ordering.

=== Cyclic Permutations ===

The Wikipedia article Cyclic permutation states

a cyclic permutation (or cycle) is a permutation of the elements of some set X which maps the elements of some subset $S$ of $X$ to each other in a cyclic fashion, while fixing (that is, mapping to themselves) all other elements of $X$.

The Mathworld article Cyclic permutation states

A permutation which shifts all elements of a set by a fixed offset, with the elements shifted off the end inserted back at the beginning.

which means it is any composition power of a circular permutation and is a different meaning than the Wikipedia definition because an ordering of elements is assumed and there is an offset which, if it is not one, may produce multiple disjoint cycles. The context should make it clear which meaning is being used.

=== Cycles ===

Another way to state this is that in an extended sense, a cycle is a permutation of $n$ objects that is a circular permutation on a subset of the objects and leaves the others fixed, whereas in a strict sense no object is fixed. The standard important result is that any permutation is the composition of disjoint cycles in a unique way. With this terminology, a circular permutation is just exactly a permutation consisting of a single cycle that permutes all of the objects.

The etymology of the word "cyclic" or "cycle" comes from the Greek "kyklos" which means

"circle, wheel, any circular body," also "circular motion, cycle of events," 

=== Example 1 ===

For example, suppose we have an ordered set of objects $\{a,b,c,d\}.$ The permutation mapping $$ a\mapsto b,\; b\mapsto c,\; c\mapsto d,\; d\mapsto a $$ is a circular permutation of the set. The circular ordering induced by this mapping means that the ordered sets $$\{b,c,d,a\},\; \{c,d,a,b\},\; \{d,a,b,c\}$$ are each equivalent to the original ordered set considered as circular orderings.

=== Example 2 ===

Given the original ordered set of objects $\{a,b,c,d\},$ the permutation mapping $$ a\mapsto b,\; b\mapsto a,\; c\mapsto d,\; d\mapsto c $$ is a permutation consisting of two cycles of length two. One of the two cycles is a circular permutation of $\{a,b\}$ and the other of $\{c,d\}.$ this is not a circular permutation or cyclic permutation according to the Wikipedia definition because it contains two cycles, but it is a cyclic permutation with offset two according to the MathWorld definition.

$\endgroup$
4
  • 1
    $\begingroup$ This is rather misleading. When you say a circular permutation $\sigma$ takes the first object to the second, etc, it implies (as I read it) that $\sigma(1)=2,\sigma(2)=3$ etc. And your example reinforces this interpretation. But as I understand it, $\sigma(1)$ can be anything (except $1$). (Yes, I know that a set has no ordering on its elements, but that point is easily overlooked by a student.) $\endgroup$ Commented Jun 22, 2019 at 19:25
  • $\begingroup$ @TonyK Thanks for that useful comment! I have now explained circular ordering in my answer. $\endgroup$ Commented Jun 22, 2019 at 19:41
  • 1
    $\begingroup$ One of us has got hold of the wrong end of the stick here! As I understand it, a circular permutation is just a cyclic permutation that leaves no element unchanged. There are $(n-1)!$ of these. You imply that there are only $n-1$ circular permutations; but this assumes an ordering on the set that doesn't exist in general. $\endgroup$ Commented Jun 22, 2019 at 20:00
  • $\begingroup$ @TonyK Thanks for that useful comment! i will adjust my answr to be clearer on this point. $\endgroup$ Commented Jun 22, 2019 at 20:04
0
$\begingroup$

I believe a circular permutation of an ordered set $\{a,b,c,d\}$ would be one where the positions of all elements are all shifted by the same amount, for example $$ \sigma_1:a \mapsto b, b \mapsto c, c\mapsto d, d \mapsto a\qquad (\text{shift by one place})$$ but also $$ \sigma_2: a \mapsto c, b \mapsto d, c\mapsto a, d \mapsto b\qquad (\text{shift by two places})$$ Note that the notion of circular permutation is not defined, if the set on which the permutation acts is not ordered.

A cyclic permutation, on the other hand, is one that is a single cycle, that is by going from one element to the one given by the permutation we'll eventually pass through all elements. $\sigma_1$, given above is cyclic, but $\sigma_2$ isn't (because starting from $a$ we get $a\rightarrow c \rightarrow a$, and we're back in the starting point without passing through all elements of the set. Another example of cyclic permutation, that is not circular, can be $$ \sigma_3 : a\mapsto c, b\mapsto d,c\mapsto b,d\mapsto a$$
Starting from $a$ we have a cycle $a\rightarrow c\rightarrow b \rightarrow d \rightarrow a$ going through all elements of the set. The notion of cyclicity doesn't require the set to be ordered.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.