Zoran Skoda permutacija

Permutacija je bijekcija sa skupa $A$ u samog sebe. Svaka bijekcija je preslikavanje koje ima inverznu funkciju, ili ekvivalentno funkcija koja je istovremeno injekcija i surjekcija.

Kompozicija dviju surjekcija je surjekcija. Kompozicija dviju injekcija je injekcija. Dakle kompozicija dviju bijekcija je bijekcija.

Zaključujemo da je kompozicija permutacija permutacija.

Kod konačnih skupova imamo slijedeću notaciju.

Neka je $S$ konačan skup. Tada permutaciju $\sigma: S\to S$ zapisujemo u obliku $2\times kard(S)$-matrice (s $2$ retka i $kard(S)$ elemenata u svakom retku). U prvi red zapisujemo elemente od $S$ (tipični primjer $1,2,\ldots,n$), a u drugi potpisujemo redom njihove vrijednosti (“slike”) po $\sigma$.

Neka je $S = \{a,b,c,d\}$. Tada za permutaciju $\sigma$ moramo reći u koji element ide $a$ u koji $b$ u koji $c$ u koji $d$. dakle, pišemo elemente $a,b,c,d$ u prvi red, a ispod svakog elementa pišemo vrijednost $\sigma(tog\,\,\,elementa)$. Dakle

$$\sigma = \left(\array{ a & b & c & d\\ \sigma(a) & \sigma(b) & \sigma(c) & \sigma(b)}\right)$$

Npr. permutacija

$$\sigma = \left(\array{ a & b & c & d\\ d & a & c & b}\right)$$

šalje $a$ u $\sigma(a) = d$, $b$ u $\sigma(b) =a$, $c$ u $\sigma(c) = c$ i $d$ u $\sigma(d) = b$.

Primijetite da se u drugom retku svaki element od $S$ pojavljuje (jer je permutacija surjekcija) i to točno jednom (jer je permutacija injekcija).

Gledajmo npr. permutacije skupa $\{1 ,2,3,4\}$. Računajmo kompoziciju

$$\sigma\circ\tau = \left(\array{ 1 & 2 & 3 & 4\\ 2 & 1 & 3 & 4}\right) \circ \left(\array{ 1 & 2 & 3 & 4\\ 3 & 1 & 4 & 2}\right)$$

U kompoziciji funkcija uvijek prvo evaluiramo funkciju na desnoj strani onda funkciju na lijevoj strani. Dakle $1$ najprije ide preko $\tau$ u $3$, a onda $3$ ide preko $\sigma$ ponovno u $3$. Dalje, $2$ ide u $\tau(2) = 1$, a $1$ zatim ide u $\sigma(1) = 2$. Slično $(\sigma\circ\tau)(3) = \sigma(\tau(3)) = \sigma(4) = 4$ i $(\sigma\circ\tau)(4) = \sigma(\tau(4)) = \sigma(2) = 1$.

Dakle, rezultat je

$$\sigma\circ\tau = \left(\array{ 1 & 2 & 3 & 4\\ 3 & 2 & 4 & 1}\right)$$

Koliko permutacija ima konačan skup $S$ od $K$ elemenata ? Prebrojimo permutacije $S\to S$. Ako je $S$ konačan skup onda ga možemo gledati kao da je uređen (jednom za svagda). Prvi element možemo smjestiti permutacijom na bilo koje od $K$ mjesta (uključujući ono na kojem smo bili i prije) tj. pridružiti mu permutacijom onaj element koji je bio prije permutacije na tom mjestu. Sad je jedno mjesto zauzeto (jedan element u kodomeni; to je zato što je permutacija injekcija pa ni jedan drugi element ne smijemo poslati u taj isti element); drugim riječima, kako je permutacija bijekcija slijedeći element možemo staviti na jedno od $K-1$ preostalih mjesta. Dakle prva dva elementa možemo smjestiti na ukupno $K\times (K-1)$ načina. Za svako od tih $K\times (K-1)$ smještenja prva dva elementa, treći element možemo smjestiti na jedno od preostalih $K-2$ mjesta, dakle prva tri elementa možemo smjestiti na $K\times (K-1)\times(K-2)$ načina itd. Dakle, sveukupno $K$ elemenata možemo razmjestiti na

$$K! = K \cdot (K-1) \cdot (K-2) \cdots 2\cdot 1$$

načina. Npr. riječ $ABC$ ima $3! = 3\cdot 2\cdot 1 = 6$ anagrama, tj. permutacija: $ABC, ACB, BAC, BCA, CAB, CBA$. Ovdje smo ih poredali “abecedno” gdje slova koja su naprijed imaju redom veću težinu nego ona iza njih ili, kako to matematičari kažu, leksikografskim uređajem (kao u enciklopediji).

Cayleyev teorem: svaka grupa izomorfna je podgrupi grupe permutacija nekog skupa.

Skica dokaza. Neka je $(G,\cdot)$ grupa s neutralnim elementom $e$. Gledamo grupu svih permutacija $Perm(G)$ same grupe. Među permutacijama su preslikavanja $L_g$, $g\in G$ gdje je $L_g(h) = g\cdot h$ za svaki $h\in G$. Ako je $L_g(h) = L_g(h')$ tada je $g h = g h'$, pa ako pomnožimo s lijeva s $g^{-1}$ dobijemo $h = h'$. Time smo dokazali da je svaka $L_g$ injekcija. Surjekcija je zato što $L_g(g^{-1} k) = k$ dakle svaki $k$ je u slici.

Sada definiramo homomorphizam grupa $L : G\to Perm(G)$, $g\mapsto L_g$. Najprije se provjeri da je to homomorfizam, tj. da $L_{a\cdot a'} = L_a\circ L_{a'}$. Zaista, za svaki $b\in B$, $L_{a\cdot a'}(b) = (a\cdot a')\cdot b = a\cdot (a'\cdot b) = L_a(L_{a'}(b)) = (L_a\circ L_{a'})(b)$. Nakon toga provjerimo da je homomorfizam zapravo injektivan. Injektivnost znači da $L_g(h) = L_{g'}(h)$ za sve $h$ implicira da $g = g'$. No, prvi identitet raspišemo $g h = g' h$ pa množenjem s $h^{-1}$ zdesna, uz korištenje asocijativnosti, daje $g = g'$. Za kraj dokaza sjetimo da je slika bilo kojeg injektivnog homomorfizma grupa podgrupa kodomene (dakle izomorfna (bijektivna homomorfna) slika početne grupe). Ako smo zaboravili tu činjenicu lako je pokažemo: neka je $J: (G,\cdot)\to (H,\circ)$ ma koji injektivni homomorfizam grupa i $J(G) = \{h\in H\,|\,\exists g, h = J(G)\}$ slika od $J$. Ako su dva elementa, $h_1, h_2\in J(G)$ dakle oblika $h_1 = J(g_1)$, $h_2 = J(g_2)$, tada je $h_1\cdot h_2 = J(g_1)\circ J(g_2) = J(g_1\cdot g_2)$, dakle element iz $J(G)$. Dakle, $J(G)$ je zatvoren s obzirom na operaciju $\circ$ u $H$. Jedinični element $e' = J(e)$ je u $J(G)$. Za svaki element $h$, inverz od $J(g)$ je $J(g^{-1})$ dakle ponovno u $J(G)$.

category: zadarmat1, zadarmat4