Permutace a symetrické grupy

Definice

Máme-li konečně velkou množinu \(M\), potom permutace této množiny je jakákoli bijektivní funkce \(\pi: M \to M\). Bijektivní znamená, že každému prvku z první množiny je přiřazen právě jeden „další“ prvek z druhě množiny (v tomto případě té samé) a naopak každý prvek z druhé množiny je přiřazen právě jednomu „předchozímu“ prvku z první množiny. Jako množina \(M\) se často bere prvních několik kladných celých čísel.

Zápisy

Uveďme si jako příklad permutaci \(\pi\) na množině \(M = \{1,2,3,4,5,6\}\) definovanou následujícím předpisem:

\[\pi(1)=4\\\pi(2)=6\\\pi(3)=2\\\pi(4)=1\\\pi(5)=5\\\pi(6)=3\]

Tento zápis je poněkud zdlouhavý, proto existují hned tři různé jednodušší zápisy:

1. Dvouřádkový zápis. Do jednoho řádku se zapíšou prvky \(M\) a do druhého prvky, které jsou jim přiřazeny. V našem případě \(\pi = \begin{pmatrix}1&2&3&4&5&6\\4&6&2&1&5&3\end{pmatrix}\).
2. Jednořádkový zápis. Pokud jde o uspořádanou množinu, první řádek dvouřádkového zápisu zapsaný ve správném pořadí je možné vynechat. V našem případě \(\pi = \begin{pmatrix}4&6&2&1&5&3\end{pmatrix}\).
3. Cyklický zápis. Ten se vytvoří tak, že začneme od libovolého prvku \(x\) množiny \(M\) a budeme postupně zapisovat \(x, \pi(x), \pi(\pi(x)), \ldots\). Jakmile se dostaname k počátečnímu prvku, tento seznam uzavřeme do závorek. Pokud jsou v množině nějaké prvky, které jsme ještě nezapsali, jeden z nich si vybereme a provedeme opět to samé. Opakujeme, až žádný prvek nezbyde. V našem případě \(\pi = (1,4)(2,6,3)(5)\). Části obsahující pouze jedno číslo (pro nějž platí \(\pi(x) = x\)) je možné vynechat, tedy \(\pi = (1,4)(2,6,3)\).

Cykly a transpozice

Permutace, která má v cyklickém zápisu pouze jednu část ohraničenou závorkami (vynecháme-li jednoprvkové části), se nazývá cyklus.

Platí pro ni, že pokud vybereme nějaký prvek \(x\), pro který \(\pi(x) \neq x\), potom opakovanou aplikací \(\pi\) postupně projdeme všechny takové prvky. Délka cyklu je počet takovýchto prvků.

Příkladem cyklu je permutace \(\pi = (6,2,3) = \begin{pmatrix}1&2&3&4&5&6\\1&3&6&4&5&2\end{pmatrix}\). Platí \(\pi(6) = 2, \pi(2) = 3, \pi(3) = 6\) a pro ostatní \(x\) je \(\pi(x) = x\).

Cyklus délky \(2\) se označuje jako transpozice.

Jde o permutaci, která přehodí dva prvky a všechny ostatní ponechá. Např. u množiny \(M\) z předchozího příkladu by \(\pi = (3,5) = \begin{pmatrix}1&2&3&4&5&6\\1&2&5&4&3&6\end{pmatrix}\) byla transpozice.

Dva cykly jsou nezávislé, pokud nemají žádný společný prvek. Např. \((2,4,5)\) a \((1,6)\) je dvojice nezávislých cyklů.

Skládání permutací

Jelikož permutace je určitý druh funkce, skládání permutací funguje stejně jako skládání funkcí. To máme vysvětleno ve vlastním článku, společně s důkazem, že jde o asociativní operaci.

Ukážeme si konkrétní příklad. Mějme \(\pi = \begin{pmatrix}1&2&3&4\\1&4&2&3\end{pmatrix}\) a \(\sigma = \begin{pmatrix}1&2&3&4\\2&4&3&1\end{pmatrix}\). Pokud si vybereme např. prvek \(1\) a chceme zjistit \((\pi \circ \sigma)(1)\), musíme nejprve zjistit \(\sigma(1)\), což je \(2\). Výsledkem je pak \(\pi(2)\), což je \(4\). Určeme nyní, co dělá složená permutace se všemi prvky:

\[(\pi \circ \sigma)(1) = \pi(\sigma(1)) = \pi(2) = 4 \\(\pi \circ \sigma)(2) = \pi(\sigma(2)) = \pi(4) = 3 \\(\pi \circ \sigma)(3) = \pi(\sigma(3)) = \pi(3) = 2 \\(\pi \circ \sigma)(4) = \pi(\sigma(4)) = \pi(1) = 1 \\\pi \circ \sigma = \begin{pmatrix}1&2&3&4\\4&3&2&1\end{pmatrix} \\\]

Všimněme si, že složením permutací vznikla opět permutace. Pojďme si ukázat, že to tak platí vždy.

Věta: Jsou-li \(\pi\) a \(\sigma\) permutace na množině \(M\), potom \(\pi \circ \sigma\) je také permutace.

Důkaz: Vezměme si nějaký prvek \(x \in M\). Podle definice permutace je \(\sigma(x) \in M\) a tedy také \((\pi \circ \sigma)(x) = \pi(\sigma(x)) \in M\). Tím je dokázáno, že skládáním vznikne skutečně funkce \(M \to M\) a nyní zbývá ještě dokázat, že je bijektivní. Vezměme dva různé prvky \(x,y \in M\). Podle definice permutace jsou \(\sigma(x)\) a \(\sigma(y)\) také dva různé prvky \(M\), a tedy i \(\pi(\sigma(x))\) a \(\pi(\sigma(y))\). Z toho plyne, že každý prvek \(M\) je funkcí \(\pi \circ \sigma\) přiřazen nejvýše jednomu prvku \(M\). Kdyby však nějaký nebyl přiřazen žádnému, potom by podle holubníkového principu musel néjaký jiný být přiřazen alespoň dvěma. Funkce \(\pi \circ \sigma\) je tedy bijektivní a jde o permutaci.

Permutace identity

Permutace identity \(\mathbb{I}\) je permutace, která každému prvku přiřadí stejný prvek, tedy \(\mathbb{I} = \begin{pmatrix} a_1 & a_2 & \ldots & a_n \\ a_1 & a_2 & \ldots & a_n \end{pmatrix}\).

Každá permutace, která má v cyklickém zápisu pouze cykly délky \(1\), je identita, neboť tyto cykly prvky nijak nepřehazují. Pro každou permutaci \(\pi\) platí, že \(\pi \circ \mathbb{I} = \mathbb{I} \circ \pi\), neboť \(\pi(\mathbb{I}(x)) = \pi(x)\) a \(\mathbb{I}(\pi(x)) = \pi(x)\).

Konkrétním příkladem identity je \(\begin{pmatrix}1&2&3&4&5&6\\1&2&3&4&5&6\end{pmatrix}\).

Inverzní permutace

Máme-li permutaci \(\pi = \begin{pmatrix} a_1 & a_2 & \ldots & a_n \\ b_1 & b_2 & \ldots & b_n \end{pmatrix}\), definujme její inverzní permutaci jako \(\pi^{-1} = \begin{pmatrix} b_1 & b_2 & \ldots & b_n \\ a_1 & a_2 & \ldots & a_n \end{pmatrix}\).

Pro tuto permutaci platí \(\pi^{-1} \circ \pi = \pi \circ \pi^{-1} = \mathbb{I}\), což je možné vidět ze skutečnosti, že každému \(a\) je permutací \(\pi\) přiřazeno nějaké \(b\), kterému následně \(\pi^{-1}\) přiřadí opět \(a\) — a naopak.

Jaká by byla inverze k permutaci \(\begin{pmatrix}1&2&3&4\\2&4&3&1\end{pmatrix}\)? Stačí přehodit řádky, tedy \(\begin{pmatrix}2&4&3&1\\1&2&3&4\end{pmatrix}\). Pro přehlednost můžeme následně seřadit sloupce: \(\begin{pmatrix}1&2&3&4\\4&1&3&2\end{pmatrix}\).

Stejně snadné je nalezení inverze, pokud máme cyklický zápis. Stačí jednoduše obrátit pořadí prvků ve všech cyklech. Např. inverze k \((4.2.6.7)(3,5,1)\) by byla \((7,6,2,4)(1,5,3)\).

Symetrické grupy

Zopakujme si, co už jsme si dokázali o skládání permutací: jde o asociativní operaci, která má prvek identity, množina permutací je na ní uzavřena a každá permutace má inverzi. Čtenáři, který si přečetl náš článek o grupách, je v tuto chvíli jistě zřejmé, že toto přesně odpovídá definici grupy. Máme-li konečnou množinu \(M\) o \(n\) prvcích, potom algebraickou strukturu tvořenou permutacemi na této množině a jejich skládáním nazýváme symetrická grupa stupně \(n\) a značíme \(\mathbb S_n\). Občas se pod tímto pojmem rozumí i grupy definované bijektivními funkcemi na nekonečných množinách, ale ty v tomto článku zanedbáme a budeme se soustředit na konečné symetrické grupy.

Povšimněme si, že symetrické grupy obecně nejsou komutativní. Pokud vezmeme např. \(\pi = \begin{pmatrix} 1&2&3 \\ 2&1&3\end{pmatrix}\) a \(\sigma = \begin{pmatrix} 1&2&3 \\ 1&3&2\end{pmatrix}\), potom \(\pi \circ \sigma = \begin{pmatrix} 1&2&3 \\ 2&3&1\end{pmatrix}\), ale \(\sigma \circ \pi = \begin{pmatrix} 1&2&3 \\ 3&1&2\end{pmatrix}\). Tím jsme tedy dokázali, že \(\mathbb S_3\) není komutativní. (Dokonce jde o nejmenší nekomutativní grupu, ovšem to tady dokazovat nebudeme.)

Rozklad na cykly a transpozice

Již jsme si ukázali tzv. cyklický zápis permutace, např. \((1,3)(2,5,4)\). Všimněme si, že vypadá, jako by šlo o jakýsi součin dvou cyklů. Ovšem toto není jen záležitost zápisu — ono totiž o součin dvou cyklů skutečně jde (přičemž součinem se rozumí grupová operace, což v případě permutací je skládání).

Obecně platí, že každá permutace se dá rozložit na součin několika nezávislých cyklů, a to přesně způbem, který byl již uveden při představení cyklického zápisu. Jelikož každý cyklus přemisťuje jiné prvky, nijak se vzájemně neovlivňují, což vysvětluje nejen to, proč jejich součinem vznikne původní permutace, ale také skutečnost, že skládání nezávislých cyklů je komutativní (na rozdíl od skládání obecně). Proto také můžeme cykly v cyklickém žapisu zapsat v libovolném pořadí.

S rozkládáním ovšem můžeme jít ješté dál. Dokažme si nyní, že každý cyklus, a tím pádem i každou permutaci, je možné rozložit na součin několika transpozic.^[1]

Věta: Pro cykly platí \(\pi = (x_1, x_2, x_3, \ldots, x_n) = (x_1, x_n) \circ \cdots \circ (x_1, x_3) \circ (x_1, x_2)\).

Konkrétně např. permutace \((7,3,4,1,6)\) by se dala rozložit jako \((7,6)(7,1)(7,4)(7,3)\)

Doplňme, že tento součin transpozic na rozdíl od součinu nezávislých cyklů není komutativní.

Inverze, parita a znaménko permutace

Inverze v permutaci \(\pi\) na uspořádané množině \(M\) je dvojice prvků \(x,y \in M\), pro které je \(x < y\), ale \(\pi(x) > \pi(y)\). Jinak řečeno, jde o dva prvky, jejichž vzájemné pořadí se po uplatnění permutace změní.

Pozor! Inverze v permutaci nijak nesouvisí s inverzní permutací. Podobnost výrazů je čistě náhodná.

Pojďme spočítat, kolik inverzí má permutace \( \begin{pmatrix}1&2&3&4&5&6&7\\1&2&3&6&5&4&7\end{pmatrix}\). Vidíme, že \(6\) je před \(5\), \(5\) je před \(4\) a \(6\) je před \(4\). Jinak je vše ve „správném“ pořadí, celkově tedy máme tři inverze.

Permutace, která má sudý počet inverzí, se označuje jako sudá. Permutace, kterš má lichý počet inverzí, se označuje jako lichá.

Permutace v předchozím příkladu měla tři inverze, jde tedy o lichou permutaci.

Definujme znaménko permutace \(\operatorname{sgn}(\pi)\) takto: znaménko sudé permutace je \(+1\) a znaménko liché permutace je \(-1\).

Všimněme si analogie s celými čísly, kde funkce \(n \mapsto (-1)^n\) vrací \(+1\) pro sudé \(n\) a \(-1\) pro liché \(n\).

Je zřejmé, že každá permutace je buď sudá, nebo lichá, ale ne obojí zároveň. Nyní si dokážeme důležitou větu o paritě permutací.

Věta: Součinem sudého počtu transpozic vznikne sudá permutace. Součinem lichého počtu transpozic vznikne lichá permutace.

Důkaz indukcí: Součin \(0\) transpozic je permutace identity, která nemá žádnou inverzi a je tedy sudá. Dokažme nyní, že pokud permutaci vynásobíme zleva transpozicí, změní se tím její parita. Pokud si permutaci představíme jako nějaké pořadí prvků, transpozice v tomto pořadí přehodí dva prvky \(x\) a \(y\). Tím se změní jejich pořadí. Pokud byly ve „správném“ pořadí, potom tímto vznikne jedna inverze, v opačném případě zanikne jedna inverze — ale každopádně se tím parita počtu inverzí změní. Mezi \(x\) a \(y\) však může být ještě dalších \(k\) prvků. Pro každý z těchto prvků se zméní jeho pořadí jak s \(x\), tak s \(y\), takže stejným způsobem dojde ke dvěma vznikům nebo zánikům inverze. To však paritu počtu inverzí neovlivní, jelikož se tyto výměny dají právě takto rozdělit do dvojic. Celkově se tedy parita musí změnit, což je přesně to, co jsme chtěli dokázat.

Permutace \(\begin{pmatrix}1&2&3&4&5&6&7\\1&2&3&6&5&4&7\end{pmatrix} = (6,4)\) se skládá z jedné transpozice, čímž se znovu potvrzuje, že je lichá.

Nyní si již uvažováním o rozkladu na transpozice lze snadno rozmyslet, že skládání permutací funguje co do parity stejně jako sčítání celých čísel: dvě sudé nebo dvě liché dají sudou, zatímco sudá s lichou nebo lichá se sudou dají lichou. To se dá jednoduše formulovat pomocí znamének: \(\operatorname{sgn}(\pi \circ \sigma) = \operatorname{sgn}(\pi) \cdot \operatorname{sgn}(\sigma)\).

Věta: Pro každé \(n \geq 2\) je v grupě \(\mathbb S_n\) stejný počet sudých a lichých permutací.

Důkaz: Vezměme libovolnou transpozici \(\tau\). Jelikož jde jen o přehození dvou prvků, které je po opětovném provedení vrátí do původního stavu, platí \(\tau = \tau^{-1}\). Definujme funkci \(f(\pi) = \tau \circ \pi\). Tato funkce je také inverzí sama sebe, jelikož \(f(f(\pi)) = \tau \circ \tau \circ \pi = \tau^{-1} \circ \tau \circ \pi = \pi\). Jelikož \(\tau\) je lichá permutace, funkce \(f\) změní znaménko permutace, kterou do ní vložíme. Z těchto dvou skutečností však plyne, že \(f\) je bijekce mezi množinou sudých a lichých permutací, a tyto množiny tedy musí mít stejnou velikost.

Zajímavostí na závěr je, že ve známé hře Patnáctka nelze polovinu pozic vyřešit — a to právě proto, že libovolná posloupnost tahů, po které zůstane volné stejné pole jako před ní, nemůže změnit paritu permutace čísel na desce. Jeden vychytralý člověk na to kdysi vyhlásil tučnou peněžní odměnu, čímž vyvolal naprostou mánii a mnoho lidí trávilo čas marnými pokusy o nalezení posloupnosti tahů, která by vedla k přehození dvou čísel. Matematika samozřejmě stála při jeho zádech a nikomu se to nepodařilo.