Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Cyclic permutation
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Definition == [[image:050712_perm_2.png|A cyclic permutation consisting of a single 8-cycle.|thumb]] There is not widespread consensus about the precise definition of a cyclic permutation. Some authors define a [[permutation]] {{mvar|Ο}} of a set {{mvar|X}} to be cyclic if "successive application would take each object of the permuted set successively through the positions of all the other objects",<ref name=":0" /> or, equivalently, if its representation in cycle notation consists of a single cycle.<ref name=":1" /> Others provide a more permissive definition which allows fixed points.<ref name=":2" /><ref name=":3" /> A nonempty subset {{mvar|S}} of {{mvar|X}} is a ''cycle'' of <math>\sigma</math> if the restriction of <math>\sigma</math> to {{mvar|S}} is a cyclic permutation of {{var|S}}. If {{mvar|X}} is [[finite set|finite]], its cycles are [[disjoint sets|disjoint]], and their [[set union|union]] is {{mvar|X}}. That is, they form a [[partition of a set|partition]], called the [[cycle decomposition (group theory)|cycle decomposition]] of <math>\sigma.</math> So, according to the more permissive definition, a permutation of {{mvar|X}} is cyclic if and only if {{mvar|X}} is its unique cycle. For example, the permutation, written in [[cycle notation]] and [[Permutation#Two-line notation|two-line notation]] (in two ways) as :<math>\begin{align} (1\ 4\ 6\ &8\ 3\ 7)(2)(5) \\ &= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 2 & 7 & 6 & 5 & 8 & 1 & 3 \end{pmatrix} \\ &= \begin{pmatrix} 1 & 4 & 6 & 8 & 3 & 7 & 2 & 5 \\ 4 & 6 & 8 & 3 & 7 & 1 & 2 & 5 \end{pmatrix} \end{align}</math> has one 6-cycle and two 1-cycles its cycle diagram is shown at right. Some authors consider this permutation cyclic while others do not. [[image:050712_perm_3.png|thumb|A permutation that is cyclic for the enlarged definition but not for the restricted one, with two fixed points (1-cycles) and a 6-cycle]]With the enlarged definition, there are cyclic permutations that do not consist of a single cycle. More formally, for the enlarged definition, a permutation <math>\sigma</math> of a set ''X'', viewed as a [[bijection|bijective function]] <math>\sigma:X\to X</math>, is called a cycle if the action on ''X'' of the subgroup generated by <math>\sigma</math> has at most one orbit with more than a single element.<ref>{{harvnb|Fraleigh|1993|loc=p. 103}}</ref> This notion is most commonly used when ''X'' is a finite set; then the largest orbit, ''S'', is also finite. Let <math>s_0</math> be any element of ''S'', and put <math>s_i=\sigma^i(s_0)</math> for any <math>i\in\mathbf{Z}</math>. If ''S'' is finite, there is a minimal number <math>k \geq 1</math> for which <math>s_k=s_0</math>. Then <math>S=\{ s_0, s_1, \ldots, s_{k-1}\}</math>, and <math>\sigma</math> is the permutation defined by :<math>\sigma(s_i) = s_{i+1}</math> for 0 β€ ''i'' < ''k'' and <math>\sigma(x)=x</math> for any element of <math>X\setminus S</math>. The elements not fixed by <math>\sigma</math> can be pictured as :<math>s_0\mapsto s_1\mapsto s_2\mapsto\cdots\mapsto s_{k-1}\mapsto s_k=s_0</math>. A cyclic permutation can be written using the compact [[cycle notation]] <math>\sigma = (s_0~s_1~\dots~s_{k-1})</math> (there are no commas between elements in this notation, to avoid confusion with a ''k''-[[tuple]]). The ''length'' of a cycle is the number of elements of its largest orbit. A cycle of length ''k'' is also called a ''k''-cycle. The orbit of a 1-cycle is called a ''fixed point'' of the permutation, but as a permutation every 1-cycle is the [[identity permutation]].<ref>{{harvnb|Rotman|2006|loc=p. 108}}</ref> When cycle notation is used, the 1-cycles are often omitted when no confusion will result.<ref>{{harvnb|Sagan|1991|loc=p. 2}}</ref>
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)