Grupy — symetrie, permutacje i twierdzenie Lagrange’a od podstaw
Grupy od podstaw: symetrie kwadratu, aksjomaty, rząd elementu, podgrupy i twierdzenie Lagrange’a, znak permutacji, izomorfizm, lemat Burnside’a, 12 przykładów.
Grupa w algebrze to zbiór z jednym działaniem, które zachowuje się „porządnie”: jest łączne, ma element neutralny i da się je odwrócić. Ta krótka definicja opisuje naraz symetrie figur, przetasowania kart, dodawanie reszt z dzielenia, mnożenie macierzy i obroty płaszczyzny. Po tej lekcji będziesz umiał sprawdzić, czy dany zbiór z działaniem jest grupą, policzyć rząd elementu, wypisać podgrupy i warstwy, zastosować twierdzenie Lagrange’a (także do reszt z dzielenia wielkich potęg), rozłożyć permutację na cykle i wyznaczyć jej znak, rozpoznać grupy izomorficzne oraz policzyć kolorowania „z dokładnością do obrotu” lematem Burnside’a. To materiał pierwszego roku studiów matematycznych i informatycznych, a zarazem narzędzie olimpijskie: zadania o resztach, parzystości przestawień i zliczaniu naszyjników rozwiązuje się nim w kilku linijkach.
Symetrie kwadratu i trójkąta — skąd się bierze grupa
Symetria figury to ruch płaszczyzny, po którym figura pokrywa się sama ze sobą. Kwadrat ma ich dokładnie osiem: cztery obroty wokół środka (o \(0^\circ, 90^\circ, 180^\circ, 270^\circ\)) i cztery symetrie osiowe. Oznaczmy:
- \(e\) — ruch „nic nie rób” (obrót o \(0^\circ\)),
- \(r\) — obrót o \(90^\circ\) przeciwnie do ruchu wskazówek zegara, \(r^2\) i \(r^3\) — obroty o \(180^\circ\) i \(270^\circ\),
- \(s_v\), \(s_h\) — symetrie względem osi pionowej i poziomej,
- \(d_1\), \(d_2\) — symetrie względem przekątnych: \(d_1\) przez wierzchołki 1 i 3, \(d_2\) przez wierzchołki 2 i 4.
Numery 1, 2, 3, 4 to miejsca wierzchołków (kolejno przeciwnie do ruchu wskazówek zegara, od prawego górnego). Każdą symetrię zapiszemy jako permutację: \(i \mapsto j\) znaczy „wierzchołek z miejsca \(i\) ląduje na miejscu \(j\)”. Obrót \(r\) przenosi 1 na 2, 2 na 3, 3 na 4 i 4 na 1, co krótko zapisujemy jako cykl \((1\;2\;3\;4)\). Dalej \(s_v = (1\;2)(3\;4)\), \(s_h = (1\;4)(2\;3)\), \(d_1 = (2\;4)\), \(d_2 = (1\;3)\) — dokładny sens tych nawiasów wyjaśnimy w części o permutacjach.
Dwie symetrie można złożyć: wykonać jedną, a potem drugą. Wynik znowu jest symetrią kwadratu — zbiór ośmiu ruchów jest „zamknięty” na składanie. To pierwsza obserwacja, z której wyrośnie definicja grupy.
Przykład 1. Obrót i symetria nie są przemienne
Oblicz \(r s_v\) i \(s_v r\).
\(r s_v\) (najpierw \(s_v\), potem \(r\)). Śledzimy każdy wierzchołek: \(1 \to 2 \to 3\), \(2 \to 1 \to 2\), \(3 \to 4 \to 1\), \(4 \to 3 \to 4\). Miejsca 2 i 4 stoją, 1 i 3 się zamieniły — to \((1\;3) = d_2\).
\(s_v r\) (najpierw \(r\), potem \(s_v\)): \(1 \to 2 \to 1\), \(2 \to 3 \to 4\), \(3 \to 4 \to 3\), \(4 \to 1 \to 2\). Wynik \((2\;4) = d_1\).
Wniosek: \(r s_v \neq s_v r\). Kolejność ma znaczenie, a grupa symetrii kwadratu nie jest przemienna. To samo widać we współrzędnych: \(s_v(x, y) = (-x, y)\), \(r(x, y) = (-y, x)\), więc \(r(s_v(x, y)) = (-y, -x)\) — symetria względem prostej \(y = -x\). Ogólnie złożenie obrotu z symetrią osiową jest symetrią osiową, a złożenie dwóch symetrii osiowych — obrotem o podwojony kąt między osiami (np. \(s_h s_v = r^2\)).
Tabelka Cayleya grupy symetrii trójkąta
Trójkąt równoboczny ma 6 symetrii: obroty \(e, r, r^2\) (o \(0^\circ, 120^\circ, 240^\circ\)) oraz trzy symetrie osiowe. Niech \(s\) będzie symetrią względem osi przez wierzchołek 1, czyli \(s = (2\;3)\). Pozostałe dwie to \(rs = (1\;2)\) i \(r^2s = (1\;3)\) — każda zostawia w miejscu jeden wierzchołek (odpowiednio 3 i 2). Wszystkie iloczyny zbiera tabelka Cayleya: w wierszu \(a\) i kolumnie \(b\) stoi \(ab\).
Dwie rzeczy rzucają się w oczy. Po pierwsze, w każdym wierszu i w każdej kolumnie każdy element występuje dokładnie raz — tabelka jest „sudoku” (kwadratem łacińskim). Po drugie, tabelka nie jest symetryczna względem przekątnej: \(sr = r^2s\), a \(rs\) to coś innego.
Grupa — definicja i aksjomaty
Przemienności nie ma wśród aksjomatów — symetrie kwadratu tworzą grupę, choć \(r s_v \neq s_v r\). W grupach przemiennych często piszemy działanie jako \(+\), element neutralny jako \(0\), a odwrotny jako \(-a\).
Przykłady grup
- \((\mathbb{Z}, +)\) — liczby całkowite z dodawaniem; neutralne 0, odwrotny do \(a\) to \(-a\). Podobnie \((\mathbb{Q}, +)\), \((\mathbb{R}, +)\), \((\mathbb{C}, +)\).
- \((\mathbb{Z}_n, +)\) — reszty \(0, 1, \ldots, n-1\) z dodawaniem modulo \(n\). Na przykład w \(\mathbb{Z}_{12}\) mamy \(8 + 7 = 3\) (godzina 8 plus 7 godzin to godzina 3).
- \((\mathbb{R} \setminus \{0\}, \cdot)\) i \((\mathbb{Q} \setminus \{0\}, \cdot)\) — mnożenie liczb niezerowych; odwrotny do \(a\) to \(\frac{1}{a}\). Także liczby dodatnie z mnożeniem.
- \(\mathbb{Z}_p^{*} = \{1, 2, \ldots, p-1\}\) z mnożeniem modulo liczba pierwsza \(p\). Ogólniej \(\mathbb{Z}_n^{*}\) — reszty względnie pierwsze z \(n\).
- \(GL_2(\mathbb{R})\) — macierze \(2 \times 2\) o niezerowym wyznaczniku z mnożeniem macierzy. Łączność mnożenia i istnienie macierzy odwrotnej to dokładnie aksjomaty 1 i 3.
- Obroty płaszczyzny wokół ustalonego punktu, obroty o wielokrotności \(\frac{360^\circ}{n}\), symetrie dowolnej figury.
- Permutacje zbioru \(\{1, \ldots, n\}\) ze składaniem — grupa \(S_n\), omówiona niżej.
Co nie jest grupą
- \((\mathbb{N}, +)\): nie ma liczby naturalnej odwrotnej do 3, bo \(-3 \notin \mathbb{N}\).
- \((\mathbb{Z}, \cdot)\): 2 nie ma odwrotności, bo \(\frac{1}{2} \notin \mathbb{Z}\).
- \((\mathbb{R}, \cdot)\): zero nie ma odwrotności. Dlatego zero się wyrzuca.
- \((\mathbb{Z}, -)\): odejmowanie nie jest łączne, bo \((5 - 3) - 1 = 1\), a \(5 - (3 - 1) = 3\).
- Liczby nieparzyste z dodawaniem: brak domkniętości, \(1 + 3 = 4\).
- Wszystkie macierze \(2 \times 2\) z mnożeniem: macierz o wyznaczniku 0 nie ma odwrotnej.
Pierwsze własności
Z samych aksjomatów wynika kilka faktów, których używa się bez przerwy.
- Element neutralny jest jeden: jeśli \(e\) i \(e'\) są neutralne, to \(e = ee' = e'\).
- Element odwrotny jest jeden: jeśli \(b\) i \(c\) są odwrotne do \(a\), to \(b = b(ac) = (ba)c = c\).
- Prawo skracania: z \(ax = ay\) wynika \(x = y\) (pomnóż z lewej przez \(a^{-1}\)). Stąd „sudoku” w tabelce Cayleya: w wierszu \(a\) nie może dwa razy stać ten sam wynik.
- Odwrotność iloczynu: \((ab)^{-1} = b^{-1}a^{-1}\) — kolejność się odwraca, bo \(ab \cdot b^{-1}a^{-1} = a(bb^{-1})a^{-1} = e\). W grupie kwadratu: \((r s_v)^{-1} = s_v r^3 = d_2\), a „naiwne” \(r^3 s_v\) daje \(d_1\).
Przykład 2. Czy to jest grupa?
a) \(\mathbb{Z}_5 \setminus \{0\} = \{1, 2, 3, 4\}\) z mnożeniem modulo 5. Iloczyn dwóch liczb niepodzielnych przez 5 nie dzieli się przez 5, więc wynik nie jest zerem — jest domkniętość. Łączność dziedziczymy po zwykłym mnożeniu, neutralne to 1. Odwrotności: \(1 \cdot 1 = 1\), \(2 \cdot 3 = 6 \equiv 1\), \(4 \cdot 4 = 16 \equiv 1\). Wszystko jest — to grupa.
b) \(\mathbb{Z}_6 \setminus \{0\}\) z mnożeniem modulo 6. Tu \(2 \cdot 3 = 6 \equiv 0\), a zera w zbiorze nie ma — brak domkniętości, to nie jest grupa. Różnica bierze się stąd, że 5 jest pierwsze, a 6 nie.
c) Macierze \(A = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}\) i \(B = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}\) mają wyznacznik 1, więc należą do \(GL_2(\mathbb{R})\). Ale \(AB = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}\), a \(BA = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}\) — grupa macierzy odwracalnych nie jest przemienna.
Rząd elementu i grupy cykliczne
Rząd grupy \(|G|\) to liczba jej elementów: grupa symetrii kwadratu ma rząd 8, trójkąta — 6, a \(\mathbb{Z}\) jest nieskończona. Rząd elementu \(g\) to najmniejsze \(k \geq 1\), dla którego \(g^k = e\) (w zapisie addytywnym: \(kg = 0\)); oznaczamy go \(\operatorname{ord}(g)\). Jeśli takiego \(k\) nie ma, rząd jest nieskończony — tak jest dla każdej niezerowej liczby w \((\mathbb{Z}, +)\).
W grupie kwadratu: \(\operatorname{ord}(e) = 1\), \(\operatorname{ord}(r) = \operatorname{ord}(r^3) = 4\), \(\operatorname{ord}(r^2) = 2\), a każda z czterech symetrii osiowych ma rząd 2 (dwa odbicia lustrzane wracają do punktu wyjścia).
Gdy \(\operatorname{ord}(g) = k\), potęgi \(g, g^2, \ldots\) powtarzają się co \(k\) kroków, więc \(g^m = e\) dokładnie wtedy, gdy \(k \mid m\). Ten fakt przyda się wiele razy.
Grupy cykliczne i generatory
Grupa jest cykliczna, jeśli wszystkie jej elementy są potęgami jednego elementu \(g\), zwanego generatorem: \(G = \langle g \rangle = \{e, g, g^2, \ldots\}\). Wzorcowe przykłady to \((\mathbb{Z}, +)\) z generatorem 1 i \((\mathbb{Z}_n, +)\), także z generatorem 1. Obroty kwadratu \(\{e, r, r^2, r^3\}\) tworzą grupę cykliczną rzędu 4, a pierwiastki z jedności stopnia \(n\), czyli liczby zespolone \(\cos\frac{2k\pi}{n} + i\sin\frac{2k\pi}{n}\), tworzą grupę cykliczną rzędu \(n\) z mnożeniem. Rząd generatora równa się rzędowi grupy.
Przykład 3. Rzędy elementów: reszty modulo 12 i modulo 7
a) W \(\mathbb{Z}_{12}\) rząd elementu \(k\) to najmniejsze \(m \geq 1\), dla którego \(12 \mid km\). Przykładowo dla \(k = 8\): \(8, 16 \equiv 4, 24 \equiv 0\), więc rząd to 3. Ogólnie
(tu wraca NWD i rozkład na czynniki pierwsze). Daje to: 0 ma rząd 1; 6 — rząd 2; 4 i 8 — rząd 3; 3 i 9 — rząd 4; 2 i 10 — rząd 6; 1, 5, 7, 11 — rząd 12. Generatory \(\mathbb{Z}_{12}\) to więc dokładnie liczby względnie pierwsze z 12: \(1, 5, 7, 11\). Zauważ, że każdy rząd (1, 2, 3, 4, 6, 12) dzieli 12 — za chwilę zobaczymy dlaczego.
b) W \(\mathbb{Z}_7^{*}\) (mnożenie modulo 7) liczymy kolejne potęgi. Dla 2: \(2, 4, 8 \equiv 1\) — rząd 3, więc 2 nie jest generatorem. Dla 3: \(3, 9 \equiv 2, 6, 18 \equiv 4, 12 \equiv 5, 15 \equiv 1\) — pojawiły się wszystkie reszty, rząd wynosi 6 i \(\mathbb{Z}_7^{*} = \langle 3 \rangle\) jest cykliczna. W teorii liczb taki generator nazywa się pierwiastkiem pierwotnym.
Podgrupy, warstwy i twierdzenie Lagrange’a
Podgrupa \(H \leq G\) to podzbiór, który z tym samym działaniem sam jest grupą: zawiera \(e\), iloczyn dowolnych dwóch swoich elementów i odwrotność każdego swojego elementu. W grupie skończonej wystarczy sprawdzić domkniętość na działanie — odwrotność przyjdzie sama, bo \(g^{-1} = g^{k-1}\) dla \(k = \operatorname{ord}(g)\).
Każdy element \(g\) wyznacza podgrupę cykliczną \(\langle g \rangle\), która ma dokładnie \(\operatorname{ord}(g)\) elementów. W \(\mathbb{Z}_{12}\) np. \(\langle 4 \rangle = \{0, 4, 8\}\), a \(\langle 3 \rangle = \{0, 3, 6, 9\}\).
Warstwy
Dla podgrupy \(H\) i elementu \(g\) warstwa lewostronna to zbiór \(gH = \{gh : h \in H\}\) (w zapisie addytywnym \(g + H\)). Dwie własności robią całą robotę:
- każda warstwa ma tyle elementów co \(H\), bo z prawa skracania \(gh_1 = gh_2\) daje \(h_1 = h_2\);
- dwie warstwy są albo równe, albo rozłączne: jeśli \(x \in g_1H \cap g_2H\), to \(g_1H = xH = g_2H\).
Warstwy dzielą więc grupę na równe, rozłączne kawałki. W \(\mathbb{Z}_{12}\) podgrupa \(H = \{0, 4, 8\}\) ma cztery warstwy: \(H\), \(1 + H = \{1, 5, 9\}\), \(2 + H = \{2, 6, 10\}\), \(3 + H = \{3, 7, 11\}\).
Twierdzenie Lagrange’a
Dowód to dokładnie rysunek powyżej: \(G\) rozpada się na \([G : H]\) rozłącznych warstw, każda ma \(|H|\) elementów. Stąd w grupie rzędu 8 podgrupy mogą mieć tylko rzędy 1, 2, 4 lub 8, a w grupie rzędu 12 nie ma podgrupy rzędu 5 ani 8.
Przykład 4. Warstwy lewe i prawe w grupie trójkąta
Wyznacz warstwy lewo- i prawostronne podgrupy \(H = \{e, s\}\) w grupie symetrii trójkąta.
Lewe warstwy \(gH\) odczytujemy z wierszy tabelki Cayleya: \(eH = \{e, s\}\), \(rH = \{r, rs\}\), \(r^2H = \{r^2, r^2s\}\). Trzy warstwy po 2 elementy: \(6 = 3 \cdot 2\), zgodnie z Lagrange’em.
Prawe warstwy \(Hg = \{g, sg\}\) bierzemy z kolumn: \(He = \{e, s\}\), \(Hr = \{r, sr\} = \{r, r^2s\}\), \(Hr^2 = \{r^2, sr^2\} = \{r^2, rs\}\). To inny podział grupy: \(rH \neq Hr\). W grupach nieprzemiennych lewe i prawe warstwy mogą się różnić; dla grup przemiennych zawsze się pokrywają.
Wnioski: rząd elementu, grupy rzędu pierwszego, małe twierdzenie Fermata
Twierdzenie Lagrange’a zastosowane do podgrupy \(\langle g \rangle\) daje serię mocnych wniosków.
- Rząd elementu dzieli rząd grupy: \(\operatorname{ord}(g) \mid |G|\), bo \(|\langle g \rangle| = \operatorname{ord}(g)\).
- \(g^{|G|} = e\) dla każdego \(g\), bo \(|G|\) jest wielokrotnością rzędu \(g\).
- Grupa rzędu pierwszego \(p\) jest cykliczna: weź \(g \neq e\); jego rząd jest większy od 1 i dzieli \(p\), więc wynosi \(p\) i \(\langle g \rangle = G\).
- Małe twierdzenie Fermata: dla pierwszego \(p\) i \(p \nmid a\) mamy \(a^{p-1} \equiv 1 \pmod p\) — to wniosek 2 dla grupy \(\mathbb{Z}_p^{*}\) rzędu \(p - 1\).
- Twierdzenie Eulera: dla \(\mathrm{NWD}(a, n) = 1\) mamy \(a^{\varphi(n)} \equiv 1 \pmod n\), gdzie \(\varphi(n) = |\mathbb{Z}_n^{*}|\) to liczba reszt względnie pierwszych z \(n\).
Twierdzenie nie działa w drugą stronę: z tego, że \(d \mid |G|\), nie wynika istnienie podgrupy rzędu \(d\). Najmniejszy kontrprzykład to grupa \(A_4\) rzędu 12, która nie ma podgrupy rzędu 6 (dowód w przykładzie 8).
Przykład 5. Reszty z dzielenia wielkich potęg
a) Reszta z dzielenia \(3^{100}\) przez 7. Z Fermata \(3^6 \equiv 1 \pmod 7\), a \(100 = 6 \cdot 16 + 4\), więc
b) Dwie ostatnie cyfry \(7^{2026}\), czyli reszta modulo 100. Euler daje \(7^{40} \equiv 1\), bo \(\varphi(100) = 40\), ale jeszcze szybciej: \(7^4 = 2401 \equiv 1 \pmod{100}\). Rząd 7 w \(\mathbb{Z}_{100}^{*}\) wynosi 4 — i zgodnie z Lagrange’em dzieli 40. Ponieważ \(2026 = 4 \cdot 506 + 2\), mamy \(7^{2026} \equiv 7^2 = 49\). Dwie ostatnie cyfry to 49.
Morał: wykładnik zawsze redukujemy modulo rząd elementu (albo modulo jego wielokrotność, np. \(p - 1\) czy \(\varphi(n)\)).
Przykład 6. Wszystkie podgrupy grupy symetrii kwadratu
Z Lagrange’a podgrupy mają rząd 1, 2, 4 lub 8. Rzędu 1 i 8 są dwie trywialne: \(\{e\}\) i cała grupa. Podgrupa rzędu 2 to \(\{e, g\}\) z \(g\) rzędu 2 — takich elementów jest pięć (\(r^2, s_v, s_h, d_1, d_2\)), więc i podgrup pięć. Rzędu 4 są trzy:
- \(\{e, r, r^2, r^3\}\) — cykliczna, generowana przez \(r\);
- \(\{e, r^2, s_v, s_h\}\) i \(\{e, r^2, d_1, d_2\}\) — w obu każdy element różny od \(e\) ma rząd 2.
Razem 10 podgrup (komputerowe sprawdzenie wszystkich 255 niepustych podzbiorów daje tę samą liczbę).
Permutacje — zapis cykliczny, rząd i znak permutacji
Permutacja zbioru \(\{1, \ldots, n\}\) to wzajemnie jednoznaczne przekształcenie tego zbioru w siebie. Wszystkie permutacje ze składaniem tworzą grupę symetryczną \(S_n\) rzędu \(n!\) (liczbę ustawień znasz z kombinatoryki — permutacje bez powtórzeń). Zapis dwuwierszowy podaje obraz każdego elementu:
Wygodniejszy jest zapis cykliczny. Startujemy od 1 i idziemy za strzałkami: \(1 \to 5 \to 2 \to 7 \to 1\) — to cykl \((1\;5\;2\;7)\). Pierwsza nieużyta liczba to 3: \(3 \to 9 \to 6 \to 3\), cykl \((3\;9\;6)\). Zostają 4 i 8, które się zamieniają: \((4\;8)\). Zatem \(\sigma = (1\;5\;2\;7)(3\;9\;6)(4\;8)\). Cykle są rozłączne, więc ich kolejność w zapisie nie ma znaczenia; punkty stałe zwykle się pomija. Cykl długości 2 to transpozycja.
Przykład 7. Rząd, odwrotność i potęga permutacji
Dla \(\sigma = (1\;5\;2\;7)(3\;9\;6)(4\;8)\):
- rząd: \(\mathrm{NWW}(4, 3, 2) = 12\); w szczególności \(\sigma^4\) i \(\sigma^6\) nie są identycznością;
- odwrotność: każdy cykl czytamy wstecz, \(\sigma^{-1} = (1\;7\;2\;5)(3\;6\;9)(4\;8)\);
- \(\sigma^6\): cykl długości 3 i transpozycja znikają (bo \(3 \mid 6\) i \(2 \mid 6\)), a 4-cykl w szóstej potędze to jego kwadrat, który przeskakuje co drugi element: \(\sigma^6 = (1\;2)(5\;7)\).
Składanie permutacji
Składamy od prawej do lewej, śledząc każdy element przez kolejne czynniki. Dla \(\sigma = (1\;2\;3)\) i \(\tau = (1\;2)\) w \(S_3\): w \(\sigma\tau\) najpierw działa \(\tau\), więc \(1 \to 2 \to 3\), \(2 \to 1 \to 2\), \(3 \to 3 \to 1\), czyli \(\sigma\tau = (1\;3)\). Natomiast \(\tau\sigma = (2\;3)\). Grupa \(S_n\) dla \(n \geq 3\) nie jest przemienna.
Znak permutacji, permutacje parzyste i grupa alternująca
Każdy cykl rozkłada się na transpozycje: \((a_1\;a_2\;\ldots\;a_k) = (a_1\;a_k)\cdots(a_1\;a_3)(a_1\;a_2)\), np. \((1\;2\;3) = (1\;3)(1\;2)\). Cykl długości \(k\) to więc \(k - 1\) transpozycji. Rozkład nie jest jednoznaczny, ale parzystość liczby transpozycji już tak — to kluczowe twierdzenie o permutacjach. Definiujemy znak:
gdzie \(c\) to liczba cykli razem z punktami stałymi. Znak jest multiplikatywny: \(\operatorname{sgn}(\sigma\tau) = \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)\). Permutacje o znaku \(+1\) to parzyste; tworzą podgrupę \(A_n\) (grupę alternującą) rzędu \(\frac{n!}{2}\) — dokładnie połowę, bo złożenie z \((1\;2)\) zamienia permutacje parzyste na nieparzyste i odwrotnie.
Dla naszej \(\sigma\): \(n = 9\), \(c = 3\), więc \(\operatorname{sgn}(\sigma) = (-1)^6 = 1\) — permutacja parzysta (\(3 + 2 + 1 = 6\) transpozycji). Uwaga na pułapkę: cykl o długości nieparzystej jest permutacją parzystą.
Klasyczne zastosowanie to układanka „piętnastka”: każdy ruch to transpozycja pustego pola z sąsiednim. Pokolorujmy pola jak szachownicę: każdy ruch zmienia kolor pola z dziurą, więc gdy dziura wraca na swoje miejsce, wykonano parzystą liczbę ruchów, a permutacja szesnastu pól jest parzysta. Układu z zamienionymi tylko klockami 14 i 15 (jedna transpozycja) nie da się więc osiągnąć.
Przykład 8. Permutacje czterech elementów według typu cykli
Rozbijamy 24 permutacje zbioru \(\{1, 2, 3, 4\}\) według długości cykli:
- identyczność: 1 element, rząd 1, parzysta;
- transpozycje \((a\;b)\): \(\binom{4}{2} = 6\), rząd 2, nieparzyste;
- 3-cykle \((a\;b\;c)\): 4 wybory pominiętego elementu razy 2 kierunki \(= 8\), rząd 3, parzyste;
- 4-cykle: \(3! = 6\) (ustalamy start w 1, resztę ustawiamy dowolnie), rząd 4, nieparzyste;
- pary transpozycji \((a\;b)(c\;d)\): 3, rząd 2, parzyste.
Kontrola: \(1 + 6 + 8 + 6 + 3 = 24\). Elementów rzędu 2 jest 9, rzędu 3 — 8, rzędu 4 — 6; wszystkie rzędy dzielą 24. Parzyste: \(1 + 8 + 3 = 12\) — to grupa \(A_4\). I to ona łamie odwrotność twierdzenia Lagrange’a: nie ma podgrupy rzędu 6. Podgrupa \(H\) rzędu 6 miałaby indeks 2, czyli tylko dwie warstwy: \(H\) i \(gH\) dla dowolnego \(g \notin H\). Gdyby \(g^2\) leżało w \(gH\), to \(g^2 = gh\), czyli \(g = h \in H\) — sprzeczność. Zatem kwadrat każdego elementu leży w \(H\). Każdy z ośmiu 3-cykli jest kwadratem (\(c = (c^2)^2\), bo \(c^3 = e\)), więc \(H\) zawierałaby \(e\) i osiem 3-cykli — co najmniej 9 elementów, a nie 6. Największy rząd w \(S_5\) to 6, osiągany przez \((1\;2)(3\;4\;5)\), choć żaden pojedynczy cykl w \(S_5\) nie ma długości 6.
Permutacje są uniwersalne. Twierdzenie Cayleya mówi, że każda grupa jest „grupą permutacji”: mnożenie z lewej przez \(g\) przestawia elementy grupy (to wiersz \(g\) tabelki Cayleya), więc grupa rzędu \(n\) siedzi wewnątrz \(S_n\).
Grupa diedralna i izomorfizm grup
Grupę symetrii \(n\)-kąta foremnego oznaczamy \(D_n\) (grupa diedralna). Ma \(2n\) elementów: \(n\) obrotów \(e, r, \ldots, r^{n-1}\) o wielokrotności \(\frac{360^\circ}{n}\) i \(n\) symetrii osiowych \(s, rs, \ldots, r^{n-1}s\). Całą tabelkę wyznaczają trzy reguły:
Ostatnia oznacza, że przenosząc \(s\) przez obrót, zmieniamy kierunek obrotu: \(sr = r^{-1}s\). Dla trójkąta daje to \(sr = r^2s\), jak w tabelce. Dla nieparzystego \(n\) każda oś przechodzi przez wierzchołek i środek przeciwległego boku; dla parzystego \(n\) połowa osi łączy przeciwległe wierzchołki, a połowa — środki przeciwległych boków. Grupa kwadratu to \(D_4\), grupa trójkąta — \(D_3\).
Izomorfizm grup
Dwie grupy są izomorficzne (\(G \cong H\)), jeśli istnieje bijekcja \(\varphi \colon G \to H\) zachowująca działanie: \(\varphi(ab) = \varphi(a)\varphi(b)\). Mówiąc po ludzku: to ta sama tabelka Cayleya z przemianowanymi elementami. Izomorfizm zachowuje rząd grupy, przemienność i liczbę elementów każdego rzędu — to najszybsze narzędzia do wykazania, że grupy nie są izomorficzne.
Na przykład \(D_3 \cong S_3\): każda z 6 permutacji wierzchołków trójkąta jest symetrią. Ale \(D_4 \not\cong S_4\) (8 elementów zamiast 24): transpozycja \((1\;2)\) zamieniłaby sąsiednie wierzchołki, zostawiając 3 i 4, a wtedy bok 2–3 przeszedłby na przekątną 1–3.
Porównajmy dwie grupy rzędu 4: cykliczną \(\mathbb{Z}_4\) i grupę czwórkową Kleina \(V = \{e, a, b, c\}\) (po lewej dodawanie modulo 4, po prawej \(V\)):
Na przekątnej tabelki \(V\) stoi same \(e\): każdy element ma rząd 2 (poza \(e\)). W \(\mathbb{Z}_4\) element 1 ma rząd 4. Izomorfizm zachowuje rzędy, więc \(\mathbb{Z}_4 \not\cong V\). Grupę Kleina już znasz: to podgrupa \(\{e, r^2, s_v, s_h\}\) grupy kwadratu (\(s_v s_h = r^2\)). Każda grupa rzędu 4 jest izomorficzna z \(\mathbb{Z}_4\) albo z \(V\), a każda grupa rzędu 6 — z \(\mathbb{Z}_6\) albo z \(S_3\). Stąd najmniejsza grupa nieprzemienna ma 6 elementów.
Przykład 9. Które grupy rzędu 4 są cykliczne?
a) \(\mathbb{Z}_5^{*} = \{1, 2, 3, 4\}\): potęgi dwójki modulo 5 to \(2, 4, 3, 1\) — rząd 4, więc grupa jest cykliczna, a \(\varphi(k) = 2^k \bmod 5\) jest izomorfizmem \(\mathbb{Z}_4 \to \mathbb{Z}_5^{*}\) (dodawanie wykładników odpowiada mnożeniu potęg).
b) \(\mathbb{Z}_8^{*} = \{1, 3, 5, 7\}\): \(3^2 = 9 \equiv 1\), \(5^2 = 25 \equiv 1\), \(7^2 = 49 \equiv 1\). Każdy element poza 1 ma rząd 2, więc to grupa Kleina (\(3 \cdot 5 = 15 \equiv 7\) — iloczyn dwóch „liter” daje trzecią, jak \(ab = c\)).
c) Obroty kwadratu \(\{e, r, r^2, r^3\}\) — cykliczna; symetrie prostokąta niebędącego kwadratem \(\{e, r^2, s_v, s_h\}\) — Klein. Dwie grupy tego samego rzędu, różna struktura.
Lemat Burnside’a — zliczanie z dokładnością do symetrii
Ile jest różnych naszyjników z 6 koralików czarnych i białych? Ciągów zero-jedynkowych długości 6 jest \(2^6 = 64\), ale naszyjnik obrócony to ten sam naszyjnik. Nie wystarczy podzielić przez 6, bo niektóre układy mają mniej niż 6 różnych obrotów (np. wszystkie białe ma tylko jeden). Właściwe narzędzie to działanie grupy na zbiorze.
Orbity i stabilizatory
Grupa \(G\) działa na zbiorze \(X\), gdy każdy \(g \in G\) przestawia elementy \(X\) zgodnie z działaniem grupy (np. obroty przestawiają kolorowania). Orbita \(\mathrm{Orb}(x)\) to wszystko, do czego da się przejść z \(x\) — w zadaniach to jeden „obiekt z dokładnością do symetrii”. Stabilizator \(\mathrm{Stab}(x)\) to podgrupa elementów, które \(x\) nie ruszają.
To Lagrange w przebraniu: elementy jednej warstwy \(g\,\mathrm{Stab}(x)\) przenoszą \(x\) w to samo miejsce. Przykłady: wierzchołek 1 kwadratu może trafić na 4 miejsca, a stabilizator to \(\{e, d_1\}\), stąd \(|D_4| = 4 \cdot 2 = 8\). Obrotów sześcianu jest \(6 \cdot 4 = 24\) (wybrana ściana na 6 miejsc, potem 4 obroty wokół niej). Słowo ANANAS: grupa \(S_6\) przestawia litery, stabilizator to przestawienia trzech A i dwóch N między sobą, \(3! \cdot 2! = 12\), więc różnych słów jest \(\frac{720}{12} = 60\).
Lemat Cauchy’ego–Frobeniusa–Burnside’a
Dowód to podwójne zliczanie par \((g, x)\) z \(gx = x\). Licząc po \(g\), dostajemy \(\sum |\mathrm{Fix}(g)|\). Licząc po \(x\), dostajemy \(\sum |\mathrm{Stab}(x)| = \sum \frac{|G|}{|\mathrm{Orb}(x)|}\) — a każda orbita wnosi do tej sumy dokładnie \(|G|\). Przy kolorowaniu \(n\) miejsc \(k\) kolorami jest prosty przepis: jeśli \(g\) jako permutacja miejsc ma \(c(g)\) cykli, to \(|\mathrm{Fix}(g)| = k^{c(g)}\), bo w każdym cyklu wszystkie miejsca muszą mieć ten sam kolor.
Przykład 10. Naszyjniki i bransoletki z 6 koralików
Naszyjniki (utożsamiamy tylko obroty, grupa ma 6 elementów). Obrót o \(j\) pozycji rozpada się na \(\mathrm{NWD}(j, 6)\) cykli, więc ma \(2^{\mathrm{NWD}(j, 6)}\) punktów stałych. Dla \(j = 0, 1, \ldots, 5\): \(64, 2, 4, 8, 4, 2\), suma 84.
Bransoletki (można je też odwrócić na drugą stronę; grupa \(D_6\) ma 12 elementów). Dochodzi 6 symetrii osiowych. Trzy osie przechodzą przez dwa przeciwległe koraliki: te dwa stoją, pozostałe cztery tworzą 2 pary, razem 4 cykle i \(2^4 = 16\) punktów stałych. Trzy osie przechodzą między koralikami: 3 pary, \(2^3 = 8\). Zatem
Różnica \(14 - 13 = 1\) ma konkretny sens: dokładnie jedna para naszyjników (oba z trzema czarnymi koralikami) to wzajemne lustrzane odbicia — obrotem nie przejdą w siebie, ale po odwróceniu bransoletki już tak.
Przykład 11. Wierzchołki kwadratu w trzech kolorach
Na ile sposobów można pokolorować wierzchołki kwadratu trzema kolorami, jeśli kolorowania różniące się symetrią kwadratu uznajemy za takie same? Grupa \(D_4\), \(k = 3\), liczymy cykle każdej symetrii jako permutacji wierzchołków:
- \(e\): 4 cykle, \(3^4 = 81\);
- \(r, r^3\): jeden 4-cykl, po \(3\);
- \(r^2 = (1\;3)(2\;4)\): 2 cykle, \(9\);
- \(s_v = (1\;2)(3\;4)\), \(s_h = (1\;4)(2\;3)\): po 2 cykle, po \(9\);
- \(d_1 = (2\;4)\), \(d_2 = (1\;3)\): po 3 cykle (dwa punkty stałe i para), po \(27\).
Gdyby utożsamiać tylko obroty, wyszłoby \(\frac{81 + 3 + 9 + 3}{4} = 24\).
Przykład 12. Ściany sześcianu w dwóch kolorach
Ile jest istotnie różnych kolorowań ścian sześcianu dwoma kolorami (z dokładnością do obrotu)? Grupa obrotów ma 24 elementy; dzielimy je według osi:
- identyczność: 6 cykli, \(2^6 = 64\);
- obroty o \(\pm 90^\circ\) wokół osi przez środki przeciwległych ścian (6 obrotów): 2 ściany stoją, 4 tworzą jeden cykl — 3 cykle, po \(8\);
- obroty o \(180^\circ\) wokół tych osi (3 obroty): 2 ściany stoją + 2 pary — 4 cykle, po \(16\);
- obroty o \(\pm 120^\circ\) wokół przekątnych sześcianu (8 obrotów): dwa 3-cykle ścian, po \(4\);
- obroty o \(180^\circ\) wokół osi przez środki przeciwległych krawędzi (6 obrotów): 3 pary, po \(8\).
Kontrola liczności: \(1 + 6 + 3 + 8 + 6 = 24\). Wynik:
Typowe błędy
- Zła kolejność składania. \(ab\) to „najpierw \(b\)”. Odwrócenie konwencji w połowie rachunku daje \(d_1\) zamiast \(d_2\) (przykład 1). Ustal konwencję na początku i jej się trzymaj.
- Zakładanie przemienności. Aksjomaty jej nie wymagają; \(D_n\) (\(n \geq 3\)), \(S_n\) (\(n \geq 3\)) i \(GL_2(\mathbb{R})\) nie są przemienne. W szczególności \((ab)^{-1} = b^{-1}a^{-1}\), nie \(a^{-1}b^{-1}\).
- Pominięcie domkniętości. „Zbiór z działaniem” musi mieć wynik w tym samym zbiorze — \(\mathbb{Z}_6 \setminus \{0\}\) z mnożeniem odpada już tutaj.
- Rząd permutacji jako suma lub iloczyn długości cykli. To NWW: \((1\;2)(3\;4\;5)\) ma rząd 6, ale \((1\;2)(3\;4)\) — rząd 2, nie 4.
- Cykle nierozłączne. Wzór na rząd przez NWW działa tylko dla cykli rozłącznych. Najpierw złóż permutację i rozłóż ją na nowo.
- Znak cyklu. Cykl długości \(k\) ma znak \((-1)^{k-1}\): 3-cykl jest parzysty, transpozycja nieparzysta.
- Odwracanie Lagrange’a. \(d \mid |G|\) nie gwarantuje podgrupy rzędu \(d\) (\(A_4\) i liczba 6).
- Dzielenie przez \(|G|\) bez Burnside’a. \(\frac{64}{6}\) nie jest nawet liczbą całkowitą — kolorowania symetryczne mają mniejsze orbity.
- Mylenie naszyjników z bransoletkami. Inna grupa (obroty albo obroty i odbicia), inny wynik: 14 i 13.
Ściąga — grupy w pigułce
Sprawdź się
Rozwiąż samodzielnie, potem porównaj z odpowiedziami poniżej.
- Wyznacz rząd i znak permutacji \((1\;2\;3)(4\;5)\) w \(S_6\).
- Jaki rząd ma 9 w \(\mathbb{Z}_{12}\)? Wypisz podgrupę \(\langle 9 \rangle\).
- Oblicz resztę z dzielenia \(5^{2026}\) przez 13.
- Czy grupa rzędu 10 może mieć element rzędu 4?
- Ile jest naszyjników z 5 koralików w dwóch kolorach, jeśli utożsamiamy obroty?
- Czy grupa \(\mathbb{Z}_{10}^{*} = \{1, 3, 7, 9\}\) jest cykliczna?
Zadania z rozwiązaniami krok po kroku, w których przydają się rzędy elementów, twierdzenie Fermata i zliczanie z symetrią:
- Reszta z dzielenia potęgi dwójki przez 7 — rząd 2 w \(\mathbb{Z}_7^{*}\).
- Dwie ostatnie cyfry wieży potęg trójki — rząd 3 modulo 100 i redukcja wykładnika.
- Największa liczba dzieląca n⁵ − n dla każdego całkowitego n — małe twierdzenie Fermata dla trzech liczb pierwszych.
- Różne ciągi liter ze słowa KAJAKARZ — orbita i stabilizator jak przy słowie ANANAS.
- Nieprzystające trójkąty o całkowitych bokach i obwodzie 30 — liczenie obiektów z dokładnością do przestawienia.
- Trójkąty rozwartokątne o wierzchołkach w dwunastokącie foremnym — symetria obrotowa \(D_{12}\) w zliczaniu.
Więcej zadań z pełnymi rozwiązaniami:
- Zadania z algebry abstrakcyjnej — grupy, permutacje, podgrupy, orbity.
- Zadania z kombinatoryki — permutacje, kombinacje i zliczanie.
Nowe zadania z pełnymi rozwiązaniami, które ćwiczą rachunki z tej lekcji:
- Macierze 2 × 2 nad Z₃ spełniające A² = I
- Liczba wszystkich podgrup grupy Z₄ ⊕ Z₄
- Rząd złożenia permutacji (2 7 5 4)(3 6) i (1 2 5)(3 4 6 7) w S₇
- Liczba elementów rzędu 6 w grupie alternującej A₇
- Wycięcie trzech pól z planszy 4 × 4 z dokładnością do obrotów i odbić
- Kolorowanie krawędzi sześcianu dwoma kolorami z dokładnością do obrotów
Więcej o resztach z dzielenia, które tworzą grupy \(\mathbb{Z}_n\), znajdziesz w lekcji kongruencje i reszty z dzielenia.
Dzisiejszy zestaw zadań → Trening liczenia w pamięci · 2 min