Grupy permutacji

https://en.wikipedia.org/wiki/Permutation_group

https://en.wikipedia.org/wiki/Permutation_graph

WPROWADZENIE

Dlaczego grupy permutacji są interesujące?

• Grupy permutacji są najstarszym typem reprezentacji grup.
• Grupy permutacji pełnią w matematyce szczególną rolę. Pojawiają się w bardzo różnorodnych działach matematyki. Są z jednej strony niemal najprostszymi grupami nieprzemiennymi, ale też są wystarczająco złożone, aby zawierać wszystkie grupy skończone.
• Algorytmy grup permutacji pełnią ważną rolę konia pociągowego systemów algebry symbolicznej obliczających grupy.
• Permutacje są obecne w fizyce.
• Teoria permutacji była kluczowa dla złamania szyfru Enigmy.
  https://www.impan.pl/Great/Rejewski/article.html
• W teorii grafów istnieją grafy permutacji, których wierzchołki odpowiadają elementom permutacji. Dwa wierzchołki są połączone krawędzią, jeżeli permutacja zmienia kolejność odpowiednich elementów (powstaje inwersja).
  Przykład. Permutacja [3 1 2] odpowiada grafowi G = (V, E), gdzie zbiór wierzchołków V = {1, 2, 3}, a zbiór krawędzi E = {(1, 3), (2, 3)} (te dwie pary liczb tworzą inwersję w permutacji).

PERMUTACJE

Definicja. Permutacją (bez powtórzeń) zbioru n-elementowego X nazywamy dowolną bijekcję p: X → X. Zwykle X to zbiór liczb naturalnych od 1 do n, choć w implementacjach komputerowych czasem X to zbiór liczb całkowitych od 0 do n-1.

Permutacja p liczb od 0 do n-1 (permutacja jako funkcja).
Kolejność kolumn nie ma znaczenia.
[  0    1    2  ...   n-1 ] = [  i    j  ...]
[p[0] p[1] p[2] ... p[n-1]]   [p[i] p[j] ...]
Inny zapis permutacji to dolny wiersz macierzy (tu kolejność kolumn ma znaczenie)
[p[0], p[1], p[2], ..., p[n-1]]

Dla permutacji określamy mnożenie *, które rozumiemy jako składanie funkcji, (p*q)(i) = p(q(i)).
Permutacja tożsamościowa id(i) = i dla każdego i = 0, 1, ... n-1.
UWAGA W literaturze można spotkać inną konwencję dla mnożenia permutacji.

Permutacje zbioru n-elementowego X tworzą grupę symetryczną Sym(X), oznaczaną też S_n.
Rząd grupy S_n wynosi |S_n| = n!

Każdą podgrupę grupy symetrycznej nazywamy grupą permutacji.

Podgrupa alternująca Alt(X) [A_n], zawiera permutacje parzyste z grupy Sym(X) [S_n]. Dla n większego lub równego 5, grupa A_n jest prosta i jest to jedyna podgrupa niezmiennicza S_n.
Rząd grupy alternującej wynosi |A_n| = n! / 2.

Twierdzenie Cayley'a. Każda grupa G rzędu n jest izomorficzna z pewną podgrupą grupy symetrycznej S_n.

CYKLE

Każdą permutację można zapisać jako iloczyn cykli rozłącznych. Kolejność cykli rozłącznych w rozkładzie nie ma znaczenia.

Przykład. Cykl długości 3 (i, j, k) to permutacja
(tylko elementy i, j, k są przenoszone przez permutację)
[i j k s t ...] = (i, j, k) = (j, k, i) = (k, i, j)
[j k i s t ...]

[0 1 2 3 4 5 6] = (0, 2, 5) (1, 3, 4, 6)
[2 3 5 4 6 0 1]

Cykl długości 0 () to permutacja tożsamościowa.

Cykl długości 1 (i) to właściwie permutacja tożsamościowa.

Cykl długości 2 (i, j) = (j, i) to transpozycja (i != j).

Cykl długości k > 2 jest złożeniem k-1 transpozycji.

[c[0] c[1] ... c[k-1]] = (c[0], c[1], c[2], .... c[k-1]) = c
[c[1] c[2] ... c[0]  ]

c = (c[0], c[k-1]) (c[0], c[k-2]) ... (c[0], c[2]) (c[0], c[1])

(i, j, k) = (i, k) (i, j)

Każda transpozycja może być wyrażona jako iloczyn transpozycji liczb sąsiednich (adjacent transpositions) poprzez formułę rekurencyjną
(i, i+v) = (i+1, i+v) (i, i+1) (i+1, i+v).
Sprawdzenie, transpozycje działają kolejno od prawej do lewej.
i+v → i+1 → i.
i → i+1 → i+v.
i+1 → i+v → i+v (bez zmiany).
Przykład. (1, 4) = (2, 4) (1, 2) (2, 4) = (3, 4) (2, 3) (3, 4) (1, 2) (3, 4) (2, 3) (3, 4).

Znak permutacji p to liczba sgn(p) = (-1)^r, gdzie r jest liczbą transpozycji, na którą rozkłada się dana permutacja.
Cykl długości k ma parzystość (-1)^(k+1).
sgn(id) = 1.
sgn(p * q) = sgn(p) * sgn(q).
sgn(p^{-1}) = sgn(p).

GRUPA S_2

S_2 = {(), (0,1)}, grupa cykliczna rzędu 2.

GRUPA S_3

S_3 = {(), (0,1), (0,2), (1,2), (0,1,2), (0,2,1)}. Rząd grupy wynosi |S_3| = 3! = 6.

Grupa S_3 jest izomorficzna z C_3v i D_3.

Podział S_3 na klasy elementów sprzężonych (Byron ładnie robi przekształcenia na cyklach):
Cl_1 = {()},
Cl_2 = {(0,1,2), (0,2,1)} - cykle potrójne (parzyste permutacje),
Cl_3 = {(0,1), (0,2), (1,2)} - cykle podwójne (nieparzyste permutacje).

Podgrupa cykliczna rzędu 3 to A_3 = Cl_1 + Cl_2 = {(), (0,1,2), (0,2,1)}.
A_3 jest to dzielnik normalny, zawiera pełne klasy elementów sprzężonych.