Talk:Cyclic permutation

Stirling numbers

I added a reference to stirling numbers. - 141.225.146.175 (talk · contribs · logs) 21:57, 22 June 2005 (UTC)

Offset

Maybe I'm just being stupid but I don't understand what Offset means from this article as it isn't very clear... - Eraserhead1 14:30, 31 December 2005 (UTC)Eraserhead

Definition in terms of an example

Although a Mathematician, this article was hard for me to comprehend the first time I read it. My suggestion is to make it understandable for everyone by inserting the following practical but enlightening example in Definition 1: Suppose you have four objects labeled A,B,C,D and imagine that you arrange them in a circle side by side, each object being represented by a point on the circle. (A small scheme would be nice here). The arclengths between the points are not of significance. Choose a fixed orientation, say clockwise, and a point other than A, say C. Starting with C, read all the objects on the circle clockwise until each occurs exactly once. The outcome would be C,D,A,B and this is called a cyclic permutation of A,B,C,D. Following the same procedure for B and D we obtain all cyclic permutations of A,B,C,D.

Important Notice: As far I have searched, the concepts cyclic permutation and cycle are not identical. The only connection between them is that a cyclic permutation can be uniquely represented as a product of disjoint cycles, as can every permutation. —Preceding unsigned comment added by Ilknow (talk • contribs) 13:51, 21 January 2008 (UTC)

Merge tag

The following discussion is closed. Please do not modify it. Subsequent comments should be made in a new section.

The result was No consensus to merge -- Jreferee ^(Talk) 05:22, 17 August 2007 (UTC)

• Do not merge. Rather, I would like to see the cyclic permutation article reference strictly to it's practice in music, and move mathematical information to the cycle article. I was directed to cyclic permutation from twelve-tone technique; this article would be best as an expansion of its use in that context. If there is that much overlap, maybe a disambiguation page is in order. count_lawrence 14:15, 23 August 2006 (UTC)

  But at present there is nothing about music here: only three different definitions of what could be a cyclic permutation. Also, the article is completely ill written concerning formatting, language, punctuation, and missing references. — MFH:Talk 20:01, 10 November 2006 (UTC)

I've reverted Merge

I've temporarily reverted the merge of Cycle (mathematics) into this article, since I'm unconvinced that this is a good idea. I would like to have more discussion about this. Please see the discussion [Wikipedia_talk:WikiProject_Mathematics/Archive_27#Merge_of_Cycle_.28mathematics.29.2C_into_Cyclic_permutation here]. Paul August ☎ 22:30, 18 July 2007 (UTC)

From Wikipedia talk:WikiProject Mathematics

I transcribed the discussion below.--Jorfer 20:41, 30 July 2007 (UTC)

Merge of Cycle (mathematics), into Cyclic permutation

Recently Cycle (mathematics) was merged into Cyclic permutation. Since I'm unconvinced that this is a good idea, I've temporarily reverted that merge until we could have a discussion here. So what does everyone think? Paul August ☎ 22:29, 18 July 2007 (UTC)

• Well, you should have told us what's wrong here in the first place, to explain your actions. Anyway, I see multiple problems with all three articles and the way how the merge was performed by a well-meaning but obviously under qualified person. So I guess I support your move. I will think a bit what can be done here. For starters, IMO the title Cycle (mathematics) must be made into a "subdisambig" page made of Cycle#Mathematics, since the qualifier is way too general. At the moment I am not familiar with English math terminology, so I am quite suspicious with seeing three quite distinct things supposedly called Cyclic permutation. It particular, it seems to confuse permutation cycle and cyclic permutation, not to say it has no references. Also, "i -> (i+k)(mod n)" is called shift permutation, cyclic shift permutation rotation permutation or simply rotation. Tangentially: in my olden days of Russian mathematics, a methodological distinction was drawn between permutations and substitutions (in the same way as graphs are not the same as (0,1)-matrices, although there is a 1-1 correspondence). I will think for more.`'Míkka 23:33, 18 July 2007 (UTC)

  P.S. What a funny thing math is: in some texts an acyclic permutation is a cyclic permutation!-) `'Míkka 23:44, 18 July 2007 (UTC)

• I agree with the unmerge and agree that Cycle (mathematics) should be a disambig. As for maths terminology, I am not surprised at all that three different things are given the same name, but I think that in the postscript, Míkka has been confused by the notation - it is definitely meant to be an acyclic permutation. JPD (talk) 11:14, 19 July 2007 (UTC)

  Define acyclic permutation, then. Whatever it is, in the Travelling Salesman Problem permutations which are one full cycle of all elements are considered, so I am confused indeed, but not in the way you think. `'Míkka 16:10, 19 July 2007 (UTC)

  The way the term cycle, in the sense of cycle of a function, is used by mathematicians, it is not restricted to bijections, unlike what is suggested by Cycle (mathematics). Let f : S → S be any function. Then a cycle of f, with period p, is an infinite sequence a₀, a₁, ..., such that a_i+1 = f(a_i) for i = 0, 1, ..., a_k = a₀ for some k > 0, where p is the least such value of k. See, for example, the use of the term in the Collatz conjecture article. If f is viewed as the state transition function of an automaton, this is the same as an infinite loop in programmers' parlance.  --Lambiam 14:59, 19 July 2007 (UTC)

  ...and in permutation theory it used to be called permutation cycle or simply cycle. `'Míkka 16:10, 19 July 2007 (UTC)

• JPD wrote: "am not surprised at all that three different things are given the same name". Actually I am surprised. Maths used to be distinguished from all other domains by being least ambiguous and vague. Yes, some different things are called the same word, but usually they are in different branches of math, and the same word usually indicates the analogy. In this case we talking about a single very narrow domain of permutation theory/theory of permutations/permutation group theory (which even does not a Wikipedia article). So I smell that the naming mess is actually created by non-mathematicians. Therefore I suggest that whoever undertakes the job of cleaning the act here, please use definitions from reputable books, which are specifically devoted to permutations as a basis, not from random websites and arbitrary by-math articles. And of course, if some (mis)-usage is widespread, then we have to report it as well, but duly and clearly noting in which domain this alternative terminology is used. `'Míkka 16:22, 19 July 2007 (UTC)
• After quick look around, I noticed certain duplication is structurelessness in the area of theory of permutations: e.g. permutation group vs. symmetric group (the latter being a special case of perm groups: a group of all perms over N elems). This is not the first time that, paraphrasing a russian say, "Wikipedian not reader. Wikipedian writer." `'Míkka 16:56, 19 July 2007 (UTC)

  P.S. Usually I don't waste my time in talk pages and put my words into deeds right away, but here I am slowing down. I used to work with permutations about 30 years ago (and even had a couple articles published), but since then I radically changed my interests, so I cannot call myself an expert here, and therefore I do not want to start rewriting myself (especially not having books in perms handy), but I will take part in this job. `'Míkka 17:12, 19 July 2007 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

circular permutation

I have reverted the last edit for several reasons.

1. Carmichael's definition of circular permutation (A permutation such as ... is called a circular permutation or a cyclic permutation. [and later] A circular permutation on two letters, such as (ab), is called a transposition. [and his first theorem is] Any given permutation is a product of circular permutations no two of which have a letter in common.) is what we call a cyclic permutation, with fixed points allowed - there is no question about this.

2. Expanding on the difference between cyclic and circular permutations (in the modern sense) was a good edit, but the improvement on this just muddied the waters. No cycle has a distinguished starting element, so to say that a circular permutation is a permutation without a distinguished starting element does not differentiate the two ideas. You have to bring in the circular arrangement versus the linear arrangement of the elements to see the difference.

3. I can not parse the statement about leaving circular permutations invariant by composing with cycles in any meaningful way. Perhaps the intent was to rotate the circular permutation?

I think the problems are coming from trying to mix the passive (= arrangement) and active (= mapping = substitution) forms of permutations. Cycles are active while circular permutations are passive. Bill Cherowitzo (talk) 04:57, 8 June 2014 (UTC)

I've just added a section on circular permutations in Permutation#Definition and usage which I think says what was intended here. If that addition is ok, the problem of what to do on this page remains. Bill Cherowitzo (talk) 21:00, 8 June 2014 (UTC)

Why does "anticyclic" redirect here?

Word not used in article. Equinox (talk) 18:54, 8 September 2015 (UTC)

As far as I can tell this is related to the above discussion on circular permutations. A circular permutation (or if you prefer a cyclic permutation with no fixed points) can have one of two "orientations", clockwise or counterclockwise. If clockwise is the preferred orientation for cyclic permutations then counterclockwise would be the other orientation, that is, an anti-cyclic permutation. This terminology seems to be used only in applications and almost always in the situation where only three things are permuted. The circular permutations on three elements are either cyclic or anti-cyclic. If there are more elements involved then a circular permutation does not have to be either cyclic or anti-cyclic. Why the redirect? - I think it stems from a basic confusion between the terms circular and cyclic that is to be found in the literature. What should we do about this? - Not sure, suggestions welcome. Bill Cherowitzo (talk) 21:29, 8 September 2015 (UTC)

A good starting-point is to look on Google Books or Google Scholar, and see whether there is any overwhelming similarity of usage; unfortunately I'm not mathematically competent enough to understand most papers of that kind. Equinox (talk) 02:24, 9 September 2015 (UTC)

Fitzpatrick uses the term to denote a shift of two elements. See p. 18 of "Maxwell's equations and the principles of electromagnetism" — Preceding unsigned comment added by 192.249.3.208 (talk) 14:56, 8 November 2019 (UTC)

Identity permutation is allowed for 1-element sets?

Read literally, the current definition in the article never allows the identity permutation. However, a careful reading of the literature seems to allow the identity permutation only for sets of size 1.

For example, Knuth fascicle 2b (p. 35), defines a "cyclic permutation" of $\{1,\ldots ,n\}$ as "those $a_{1},\ldots ,a_{n}$ whose cycle representation consists of a single $n$-cycle". Note that this allows the trivial permutation iff n=1.

Anomalistic recently edited the page to say that there should be "at most one" nontrivial cycle, but I reverted this as potentially too broad — the references I could find clearly seem to require a nontrivial cycle for $n>1$.

I have to say that I found most of the texts I could find to be frustratingly vague on this point. Knuth was by far the best (unsurprisingly), but also corresponds to the more restrictive meaning of "cyclic permutation" in which no fixed points are allowed (except for n=1). Is there a clearer reference? — Steven G. Johnson (talk) 22:12, 9 July 2023 (UTC)

The definition given here is circular, as in involves cycles which are defined as subsets on which the restriction of the permutation is cyclic. I will fix this in the article. D.Lazard (talk) 08:57, 10 July 2023 (UTC)

Thank you both for your concern about the accuracy of this definition. It is now clear that all cited authors allow the permutation (1) as cyclic. However, the header and definition sections now disagree for larger sizes, with the header allowing (2 1)(3) and the definitions section stating that "some authors enlarge the definition" to allow it.

Header: "In mathematics, and in particular in group theory, 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. If S has k elements, the cycle is called a k-cycle [uncited, but supported by]" (equivalent to, but more formal than "at most one nontrivial cycle")

Definition section: "A permutation $\sigma$ of a set X is a cyclic permutation, if no nonempty proper subset S of X is left (globally) fixed by the permutation (that is $\sigma (S)=S$). ... Some authors enlarge the definition of a cyclic permutation to permutations whose all but one cycles have only one element."

This disagreement is reflective of the disagreement of the two cited sources on the matter; I propose that this article recognize this ambiguity in both the header and definitions sections lest it represent a single definition as canonical without the sources to back up that preeminence. Anomalistic (talk) 12:13, 10 July 2023 (UTC)

I reviewed several works, 4 of which contained unambiguous definitions of the term "Cyclic permutations". Two were equivalent to

A) A cyclic permutation is a permutation consisting of a single cycle.

and two were equivalent to

B) A cyclic permutation is a permutation with at most one nontrivial cycle.

To avoid ambiguity here are some examples listed as "Permutation | is it cyclic according to A | is it cyclic according to B"

() | yes | yes

(1) | yes | yes

(1 2) | yes | yes

(1)(2) | no | yes

(1)(3 2) | no | yes

(2 1)(4 3) | no | no

Here are the relevant works and quotations

Supporting A

"95. [21] Discuss how to generate all _cyclic permutations_ of {1,...,n}, namely those a_1...a_n whose cycle representation consists f a single n-cycle"

(Donald E. Knuth. (2002), The are to Computer Programming Pre-Fascicle 2B. p. 35)

"A cyclic permutation is a permutation whose successive application would take each object of the permuted set successively through the positions of all the other objects

DEFINITION: A permutation of the form

( x π(x) π^2(x) ... π^{p-2}(x) π^{p-1}(x) )

( π(x) π^2(x) π^3(x) ... π^{p-1}(x) x )

is said to be cyclic permutation of period p."

(Gross, Jonathan L. (2008), Combinatorial Methods with Computer Applications, Chapman & Hall/CRC, p. 29, ISBN 978-1-58488-743-0)

Supporting B

"More precisely, the permutation y is cyclic with the cycle (or k-cycle) (i_1 i_2 ... i_k) (a list of distinct integers) if y(i_r) = i_{r+1} for r = 1, 2, ..., k-1 and v(i_k) = i_1 but y(j) = j for all other j. When there is no likelihood of confusion, a cyclic permutation is called a cycle." (emphasis original)

(Bogart, Kenneth P. (2000), Introductory Combinatorics (3rd ed.), Harcourt, Brace, Jovanovich, p. 554, ISBN 0-12-110830-9)

"A permutation on a set S is a one-to-one mapping of S onto itself. In this context, the elements of S are called objects.

A permutation π of a finite set S is cyclic if there is a sub collection of objects that can be arranged in a cycle (a1 a2 ... an) so that each object aj is mapped by π onto the next object in the cycle and every object of S not in this cycle is fixed by π, that is, mapped to itself."

(Kenneth H Rosen et al. Handbook of Discrete and Combinatorial Mathematics (2000) p. 153)

From same source:

"[Augustin-LouisCauchy] also introduced the current notation (a1 a2 ... an) to denote the cyclic permutation on the letters a1, a2, ... , an." (p. 17)

"Every permutation has a cycle decomposition." (154)

"The cycle decomposition of a permutation into a product of disjoint cyclic permutations is unique up to the order of the factors." (154)

I agree with @Stevenj that we should use definition A (or a different wording of it) as the primary definition and also acknowledge that there is not consensus on a single definition. Anomalistic (talk) 16:35, 12 July 2023 (UTC)

The article was recently edited to claim the following definition:

A permutation of a set X is a cyclic permutation, if no nonempty proper subset S of X is left (globally) fixed by the permutation

which seems to be equivalent to a derangement, and also excludes the case of n=1!

My sense of the literature is that the most common definition of "cyclic permutation" is that every element of the set lies within the *same* orbit/cycle. (This definition allows n=1.) e.g. this definition is used by Knuth and by the literature on randomly sampling cyclic permutations (most commonly by Sattolo's algorithm, e.g. see this review). By this definition, there are (n-1)! cyclic permutations of n elements. This definition is arguably also the simplest, least controversial, and easiest to understand as distinct from a derangement.

So my recommendation is to *start* with this narrow definition. Then, if the references support it, we can *also* mention that some authors use a more general definition.

— Steven G. Johnson (talk) 17:08, 10 July 2023 (UTC)

Yes, I wholeheartedly support the definition that "cyclic permutation" means that every element of the set lies within the same orbit, or anything exactly equivalent to that. Especially with an infinite set X, we have to be careful that the orbit of x ∈ X under a permutation σ is all elements {τ(x) | τ ∈ G} where G is the smallest subgroup (of all permutation of X) that contains σ. —Quantling (talk | contribs) 18:47, 12 July 2023 (UTC)

Contradicting my earlier post that a "cycle" should be a permutation of a non-empty subset of X rather than a permutation of all of X, I'd like to start with what seems the simplest to me: a cycle is a permutation of X with exactly one non-trivial orbit, where a non-trivial orbit is one that has two or more elements of X. As such, the identity permutation is not a cycle, even if |X| = 1. However, the identity permutation is the empty product of cycles; and generally every permutation can be represented (up to rearrangements) uniquely as the product of cycles. (So, the identity permutation is not a cycle for much the same reason as 1 is not a prime number. Inclusion would make cyclic decomposition (or prime factorization) not unique.) —Quantling (talk | contribs) 18:58, 12 July 2023 (UTC)

References

Also note the article on circular shifts. These are permutations in which all elements are in the same orbit -- one of our definitions of cyclic permutation here -- plus a criterion based upon the elements labels, which is essentially that there must be some k for which i → i + k mod n. As we clarify the various definitions of cyclic permutation, I think it would be good to mention that circular shifts are not the same as any of them. —Quantling (talk | contribs) 18:50, 10 July 2023 (UTC)

which seems to be equivalent to a derangement No: the permutation (12)(34) is a derangement but it fixes the nonempty proper set {1, 2}. I think that there is no universally agreed answer to the question "is the identity permutation on a set of size larger than 1 considered a cyclic permutation (i.e., a 1-cycle)?" I am not convinced by D.Lazard's bold edits. --JBL (talk) 20:18, 10 July 2023 (UTC)

All this discussion is based on a mistake of the article, which asserts that a cycle is the same thing as a circular permutation. I have tagged the article as {{confusing}}, with "In common terminology, a cycle is not exactly the same as a circular permutation: a circular permutation is a permutation that has exactly one non trivial cycle in its cycle decomposition; a cycle is a permutation without nonempty fixed proper subset".

So, the identity is not a circular permutation, and the identity of a singleton is a cycle that is not a circular permutation.

As fixing this requires to rewrite the whole article, I have also tagged it with {{cleanup rewrite}}, a template that does not allows to display a "reason=" parameter. D.Lazard (talk) 20:13, 10 July 2023 (UTC)

There is a set vs. subset distinction going on here, yes? Any permutation of a set X has a cycle decomposition. If the cycle decomposition has exactly one "cycle" that contains all of X then the permutation is a "cyclic permutation". In particular, "cyclic permutation" applies to an entire set X, but each "cycle" of an arbitrary permutation is a cyclic permutation of S for some S ⊆ X. —Quantling (talk | contribs) 20:34, 10 July 2023 (UTC)

There is certainly (among other issues) the question of a subset versus the whole set, but it is not true that people (e.g., mathematicians in the relevant fields) are consistent in distinguishing between the two cases via any linguistic pattern, including the one you suggest. (In this respect the situation is unlike the use of "complete graph" versus "clique" in graph theory.) --JBL (talk) 00:20, 11 July 2023 (UTC)

This terminology question is more subtle than it may seem. A typical example is the permutation (1 3)(2)(4): it is a circular permutation for some authors; if the numbers represent the edges of a square, this permutation is the symmetry with respect to a diagonal, which is never considered, in geometry, as a cyclic permutation. Here is a terminology that seems compatible with all sources:

Given a permutation s of a set X, then

• a cycle (set) of s is the orbit of a single element or, equivalently a minimal nonempty subset that is left fixed by s;
• a cycle (permutation) of s is a permutation that equals s on a cycle (set) S, and is the identity outside.
• depending on the context and authors, a cyclic permutation is a permutation that is either
  • a cycle;
  • a permutation that has exactly one nontrivial cycle, in which case the identity is not a cyclic permutation;
  • a permutation that has at most one nontrivial cycle, in which case the identity is a circular permutation;
  • possibly, for some authors, a cyclic permutation is not the same as a circular permutation.

D.Lazard (talk) 11:29, 11 July 2023 (UTC)

You left off what seems to be one of the most common definitions in the literature: a permutation which has exactly one cycle, in which case (1) is a cyclic permutation. (I think it would be useful here to survey the exact wording in as many reliable sources as we can find, and make a list of how they use the term.) — Steven G. Johnson (talk) 12:12, 11 July 2023 (UTC)

Okay, so there is no single way that universally accepted. The article should pick something and use that. And there should be a section indicating some common alternatives to that which was picked. My preference for the pick is along the lines of

1. A permutation is a function that is a one-to-one correspondence from a set to itself.
2. A cyclic permutation is a permutation such that for any restriction to a non-empty proper subset of the domain, the resulting restricted function is not a permutation of the subset. (In particular, the image of the subset fails to be exactly the subset.)
3. The restriction of a permutation to a non-empty (but possibly improper) subset is a cycle if that restriction is a cyclic permutation of the subset. (Note that cycle is not merely a subset; the defining properties include the cyclic permutation of that subset.)

—Quantling (talk | contribs) 16:25, 11 July 2023 (UTC)

With these definitions the cycle decomposition would not be a composition of functions (domain and range do not agree).

As far as I know, the only term for which there is no consensus is the article title. This is taken into account in the above suggested terminology. D.Lazard (talk) 16:58, 11 July 2023 (UTC)

Right, my pick would be that a cycle is a function that is defined only on the subset and thus, generally, a permutation is not the function composition of the cycles of its cycle decomposition. While I like my pick for other reasons, admittedly this makes the definition of cycle decomposition more complicated. One might say, "if a cycle's domain is extended from its subset S to the entire set X by mapping each element of X−S to itself then the original permutation is the function composition of the cycles' extended functions.

If we include the points of X−S in a cycle's domain then things get fuzzy for me. For example for the permutation (1) (2) (3, 4) (in cycle notation), the cycle for (1) and the cycle for (2) are the exact same permutation of X = {1, 2, 3, 4}. —Quantling (talk | contribs) 17:19, 11 July 2023 (UTC)

The first possible definition of a circular permutation ("a cycle") must be read as "a permutation that has exactly one cycle". However, in the above list, an item is lacking:

• a permutation is a cycle if it is a cycle of itself, or, equivalently, has only one cycle.

These three meanings of "a cycle" are compatible, even if some authors do not clearly distinguish them. I doubt that other meanings are commonly used.

Also, if a cycle (set) of a permutation is a singleton set (a fixed point of the permutation), the corresponding cycle (permutation) is the identity. So, for a set with 4 elements, the permutation (2 3 1 4) may be written (2 3 4)(1), if the emphasis is given on cycles as subsets, or (2 3 4) if the emphasis if given on cycles as permutations. D.Lazard (talk) 16:39, 11 July 2023 (UTC)

Do you have a reference for this claim? "a circular permutation is a permutation that has exactly one non trivial cycle in its cycle decomposition; a cycle is a permutation without nonempty fixed proper subset" Anomalistic (talk) 16:22, 12 July 2023 (UTC)

I found a reference which states that it is acceptable to refer to cyclic permutations as cycles when there is not risk of confusion and have changed many uses in the article where I did perceive a risk of confusion. Consequently, I removed the tags. Feel free to fixup any confusing spots that I missed. Anomalistic (talk) 15:31, 15 July 2023 (UTC)

In terms of orbits

The above section is getting pretty hard to follow, so I'm starting a new section. Summarizing what I and others have written above, I propose that we define the terms in terms of orbits.

• A cyclic permutation of a set X is a permutation of X for which every element of X is in the same orbit. (In particular, there are (n−1)! cyclic permutations of a set X with |X| = n. Furthermore, the identity permutation is a cyclic permutation only when |X| = 1.)
• A cycle of a set X is a permutation of X that has exactly one non-trivial orbit, where a non-trivial orbit is an orbit with size at least 2. (In particular, the identity permutation is never a cycle, which is good because adding it to any cycle decomposition for a permutation would give a distinct cycle decomposition for that permutation.)
• A cycle decomposition is a representation of a permutation as the product of disjoint cycles. Cycles are disjoint if the elements in their non-trivial orbits are disjoint. (In particular, the cycle decomposition of the identity permutation is the (empty) product of zero cycles. Furthermore, a cycle decomposition is unique up to rearrangement of the disjoint cycles.)
• I know that circular shift hasn't gotten much attention in the discussion here. Perhaps we could leave it out. Alternatively, those of you with access to relevant publications might give a summary of what is out there in the literature. Possibilities include:

1. A circular shift of an ordered set X = (x₀, ... x_n−1) is a permutation of X of the form x_j → x_{j+k mod n} for some k ∈ {0, ..., n−1}. (In particular, it is a cyclic permutation only when k and n are relatively prime.)
2. A circular shift of a set X is a permutation of X that is some integer power of a cyclic permutation. (In particular, the identity permutation for any X with |X| ≥ 1 is a circular shift because it is the power 0 of any cyclic permutation. Furthermore, every orbit of a circular shift is of the same size (at least when |X| is finite).)

• What is a circular permutation, if anything?

—Quantling (talk | contribs) 19:31, 12 July 2023 (UTC)