Tri otázky k permutáciám

[Dominika Harmanová]

1. V materiáloch pre cv.5 "Rád a parita permutácie" sa v riešení druhého príkladu hovorí "každý cyklus vieme rozložiť na súčin transpozícií, ktorých počet je o jedna menší ako dĺžka cyklu." Odkiaľ toto vieme?

2. V skriptách str.30 máme uvedené ako vyzerá rozklad permutácie (123) na transpozície, ale chýba mi informácia o tom, ako rozklad na transpozície urobiť. Tj - vo všeobecnosti - aký je mechanizmus rozkladu permutácie na transpozície? Ako získať transpozície?

3. Zaujímalo by ma, či poznáme nejaký efektívny spôsob, ako rozkladať grupu permutácií na triedy. Napr triedy rozkladu $G = (S_4, \circ)$ podľa
$H = \{id,\ (1234),\ (13)(24),\ (1432)\}$ som riešila nasledovne (viď nižie), ale tento spôsob sa mi veľmi nepáči, keďže je extrémne zdĺhavý a človek musí mechanicky prechádzať cez každú možnosť. A navyše, v tomto konkrétnom príklade, som postupovala prvok po prvku $S_4$ a náhodou prvých 5 prvkov mi rovno dalo celý rozklad. Vieme to urobiť lepšie?

Moje riešenie:

$S_4$ je množina všetkých štvorprvkových permutácií, tj pre danú štvoricu prvkov obsahuje 4.3.2.1=24 permutácií:
\begin{gather*}
S_4 = \{id,\ (34),\ (23),\ (234),\ (243),\ (24),\ (12),\ (12)(34),\ (123),\ (1234),\ (1243),\ (124),
\\ \hspace{1.8cm} (132),\ (1342),\ (13),\ (134),\ (13)(24),\ (1324),\ (1432),\ (142),\ (143),\ (14),\ (1423),\ (14)(23)\}
\end{gather*}

Skladanie narozdiel od násobenia nie je komutatívna operácia, a preto sa musíme pozrieť zvlášť na pravé aj ľavé triedy rozkladu.

Ľavé triedy:
$id \circ H = H = \{id,\ (1234),\ (13)(24),\ (1432)\}$
$(34) \circ H = \{(34),\ (34)(1234),\ (34)(13)(24),\ (34)(1432)\} = \{(34),\ (124),\ (1423),\ (132)\}$
$(23) \circ H = \{(23),\ (23)(1234),\ (23)(13)(24),\ (23)(1432)\} = \{(23),\ (134),\ (1243),\ (142)\}$
$(234) \circ H = \{(234),\ (234)(1234),\ (234)(13)(24),\ (234)(1432)\} = \{(234),\ (1324),\ (143),\ (12)\}$
$(243) \circ H = \{(243),\ (243)(1234),\ (243)(13)(24),\ (243)(1432)\} = \{(243),\ (14),\ (123),\ (1342)\}$
$(24) \circ H = \{(24),\ (24)(1234),\ (24)(13)(24),\ (24)(1432)\} = \{(24),\ (14)(23),\ (13),\ (12)(34)\}$


Týchto 5 tried je príkladom ľavého rozkladu G podľa H - triedy sú neprázdne, navzájom disjunktné a na zjednotení dávajú pôvodnú množinu prvkov grupy G.


Pravé triedy:
$H \circ id = H = \{id,\ (1234),\ (13)(24),\ (1432)\}$
$H \circ (34) = \{(34),\ (1234)(34),\ (13)(24)(34),\ (1432)(34)\} = \{(34),\ (123),\ (1324),\ (142)\}$
$H \circ (23) = \{(23),\ (1234)(23),\ (13)(24)(23),\ (1432)(23)\} = \{(23),\ (124),\ (1342),\ (143)\}$
$H \circ (234) = \{(234),\ (1234)(234),\ (13)(24)(234),\ (1432)(234)\} = \{(234),\ (1243),\ (132),\ (14)\}$
$H \circ (243) = \{(243),\ (1234)(243),\ (13)(24)(243),\ (1432)(243)\} = \{(243),\ (12),\ (134),\ (1423)\}$
$H \circ (24) = \{(24),\ (1234)(24),\ (13)(24)(24),\ (1432)(24)\} = \{(24),\ (12)(34),\ (13),\ (14)(23)\}$


Týchto 5 tried je príkladom pravého rozkladu G podľa H. Opäť platí, že triedy sú neprázdne, navzájom disjunktné a na zjednotení dávajú pôvodnú množinu prvkov grupy G.

[Ludovit_Balko]

1. V materiáloch pre cv.5 "Rád a parita permutácie" sa v riešení druhého príkladu hovorí "každý cyklus vieme rozložiť na súčin transpozícií, ktorých počet je o jedna menší ako dĺžka cyklu." Odkiaľ toto vieme?

2. V skriptách str.30 máme uvedené ako vyzerá rozklad permutácie (123) na transpozície, ale chýba mi informácia o tom, ako rozklad na transpozície urobiť. Tj - vo všeobecnosti - aký je mechanizmus rozkladu permutácie na transpozície? Ako získať transpozície?

Jedna z možností, ako rozložiť ľubovoľný cyklus $(a_1a_2\cdots a_n)$ na súčin transpozícií je
$$
(a_1a_2\cdots a_n)=(a_1a_n)(a_1a_{n-1})(a_1a_{n-2})\cdots(a_1a_{3})(a_1a_{2})
$$
a počet transpozícií v tomto rozklade je $n-1$. Vyššie uvedený rozkald je použitý v skriptách v dôkaze tvrdenia 2.5.17. na strane 30.

Zaujímalo by ma, či poznáme nejaký efektívny spôsob, ako rozkladať grupu permutácií na triedy.

Nejaký univerzálny spôsob asi nie je a pri odpovedi na otázku, ako presne vyzerajú všetky triedy rozkladu, sa ich (trochu nudnému) počítaniu nevyhnete. Čo môže ale pomôcť pri otázke, akým prvkom násobiť H, tak aby ste nepočítali zbytočne tú istú triedu rozkladu, je fakt, že získané množiny tvoria rozklad grupy. Takže ak spočítate jednu triedu tak viete, že získané prvky už nepoužijete na získanie ostatných tried. Napríklad vo Vašom príklade, keď ste zistili, že
$$
(34)\circ H=\{(34), (124), (1423), (132)\}
$$
tak automaticky viete že $$(34)\circ H=(124)\circ H=(1423)\circ H=(132)\circ H.$$