Jump to content

Talk:Cycle notation

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

What is the algorithmic complexity of decomposing a permutation into those cycles?

Seems O(n) to me: you start with the first element, compute the output of the permutation, and use that as input. If the output is the first element again, you start over with another unused element, the used elements are one cycle. Each element of the permutation will be used exactly once, and the cycles will be disjoint (this is the exact technique used to prove the theorem). I don't think it'd be possible to do in a better time.
You should sign your name. Zyszys (talk) 13:32, 1 January 2011 (UTC)[reply]

permutation as a group of cycles

[edit]

The Wikipedia page on orbits defines the orbit of an element of the set on which a group acts upon, but not of the group element itself. Can someone please clarify in what context is orbit being used here? Also, since one permutation is being concerned, then should any element not have only one orbit? Pratik.Mallya Talk! 06:39, 2 March 2011 (UTC)[reply]

The orbits of a single permutation are the same as the orbits of the cyclic group generated by that permutation. The orbits of (1,2,3)(4,5)(6)(7) = (1,2,3)(4,5) = [ 2, 3, 1, 5, 4, 6, 7 ] on {1,2,3,4,5,6,7} are {1,2,3}, {4,5}, {6}, and {7}. If you omit 1-cycles, then you must be explicit about the domain being acted on. JackSchmidt (talk) 15:20, 2 March 2011 (UTC)[reply]


Thanks for answering Jack! Perhaps we should include this definition in that of orbit? In most places, this is not mentioned, but I finally came across a book by Gerhard Michler which gave this definition.Pratik.Mallya Talk! 00:36, 3 March 2011 (UTC)[reply]
Do not agree. This usage and definition of the term orbit should not be included on the Wikipedia page defining orbit. It is unconventional and completely different from the common and proper usage of the term.
"orbits of the cyclic group generated by that permutation" is not clear.
(1) What is cyclic group? How is it generated? It may be that the intended meaning is the reverse. It is known that any permutation is generated by a product of cyclic permutations. The collection of cyclic permutations that generate a given permutation, however does not necessarily form a group. The phrase would then become "orbits of the collection of cyclic permutations which generate that permutation."
(2) The use of the term orbits in this phrase is circular in its use as a means of defining the word orbit. Also, it never describes how a cyclic group (presumed to mean not a group of, but a simple collection of cyclic permutations) is related to its orbits. Here, the use of the term orbit is probably intended to refer to the orbit for a cyclic permutation, which in turn is intended to mean the collection of elements listed in the denotation of the cyclic permutation when the permutation is denoted in cycle notation.
(3) The use of the term orbits here and in the article is at best obscure and certainly not conventional in the sense of popular usage. The mathematical structure of an orbit and how an orbit is generated by a group action are in no way similar to the structure and generation implied by the usage of the term here. This usage should not be promoted in general and it should not be repeated here as it only leads to confusion (despite the fact that at least one mathematics book, as cited above, has been published stipulating this usage). The term orbits as used in the article should be replaced with a descriptive phrase such as collections of cycle elements (referring to the elements used in the denotation of a cyclic permutation). — Preceding unsigned comment added by 66.194.2.9 (talk) 21:44, 30 December 2014 (UTC)[reply]
Jack was quite correct and the use of the term orbit in this article is quite standard and in agreement with the article orbit. Perhaps Jack's explanation should be fleshed out and given in this article. Given any element g of any group G, the cyclic group generated by g (usually denoted by <g>) is the subgroup consisting of e, g, g2, g3, etc. when the group is finite and written multiplicatively. If G is the permutation group S(n), then this subgroup acts naturally on the set {1,2,...,n}. Using Jack's example, g=(123)(45)(6)(7), we have g2 = (132)(4)(5)(6)(7), g3=(1)(2)(3)(45)(6)(7), g4=(123)(4)(5)(6)(7), g5=(132)(45)(6)(7) and g6=(1)(2)(3)(4)(5)(6)(7) = e. The orbit of 1 under this subgroup (<g>) is {1,2,3}, the orbit of 4 is {4,5}, the orbit of 6 is {6} and so on. Notice how the elements in an orbit are precisely the elements in a cycle of the original permutation g which is what the definition is trying to say. The author of the article probably thought that the concept of a cyclic group generated by an element would be understood by readers of this page. Bill Cherowitzo (talk) 23:52, 30 December 2014 (UTC)[reply]


This article omits motivation and barely has examples. At the very least, it should explain how group multiplication works for cycles. Moly 15:58, 23 October 2012 (UTC) — Preceding unsigned comment added by Moly (talkcontribs)