Cyklická permutace - Cyclic permutation

v matematika, a zejména v teorie skupin, a cyklická permutace (nebo cyklus) je permutace prvků některých soubor X který mapuje prvky některých podmnožina S z X cyklickým způsobem, zatímco opravují (tj. mapují k sobě) všechny ostatní prvky X. Li S má k prvků, cyklus se nazývá a k-cyklus. Cykly jsou často označovány seznamem jejich prvků uzavřeným v závorkách v pořadí, ve kterém jsou permutovány.

Například zadáno X = {1, 2, 3, 4}, permutace (1, 3, 2, 4), která posílá 1 až 3, 3 až 2, 2 až 4 a 4 až 1 (takže S = X) je 4-cyklus a permutace (1, 3, 2), která vysílá 1 až 3, 3 až 2, 2 až 1 a 4 až 4 (takže S = {1, 2, 3} a 4 je pevný prvek) je 3-cyklus. Na druhou stranu permutace, která vysílá 1 až 3, 3 až 1, 2 až 4 a 4 až 2, není cyklická permutace, protože samostatně permutuje páry {1, 3} a {2, 4}.

Sada S se nazývá obíhat cyklu. Každá permutace na konečně mnoha prvcích může být rozložena do cyklů na disjunktních drahách.

Cyklické části permutace jsou cykly, tedy druhý příklad se skládá ze 3-cyklu a 1-cyklu (nebo pevný bod) a třetí se skládá ze dvou 2 cyklů a je označen (1, 3) (2, 4).

Definice

Schéma cyklické permutace se dvěma pevnými body; 6 cyklů a dva 1 cykly.

A permutace se nazývá cyklická permutace kdyby a jen kdyby má jediný netriviální cyklus (cyklus délky> 1).^[1]

Například permutace napsaná v dvouřádkový (dvěma způsoby) a také cyklické notace,

{ displaystyle { 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 = p 1 (2) (5),}

je šest cyklů; jeho cyklický diagram je zobrazen vpravo.

Někteří autoři omezují definici pouze na ty permutace, které se skládají z jednoho netriviálního cyklu (to znamená, že nejsou povoleny žádné pevné body).^[2]

Cyklická permutace bez triviálních cyklů; 8-cyklus.

Například permutace

{ displaystyle { begin {pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 4 & 5 & 7 & 6 & 8 & 2 & 1 & 3 end {pmatrix}} = { begin {pmatrix} 1 & 4 & 6 & 2 & 5 & 8 & 3 & 7 4 & 6 & 2 & 5 & 8 & 3 & 7 & 1 end = p 1 3 7)}

je cyklická permutace podle této přísnější definice, zatímco předchozí příklad tomu tak není.

Více formálně, obměna ${ displaystyle sigma}$ sady X, zobrazeno jako a bijektivní funkce ${ displaystyle sigma: X až X}$ , se nazývá cyklus, pokud je akce zapnutá X podskupiny generované ${ displaystyle sigma}$ má nanejvýš jednu oběžnou dráhu s více než jedním prvkem.^[3] Tento pojem se nejčastěji používá, když X je konečná množina; pak samozřejmě největší oběžnou dráhu, S, je také konečný. Nechat ${ displaystyle s_ {0}}$ být jakýmkoli prvkem Sa dal ${ displaystyle s_ {i} = sigma ^ {i} (s_ {0})}$ pro všechny ${ displaystyle i in mathbf {Z}}$ . Li S je konečný, je jich minimální počet ${ displaystyle k geq 1}$ pro který ${ displaystyle s_ {k} = s_ {0}}$ . Pak ${ displaystyle S = {s_ {0}, s_ {1}, ldots, s_ {k-1} }}$ , a ${ displaystyle sigma}$ je permutace definovaná

{ displaystyle sigma (s_ {i}) = s_ {i + 1}}

pro 0 ≤ i < k

a ${ displaystyle sigma (x) = x}$ pro jakýkoli prvek ${ displaystyle X setminus S}$ . Prvky, které nebyly opraveny ${ displaystyle sigma}$ lze zobrazit jako

{ displaystyle s_ {0} mapsto s_ {1} mapsto s_ {2} mapsto cdots mapsto s_ {k-1} mapsto s_ {k} = s_ {0}}

.

Cyklus lze napsat pomocí kompaktu cyklická notace ${ displaystyle sigma = (s_ {0} ~ s_ {1} ~ tečky ~ s_ {k-1})}$ (mezi prvky této notace nejsou čárky, aby nedošlo k záměně s a k-n-tice ). The délka cyklu je počet prvků na jeho největší oběžné dráze. Cyklus délky k se také nazývá a k-cyklus.

Dráha 1 cyklu se nazývá a pevný bod permutace, ale jako permutace je každý 1 cyklus permutace identity.^[4] Když se použije notace cyklu, 1-cykly jsou často potlačeny, pokud nedojde k záměně.^[5]

Základní vlastnosti

Jeden ze základních výsledků na symetrické skupiny je, že jakákoli permutace může být vyjádřena jako produkt disjunktní cykly (přesněji: cykly s disjunktními drahami); takové cykly dojíždějí navzájem a výraz permutace je jedinečný až do pořadí cyklů.^[A] The multiset délky cyklů v tomto výrazu ( typ cyklu ) je tedy jednoznačně určen permutací a podpisem i třída konjugace permutace v symetrické skupině je jím určena.^[6]

Počet k-cykly v symetrické skupině S_n je uveden pro ${ displaystyle 1 leq k leq n}$ následujícími ekvivalentními vzorci

{ displaystyle { binom {n} {k}} (k-1)! = { frac {n (n-1) cdots (n-k + 1)} {k}} = { frac {n !} {(nk)! k}}}

A k-cyklus má podpis (−1)^k − 1.

The inverzní cyklu ${ displaystyle sigma = (s_ {0} ~ s_ {1} ~ tečky ~ s_ {k-1})}$ je dáno obrácením pořadí položek: ${ displaystyle sigma ^ {- 1} = (s_ {k-1} ~ tečky ~ s_ {1} ~ s_ {0})}$ . Zejména proto, že ${ displaystyle (a ~ b) = (b ~ a)}$ , každý dva cykly jsou vlastní inverzní. Jelikož disjunktní cykly dojíždějí, je inverze produktu disjunktních cyklů výsledkem obrácení každého z cyklů zvlášť.

Transpozice

Matice z

{ displaystyle pi}

Cyklus pouze se dvěma prvky se nazývá a transpozice. Například permutace ${ displaystyle pi = { začátek {pmatrix} 1 & 2 & 3 & 4 1 & 4 & 3 & 2 end {pmatrix}}}$ který zamění 2 a 4.

Vlastnosti

Jakoukoli permutaci lze vyjádřit jako složení (produkt) transpozic - formálně jsou generátory pro skupina.^[7] Ve skutečnosti, když je sada, která je permutována, ${1, 2, ..., n}$ pro celé číslo $n$ , pak lze jakoukoli permutaci vyjádřit jako produkt sousední transpozice ${ displaystyle (1 ~ 2), (2 ~ 3), (3 ~ 4),}$ a tak dále. To následuje, protože libovolnou transpozici lze vyjádřit jako produkt sousedních transpozic. Konkrétně lze vyjádřit transpozici ${ displaystyle (k ~~ l)}$ kde ${ displaystyle k$ pohybem $k$ na $l$ jeden krok po druhém, pak se hýbat $l$ zpět kam $k$ byl, který zaměňuje tyto dvě a neprovádí žádné další změny:

{ displaystyle (k ~~ l) = (k ~~ k + 1) cdot (k + 1 ~~ k + 2) cdots (l-1 ~~ l) cdot (l-2 ~~ l- 1) cdots (k ~~ k + 1).}

Rozklad permutace na produkt transpozic se získá například zapsáním permutace jako produktu disjunktních cyklů a následným iterativním rozdělením každého z cyklů délky 3 a déle na produkt transpozice a cyklus délky jedna méně:

{ displaystyle (a ~ b ~ c ~ d ~ ldots ~ y ~ z) = (a ~ b) cdot (b ~ c ~ d ~ ldots ~ y ~ z).}

To znamená, že počáteční požadavek je přesunout ${ displaystyle a}$ na ${ displaystyle b,}$ ${ displaystyle b}$ na ${ displaystyle c,}$ ${ displaystyle y}$ na ${ displaystyle z,}$ a nakonec ${ displaystyle z}$ na ${ displaystyle a.}$ Místo toho je možné válec udržovat ${ displaystyle a}$ kde to je provedením správného faktoru jako prvního (jako obvykle v notaci operátora a podle konvence v článku o Permutace ). To se přesunulo ${ displaystyle z}$ do polohy ${ displaystyle b,}$ takže po první permutaci prvky ${ displaystyle a}$ a ${ displaystyle z}$ ještě nejsou na svých konečných pozicích. Provedení ${ displaystyle (a ~ b),}$ poté provedeny, pak adresy ${ displaystyle z}$ indexem ${ displaystyle b}$ vyměnit to, co původně bylo ${ displaystyle a}$ a ${ displaystyle z.}$

Ve skutečnosti symetrická skupina je Skupina coxeterů, což znamená, že je generován prvky řádu 2 (sousední transpozice) a všechny vztahy mají určitou formu.

Jeden z hlavních výsledků na symetrických skupinách uvádí, že buď všechny rozklady dané permutace na transpozice mají sudý počet transpozic, nebo všechny mají lichý počet transpozic.^[8] To umožňuje parita permutace být a dobře definované pojem.

Viz také

Třídění cyklů - třídicí algoritmus, který je založen na myšlence, že permutaci, která má být tříděna, lze zapracovat do cyklů, které lze jednotlivě otáčet, aby se získal seřazený výsledek
Cykly a pevné body
Cyklická permutace celého čísla
Cyklická notace
Kruhová permutace v proteinech

Poznámky

^ Všimněte si, že notace cyklu není jedinečná: každá k-cyklus může být napsán sám k různými způsoby, v závislosti na výběru ${ displaystyle s_ {0}}$ na jeho oběžné dráze.

Reference

^ Bogart, Kenneth P. (1990), Úvodní kombinatorika (2. vyd.), Harcourt, Brace, Jovanovich, str. 486, ISBN 0-15-541576-X
^ Gross, Jonathan L. (2008), Kombinatorické metody s počítačovými aplikacemi, Chapman & Hall / CRC, s. 29, ISBN 978-1-58488-743-0
^ Fraleigh 1993, str. 103
^ Rotman 2006, str. 108
^ Sagan 1991, str. 2
^ Rotman 2006, str. 117, 121
^ Rotman 2006, str. 118, Prop. 2.35
^ Rotman 2006, str. 122

Zdroje

Anderson, Marlow a Feil, Todd (2005), První kurz v abstraktní algebře, Chapman & Hall / CRC; 2. vydání. ISBN 1-58488-515-7.
Fraleigh, John (1993), První kurz abstraktní algebry (5. vydání), Addison Wesley, ISBN 978-0-201-53467-2
Rotman, Joseph J. (2006), První kurz v abstraktní algebře s aplikacemi (3. vyd.), Prentice-Hall, ISBN 978-0-13-186267-8
Sagan, Bruce E. (1991), Symetrická skupina / reprezentace, kombinatorické algoritmy a symetrické funkce, Wadsworth & Brooks / Cole, ISBN 978-0-534-15540-7

externí odkazy

Tento článek včlení materiál od cyklu dále PlanetMath, který je licencován pod Creative Commons Attribution / Share-Alike License.

[6] Všimněte si, že notace cyklu není jedinečná: každá k-cyklus může být napsán sám k různými způsoby, v závislosti na výběru ${ displaystyle s_ {0}}$ na jeho oběžné dráze.

[1] Bogart, Kenneth P. (1990), Úvodní kombinatorika (2. vyd.), Harcourt, Brace, Jovanovich, str. 486, ISBN 0-15-541576-X

[2] Gross, Jonathan L. (2008), Kombinatorické metody s počítačovými aplikacemi, Chapman & Hall / CRC, s. 29, ISBN 978-1-58488-743-0

[3] Fraleigh 1993, str. 103

[4] Rotman 2006, str. 108

[5] Sagan 1991, str. 2

[7] Rotman 2006, str. 117, 121

[8] Rotman 2006, str. 118, Prop. 2.35

[9] Rotman 2006, str. 122

[1]

[2]

[3]

[4]

[5]

[A]

[6]

[7]

[8]