Permutaatiot [-]
- Joukon $A$ permutaatio on bijektio $A\to A$ ja kun puhutaan permutaatioista oletetaan tavallisesti, että $\card{A}<\infty$.
- Identtinen kuvaus $Id_A: x\in A\mapsto x\in A$ on permutaatio samoin permutaation $\alpha$ käänteiskuvaus $\alpha^{-1}$ sekä kahden permutaation $\alpha$ ja $\beta$ yhdistetty kuvaus $\alpha\circ \beta$. Lisäksi pätee $(\alpha\circ \beta)\circ \gamma= \alpha \circ (\beta\circ\gamma)$.
- Jos $\alpha$ on (joukon $A$) permutaatio niin $\alpha^0=Id_A$, $\alpha^m=\underbrace{\alpha\circ \alpha\circ\ldots \circ \alpha}_{m}$ ja $\alpha^{-m}=(\alpha^{-1})^m$ kun $m>0$.
Permutaation radat ja sykliesitys [-]
Olkoon $A$ äärellinen ei-tyhjä joukko.
- Jos $\alpha$ on $A$:n permutaatio niin $\alpha$:n radat ovat joukot $\set{\alpha^j(x)\mid j\in \Z}$ missä $x\in A$ eli ekvivalenssiluokat kun ekvivalenssirelaationa on $x\sim y$ jos ja vain jos $y=\alpha^j(x)$ jollain $j\in \Z$.
- Joukon $A$:n permutaatio $\alpha$ on sykli jos $\alpha(x_j)=x_{j+1}$, $j=1,2,\ldots,k-1$ ja $\alpha(x_k)=x_1$ missä $x_1,x_2,\ldots,x_k\in A$ (ja $x_i\neq x_j$ kun $i\neq j$) ja $\alpha(x)=x$ kaikilla $x\in A\setminus\{x_1,\ldots,x_k\}$. Syklimerkinnöillä kirjoitetaan $ \alpha=\begin{pmatrix} x_1 & x_2 &\dots &x_k\end{pmatrix}$. Tällaisen syklin $\alpha$ pituus on $k$ ja sanotaan, että $\alpha$ on $k$-sykli. Syklin $\alpha$ radat ovat $\{x_1,x_2,\ldots,x_k\}$ ja joukot $\{x\}$ kaikilla $x\in A\setminus\{x_1,\ldots,x_k\}$.
- Jos $\alpha$ on permutaatio niin jokaista sen rataa vastaa sykli ja $\alpha$ voidaan esittää näiden syklien tulona (eli yhdistettynä funktiona) jolloin syklien järjestyksellä ei ole merkitystä ja $\circ$-merkkiä tavallisesti jätetään pois. (Tässä tapauksessa mikään alkio ei esiinny vähintään kahdessa syklissä ja jos näin olisi, niin silloin syklien järjestyksellä on väliä.)
Esimerkki: [+]
Olkoon \[ \alpha= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 4 & 1 & 3 & 5 & 7 & 6 \end{pmatrix}, \] joukon $A=\{1,2,3,4,5,6,7\}$ permutaatio missä siis tämä merkintätapa tarkoittaa, että esim. $\alpha(1)=2$ ja $\alpha(2)=4$ jne.
Nyt näemme, että $1\mapsto 2 \mapsto 4 \mapsto 3 \mapsto 1$ (eli $\alpha(1)=2$, $\alpha(2)=4$ jne.) ja tästä saamme syklin $\begin{pmatrix} 1 & 2 & 4 & 3\end{pmatrix}$ joka siis on permutaatio $\beta_1$ jolle pätee $\beta_1(1)=2$, $\beta_1(2)=4$, $\beta_1(4)=3$, $\beta_1(3)=1$ ja $\beta(x)=x$ kaikilla $x\in \{5,6,7\}$. Koska $\alpha(5)=5$ saamme syklin $\beta_2=(5)$ jolle siis $\beta_2(x)=x$ kaikilla $x\in A$. Lopuksi näemme, että $6\mapsto 7\mapsto 6$ joten saamme syklin $\beta_3=\begin{pmatrix} 6 & 7\end{pmatrix}$.
Syklinotaatiolla voimme nyt kirjoittaa \[ \alpha =\beta_1\beta_3=\begin{pmatrix} 1 & 2 & 4 & 3\end{pmatrix} \begin{pmatrix} 6& 7\end{pmatrix}, \] koska $\beta_2$ on identiteettifunktio. Mutta on myös muita esitystapoja syklien tuloina, esim. $\alpha= \begin{pmatrix} 7 & 6\end{pmatrix}\begin{pmatrix} 4 & 3 & 1 & 2\end{pmatrix}$ tai $\alpha =\begin{pmatrix} 1 &3 \end{pmatrix} \begin{pmatrix} 1 & 4\end{pmatrix} \begin{pmatrix} 1 & 2\end{pmatrix} \begin{pmatrix} 7 & 6\end{pmatrix}$.
Joukot $A_1=\{1,2,4,3\}$, $A_2=\{5\}$ ja $A_3=\{6,7\}$ ovat permutaation $\alpha$ radat.
Esimerkki: Permutaatioiden yhdistäminen [+]
Kun permutaatio $\alpha$ esitetään muodossa $\alpha=(4\; 3\; 2\; 1)(2\; 4)(1\; 2\; 3\; 4)$ niin järjestyksellä on merkitystä koska näillä sykleillä on yhteisiä elementtejä. Voimme esittää permutaation $(1\; 2\; 3\; 4)$ myös seuraavana verkkona:
Kun muodostamme yhdistetyn funktion $\alpha$ meidän täytyy muistaa, että määritelmästä $(f\circ g)(x)=f(g(x))$ seuraa, että meidän täytyy aloittaa oikealta ja saamme seuraavanlaisen verkon:
Tästä voimme päätellä, että $\alpha = (1\; 3)$ koska $\alpha\Bigl($$\Bigr )$$= \quad.$
Parilliset ja parittomat permutaatiot [+]
- Jokainen sykli, jonka pituus on $k\geq 2$ voidaan kirjoittaa $k-1$:n $2$-syklin tulona koska
- Jokainen permutaatio voidaan kirjoittaa $2$-syklien tulona (kunhan perusjoukossa on ainakin kaksi alkiota).
- Jos permutaatio $\alpha$ on kirjoitettu sekä $r$:n että $r'$:n $2$-syklin tulona niin $(-1)^r=(-1)^{r'}$ ja permutaation merkki on $\textrm{sign}(\alpha)=(-1)^r$.
- Jos $\alpha$ on sykli, jonka pituus on $k$ niin $\textrm{sign}(\alpha)=(-1)^{k+1}$.
- Jos $\alpha$ on $n$-alkioisen joukon permutaatio ja $\alpha$:lla on $m$ rataa niin $\textrm{sign}(\alpha)= (-1)^{n-m}$.
- Permutaatio $\alpha$ sanotaan olevan parillinen jos $\textrm{sign}(\alpha)=1$ ja muuten pariton.
- Jos $\alpha$ ja $\beta$ ovat saman joukon permutaatioita niin
$\textrm{sign}(\alpha\beta)=
\textrm{sign}(\alpha)\textrm{sign}(\beta)$.
Ryhmät [+]
Ryhmä on pari $[G,\bullet]$ missä $G$ on joukko ja $\bullet$ on binäärinen operaatio $G$:ssä eli funktio $G\times G\to G$, siten, että seuraavat ehdot ovat voimassa:
- Sulkeutuneisuus: $a\bullet b \in G$ jos $a$ ja $b\in G$. (Seuraus oletuksesta, että $\bullet:G\times G\to G$ on funktio.)
- Assosiatiivisuus: $(a\bullet b)\bullet c = a\bullet(b\bullet c)$ jos $a$, $b$ ja $c\in G$.
- Neutraalialkio: On olemassa alkio $e\in G$ siten, että $e\bullet a=a\bullet e = a$ jos $a\in G$.
- Käänteisalkio: Jos $a\in G$, niin on olemassa alkio $a^{-1}\in G$ (joka osoittautuu yksikäsitteiseksi) siten, että $a\bullet a^{-1}=a^{-1} \bullet a = e$.
Huom! [-]
- Jos joukko $G$ sisältää täsmälleen kaikki jonkin joukon $A$ permutaatiot ja $\bullet$ on funktioiden yhdistäminen $\circ$ niin $[G,\bullet]$ on ryhmä.
- Usein sanotaan "$G$ on ryhmä" jos on selvää, mikä ryhmäoperaatio on.
- Merkinnän $a\bullet b$ (tai $\bullet(a,b)$ jos pidetään tiukasti kiinni siitä, että $\bullet$ on funktio) sijasta kirjoitetaan usein $ab$. Neutraalialkion symbolina käytetään myös $1$, $I$ tai $Id$. Lisäksi $a^0=e$, $a^m=\underbrace{a\bullet a\bullet\ldots \bullet a}_{m}$ ja $a^{-m}=(a^{-1})^m$ kun $m>0$.
- Ryhmän määritelmässsä ehdot (c) ja (d) voidaan korvata
(näennäisesti vähemmän vaativilla) ehdoilla,
että on olemassa alkio $e\in G$ siten,
että $e\bullet a=a$ jos $a\in G$ ja että jos $a\in G$,
niin on olemassa alkio $a^{-1}\in
G$ siten, että
$a^{-1} \bullet a = e$. Miksi? [+]
Uusien ehtojen ja assosiatiivisuuden nojalla pätee \[ (a^{-1})^{-1}\bullet a^{-1}\bullet a\bullet a^{-1} = ((a^{-1})^{-1}\bullet a^{-1})\bullet (a\bullet a^{-1})\\= e\bullet (a\bullet a^{-1}) = a\bullet a^{-1}, \] ja \[ (a^{-1})^{-1}\bullet a^{-1}\bullet a\bullet a^{-1} = (a^{-1})^{-1}\bullet ((a^{-1})\bullet a)\bullet a^{-1})\\= (a^{-1})^{-1}\bullet (e\bullet a^{-1})= (a^{-1})^{-1}\bullet a^{-1}=e, \] joten $a\bullet a^{-1}= e$ eli alkuperäinen ehto (d) on voimassa.
Tämän tuloksen nojalla saamme \[ a\bullet a^{-1}\bullet a= (a\bullet a^{-1})\bullet a=e\bullet a =a, \] ja \[ a\bullet a^{-1}\bullet a= a\bullet (a^{-1})\bullet a)=a\bullet e, \] joten $a\bullet e = a$ ja alkuperäinen ehto (c) on voimassa.
Huomaa myös, että olisimme yhtä hyvin voineet ottaa uusiksi ehdoiksi $a\bullet e = a$ ja $a\bullet a^{-1}=e$). Toisaalta ehdoilla $e\bullet a=a$ ja $a\bullet a^{-1}=e$ ei voida korvata ehtoja (c) ja (d) koska jos $G$ on joukko, johon kuuluu vähintään $2$ alkiota ja määrittelemme $x\bullet y= y$ kun $x$ ja $y\in G$ niin (a) ja (b) ovat voimassa ja alkioksi $e$ voimme valita minkä tahansa $G$:n alkion ja alkioksi $a^{-1}$ voimme valita tämän alkion $e$. Mutta silloin alkuperäiset ehdot (c) ja (d) eivät ole voimassa.
Kommutatiiviset eli Abelin ryhmät [+]
Esimerkkejä ryhmistä (permutaatioiden lisäksi)[+]
- $G=\Z$ ja $\bullet = +$ jolloin neutraalialkio on $0$ ja $n$:n käänteisalkio on $-n$.
- $G=]0,\infty[$ ja $\bullet=\cdot$ eli tavallinen kertolasku jolloin neutraalialkio on $1$ ja $x$:n käänteisalkio on $x^{-1}$ eli $\frac 1x$.
- $G=\Z/7\Z \setminus\{[0]_7\}$ ja $\bullet$ on jäännösluokkien kertolasku.
- $G$ on joukko johon kuuluvat kaikki $n\times
n$-matriisit, joiden determinantti on nollasta poikkeava ja
$\bullet$ on matriisien
kertolasku. Neutraalialkio on yksikkömatriisi ja käänteisalkio on
käänteismatriisi. Tämä
ryhmä ei ole kommutatiivinen kun $n\geq 2$.
Aliryhmät [-]
Jos $G$ (eli $[G,\bullet]$) on ryhmä niin joukon $G$ ei-tyhjä osajoukko $H$ on $G$:n aliryhmä jos seuraavat ehdot pätevät ja silloin $H$ (eli $[H,\bullet_{|H\times H}]$) on myös ryhmä:
- Jos $a$ ja $b\in H$ niin $a\bullet b\in H$.
- Jos $a\in H$ niin $a^{-1}\in H$.
Sykliset ryhmät [+]
- Ryhmä $G$ on syklinen jos on olemassa $a\in G$ siten, että $G=\set{a^j\mid j\in \Z}$. Silloin sanotaan, että $G$ on $a$:n generoima syklinen ryhmä ja merkitään $G=\langle a\rangle$.
- Jos $G$ on ryhmä ja $a\in G$ niin $\langle a\rangle=\set{ a^{j}\mid j\in Z}$ on $a$:n generoima $G$:n syklinen aliryhmä.
Esimerkki [+]
Homomorfismit ja isomorfismit [+]
Olkoot $[G_1,\bullet_1]$ ja $[G_2,\bullet_2]$ kaksi ryhmää ja olkoon $\psi$ funktio: $ G_1\to G_2$.
- $\psi$ on homomorfismi jos $\psi(a\bullet_1 b)=\psi(a)\bullet_2 \psi(b)$ kaikilla $a$ ja $b\in G_1$.
- $\psi$ on isomorfismi jos se on homomorfismi ja bijektio (jolloin myös $\psi^{-1}$ on homomorfismi ja siten isomorfismi: $G_2\to G_1$).
- Kaksi ryhmää $[G_1,\bullet_1]$ ja $[G_2,\bullet_2]$ ovat isomorfiset jos on olemassa isomorfismi: $G_1\to G_2$.
Ryhmät ovat tässä epäolennaisia, oleellista on, että homomorfismi "säilyttää struktuurin"!
Isomorfismi: Esimerkkejä [+]
- Jos $\psi(x)=\log(x)$ niin $\psi:]0,\infty[\to \R$ on isomorfismi kun laskutoimitus joukossa $G_1=]0,\infty[$ on kertolasku ja laskutoimitus joukossa $G_2=\R$ on yhteenlasku, eli $[G_1,\bullet_1]= \bigl []0,\infty[,\cdot\bigr ]$ ja $[G_2,\bullet_2]= [\R,+]$.
- Jos $[G_1,\circ]$ on ryhmä, johon kuuluvat täsmälleen kaikki joukon $A_1$ permutaatiot ja $[G_2,\circ]$ on ryhmä, johon kuuluvat täsmälleen kaikki joukon $A_2$ permutaatiot ja $\card{A_1}=\card{A_2}=m$ niin $G_1$ ja $G_2$ ovat isomorfiset. och sådana grupper betecknas med $S_m$. Tällaiset ryhmät merkitään $S_m$:llä.
- Jokainen ryhmä $[G,\bullet]$ on isomorfinen jonkin joukon permutaatioiden aliryhmän kanssa koska joukoksi voidaan valita $G$ ja isomorfismiksi voidaan valita $\psi(a)(b) = a\bullet b$ mutta tästä ei seuraa että aina olisi hyödyllistä käsitellä ryhmää tällaisena permutaatioryhmänä.
- Jos $[G_1,\bullet_1]$ ja $[G_2,\bullet_2]$ ovat kaksi syklistä
ryhmää ja $\card{G_1}=\card{G_2}$ niin $G_1$ ja $G_2$ ovat
isomorfiset
eli on olemassa isomorfismi $\psi:G_1\to G_2$ ja tästä syystä
syklistä ryhmää, jossa on $m$ alkiota merkitään $C_m$:llä.
Sivuluokat [+]
Olkoon $G$ ryhmä, $H$ sen aliryhmä ja $a\in G$ (ja $a\bullet b$:n sijasta kirjoitetaan $ab$).
- Joukko $aH=\set{ ab\mid b\in H}$ on $H$:n vasen sivuluokka, joka sisältää $a$:n.
- Joukko $Ha=\set{ ba\mid b\in H}$ on $H$:n oikea sivuluokka, joka sisältää $a$:n.
Sivuluokilla on seuraavia ominaisuuksia (tässä ainoastaan vasemmat sivuluokat):
- $\card{aH}=\card{H}$ kaikilla $a\in G$.
- Jos $a$ ja $b\in G$ niin joko $aH=bH$ tai $aH\cap bH=\emptyset$.
- $\cup_{a\in G} aH= G$.
- Jos $a$ ja $b\in G$ ja $aH=bH$ niin pätee $b^{-1}a\in H$.
- $\card{G} =\card{H}\cdot \card{\set{aH\mid a\in G}}$ ja näin ollen luku $\card{H}$ jakaa luvun $\card {G}$ (kun nämä luvut ovat äärelliset).
Esimerkki [+]
Jos $G=\R^2=\set{(x,y)\mid x,y\in \R}$ ja laskutoimitus on yhteenlasku $(x_1,y_1)+(x_2,y_2)=(x_1+x_2,y_1+y_2)$ niin $H=\set{(t,2\cdot t)\mid t\in \R}$ on ryhmän $[G,+]$ aliryhmä ja sen sivuluokat ovat joukot $\set{(u+t,v+2\cdot t)\mid t\in \R}$ missä $(u,v)\in G$ eli suoran $y=2x$ suuntaisten suorien pistejoukot.
Sivuluokat ekvivalenssiluokkina [+]
- Relaatio $a\sim b$ jos ja vain jos $b^{-1}a\in H$ on ekvivalenssirelaatio joukossa $G$ ja ekvivalenssiluokat ovat vasemmat sivuluokat.
- Relaatio $a\sim b$ jos ja vain jos $ab^{-1}\in H$ on
ekvivalenssirelaatio joukossa $G$ ja ekvivalenssiluokat ovat
oikeat sivuluokat.
Homomorfismit, normaalit aliryhmät ja tekijäryhmät [+]
Olkoon $G$ ryhmä.
- Jos $G'$ on ryhmä, jonka neutraalialkio on $e'$ ja $\psi:G\to G'$ on homomorfismi niin $H=\set{a\in G\mid \psi(a)= e'}$ ($\psi$:n ydin) on $G$:n aliryhmä.
- $G$:n aliryhmä $H$ on muotoa $\set{a\in G\mid \psi(a)= e'}$ jollakin homomorfismilla $G\to G'$ jos ja vain jos $aH=Ha$ kaikilla $a\in G$ (tai yhtäpitävästi, $aba^{-1}\in H$ kaikilla $a\in G$ ja $b\in H$). Tässä tapauksessa sanotaan, että $H$ on $G$:n normaali aliryhmä.
- Jos $H$ on $G$:n normaali aliryhmä niin sivuluokat (vasen sama kuin oikea) muodostavat tekijäryhmän, jota merkitään $G/H$:lla ja jonka ryhmäoperaatio on $(aH)(bH)= (ab)H$, neutraalialkio $H$ ja käänteisalkio $(aH)^{-1}=a^{-1}H$. Funktio $\psi:G\to G/H$, jonka määritelmä on $\psi(a)= aH$ on homomorfismi, jonka ydin on $H$.
Jäännösluokat tekijäryhminä [+]
Kun $n> 1$ niin $n\Z=\set{n\cdot j\mid j\in \Z}$
on ryhmän $[\Z,+]$
aliryhmä ja koska yhteenlasku on
kommutatiivinen laskutoimitus niin $n\Z$ on
normaali aliryhmä. Aliryhmän $n\Z$ sivuluokat ovat jäännösluokat
modulo $n$ ja ne muodostavat tekijäryhmän $\Z/n\Z$ missä
laskutoimitus on yhteenlasku.
Sykli-indeksi ja Pólyan "väritys"-lause [-]
Määritelmä [-]
- Jos $a$ on joukon $X$ permutaatio niin $a$:n sykli-indeksi on funktio \[ \zeta_{a,X}(t_1,\ldots ,t_n)= t_1^{j_1}\cdot t_2^{j_2} \cdot \ldots \cdot t_n^{j_n} \] missä $j_k$ on $a$:n $k$-pituisten ratojen lukumäärä ja $n=\card{X}$.
- Jos $G$ on ryhmä joukon $X$ permutaatiota niin $G$:n
sykli-indeksi on
Esimerkki: Sykli-indeksi [+]
Olkoon $G$ ryhmä, joka muodostuu kaikista alla olevan verkon solmujen permutaatiosta $f$ siten, että jos solmujen $x$ ja $y$ välillä on kaari, niin myös solmujen $f(x)$ ja $f(y)$ välillä on kaari.
Koska ainoastaan solmuilla $3$ ja $4$ on $3$ naapuria niin joko $f(3)=3$ ja $f(4)=4$ tai $f(3)=4$ ja $f(4)=3$ (koska ehdosta, että naapurit pysyvät naapureina seuraa, että $x$:llä ja $f(x):llä on yhtä monta naapuria). Solmut $1$ ja $2$ kuvautuvat solmun $f(3)$ naapureille ja samoin solmut $5$ ja $6$ kuvautuvat solmun $f(4)$ naapureille.
Näin ollen kyseiset permutaatiot ovat: $(1)$, $(1\; 2)$, $(5\; 6)$, $(1\; 2)(5\; 6)$, $(3\; 4)(1\; 5)(2\; 6)$, $(3\; 4)(1\; 6)(2\; 5)$, $(3\; 4)(1\; 5\; 2\; 6)$ ja $(3\; 4)(1\; 6\; 2\; 5)$.
Näytä permutaatio:
Seuraavaksi on laskettava näiden permutaatioiden ratojen pituudet: Näin ollen sykli-indeksi tulee olemaan
Ryhmän toiminta [+]
- Jos $G$ eli $[G,\bullet]$ on ryhmä ja $X$ on joukko niin $G$:n toiminta joukossa $X$ on homomorfismi $G$:ltä $X$:n permutaatioiden ryhmälle.
- Jos yhdistetty funktio määritellään (normaalilla) tavalla $(f\circ g)(x)= f(g(x))$ niin saadaan vasen toiminta ja jos määritellään $x(f\diamond g)= (xf)g$ niin saadaan oikea toiminta. Sen sijaan että kirjoitettaisiin $\psi(a)(x)$ missä $\psi$ on homomorfismi, $a\in G$ ja $x\in X$ kirjoitetaan useimmiten $ax$ ja sanotaan että $G$ toimii joukossa $X$. Vasemmalle toiminnalle homomorfismiominaisuudeksi tulee $(ab)x=a(bx)$, $a, b\in G$, $x\in X$.
- Jos $G$ on ryhmä $X$:n permutaatioita niin identiteettifunktio on homomorfismi eikä toiminta-käsitettä tarvita.
- Jos $G$ on ryhmä niin se toimii itsessään esim. siten, että
$\psi(a)(x) = ax$ (vasen toiminta), $\psi(a)(x)= axa^{-1}$
(vasen toiminta), $\psi(a)(x)= xa$ (oikea toiminta)
tai $\psi(a)(x)= a^{-1}xa$ (oikea toiminta).
Radat, kiinnittäjäaliryhmät ja kiintopistejoukot [+]
- Jos $x\in X$ niin sen rata $G$:n toiminnassa on joukko $Gx=\set{ax\mid a\in G}\subseteq X$.
- Jos $x\in X$ niin sen rata alkion $a\in G$ toiminnassa on joukko $\langle a\rangle$$x$ $=\set{a^jx\mid j\in \Z}\subseteq X$.
- Jos $x\in X$ niin sen kiinnittäjäaliryhmä $G$:n toiminnassa on aliryhmä $G_x=\set{a\in G\mid ax=x}\subseteq G$.
- Jos $a\in G$ niin sen kiintopistejoukko
on $X$:n osajoukko $ X_a=\set{x\in X\mid ax=x}\subseteq X$.
(Tätä joukkoa merkitään joskus myös $X^a$:lla tai $F(a)$:lla.) - Jokaisella $x\in X$ pätee $\abs{Gx}\cdot \abs{G_x}
=\abs{G}$.
Miksi [+]
Oletamme, että $G$ on äärellinen ryhmä. Jos $H$ on $G$:n aliryhmä niin $\abs{H}\cdot m=\abs{G}$ missä $m$ on $H$:n (esim. vasempien) sivuluokkien lukumäärä (koska kaikissa sivuluokissa on yhtä monta alkiota kuin $H$:ssa ja niiden unioni on $G$). Koska $G_x$ on $G$:n aliryhmä niin valitsemme $H=G_x$ ja konstruoimme bijektion $\psi$ aliryhmän $G_x$ sivuluokkien joukosta rataan $Gx$ jolloin osoitamme, että $m=\abs{Gx}$ josta seuraa, että $\abs{G}=\abs{G_x}\cdot \abs{Gx}$.
Määrittelemme $\psi(aG_x)= ax$. Jos $a_1G_x=a_2G_x$ niin pätee $a_2^{-1}a_1\in G_x$ joten $a_2^{-1}a_1x=x$ eli $a_1x=a_2x$ joten $\psi$ on hyvin määritelty.
Jos $a_1x=a_2x$ niin pätee $a_2^{-1}a_1x=x$ joten $a_2^{-1}a_1\in G_x$, josta seuraa, että $a_1G_x=a_2G_x$ eli $\psi$ on injektio.
Jos $y\in Gx$ niin on olemassa $a\in G$ siten, että $y=ax$ ja silloin $y=\psi(aG_x)$ josta seuraa, että $\psi$ on surjektio.
- Jos joukossa $X$ määritellään relaatio $\sim$ siten, että $x\sim y$ jos ja vain jos $x=ay$ jollakin $a\in G$ niin $\sim$ on ekvivalenssirelaatio ja ekvivalenssiluokat ovat radat $G$:n toiminnassa eli joukot $Gx$ missä $x\in X$.
Esimerkki: $G_x$, $Gx$ ja $X_a$ [+]
Permutaation generoima syklinen ryhmä [+]
- $\beta_j^{r}$ on identiteetti funktio jos ja vain jos $b_j\,|\, r$.
- $\alpha$:n generoiman syklisen ryhmän alkioiden lukumäärä $\card{G}$ on lukujen $b_1,b_2, \ldots,b_k$ pienin yhteinen jaettava koska $\card{G}$ on pienin positiivinen luku $q$ siten, että $\alpha^q$ on identiteettifunktio (eli sama kuin $\alpha^0$).
- Jos $\beta_j=(x_1\; x_2\; \ldots \; x_{b_j})$ ja $1\leq i \leq b_j$ niin $\beta_j^mx_i=\alpha^mx_i=x_i$ kun $0 \leq m<\card{G}$ jos ja vain jos $b_j\,|\, m$, josta seuraa, että kiinnittäjäaliryhmä $G_{x_i}$ on
Ratojen lukumäärä ryhmän toiminnassa (Burnsiden lemma) [+]
Merkitsemme ratojen joukkoa $X/G$:llä ja ne ovat ekvivalenssiluokkia kun ekvivalenssirelaatio $\sim$ on $x\sim y$ jos ja vain jos $x=ay$ jollain $a\in G$. Eri radoilla ei ole yhteisiä alkioita ja ratojen unioni on $X$ eli $X=\cup_{R\in X/G}R$. Koska $\abs{G_x}= \frac {\abs{G}}{\abs{Gx}}$ ja $Gx$ on rata, johon alkio $x$ kuuluu niin saamme väitteemme seuraavan laskun avulla:
Ryhmän toiminta ja "väritykset" [+]
- Joukon $X$ väritys on funktio $\omega:X\to K$ missä $K$ on joukko ''värejä''.
- Jos ryhmä $G$ toimii joukossa $X$, erityisesti jos $G$:n alkiot ovat $X$:n permutaatioita, niin se toimii kaikkien väritysten joukossa $K^X$ siten, että $(a\omega)(x)= \omega(a^{-1}x)$, $a\in G$, $x\in X$.
- Tämä on vasen toiminta koska
- Jos $\Omega\subseteq K^X$ on $X$:n väritysten osajoukko niin $G$ toimii joukossa $\Omega$ mikäli $G\Omega=\Omega$.
- Ryhmän $G$ toiminta väritysten joukossa $\Omega$ määrittelee ekvivalenssirelaation $\Omega$:ssa siten, että $\omega \sim \eta$ jos ja vain jos $\omega =a\eta$ jollakin $a\in G$ ja silloin näitä värityksiä pidetään "samoina".
- Näin ollen $G$:n toiminnan suhteen "erilaisten" väritysten lukumäärä on sama kuin ekvivalenssiluokkien. lukumäärä ja siten sama kuin ratojen lukumäärä $G$:n toiminnassa väritysten joukossa.
Ratojen lukumäärä ryhmän toiminnassa värityksillä [+]
Jos $G$ joukon $X$ permutaatioita ja $G$ toimii joukon $X$ väritysten joukolla $\Omega$, niin G:n toiminnan suhteen ”erilaisten” väritysten lukumäärä eli ratojen lukumäärä on (Burnsiden lemman mukaan) \[ \frac 1{\card{G}}\sum_{a\in G} \card{\Omega_a}, \] missä $\Omega_a=\set{\omega\in \Omega\mid a\omega=\omega} $ on niiden väritysten joukko, jotka ovat invariantteja, eli kiintopisteitä, $a$:n toiminnassa.
Pólyan "väritys"-lause [-]
Olkoon $G$ ryhmä joukon $X$ permutaatioita ja $\zeta_{G,X}(t_1,t_2,\ldots,t_n)$ sen sykli-indeksi. Olkoon $K=\{v_1,v_2,\ldots,v_r\}$ joukko "värejä", joilla $X$:n alkioita väritetään.
Silloin termin \[ v_1^{i_1}\cdot v_2^{i_2}\cdot \ldots \cdot v_r^{i_r}, \] kerroin polynomissa \[ \zeta_{G,X}(v_1^1+\ldots+v_r^1,v_1^2+\ldots+ v_r^2,\ldots,v_1^n+\ldots +v_r^n) \] on niiden $X$:n väritysten lukumäärä, joissa väriä $v_j$ käytetään täsmälleen $i_j$ kertaa (eli $\card{\set{x\in X\mid \omega(x)=v_j}}=i_j$) ja jotka eivät ole ekvivalentteja $G$:n toiminnassa.
Jos käytetään $r$ väriä mutta muita rajoituksia ei ole niin $G$:n toiminnassa ei-ekvivalenttien väritysten lukumäärä on \[ \zeta_{G,X}(r,r,\ldots,r). \]
Esimerkki: $4$-kulmion symmetriat ja väritys [+]
Olkoon $X=\{0,1,2,3\}$. Koska joukossa $X$ on $4$ alkiota niin on olemassa $4!=24$ joukon $X$ permutaatiota. Mutta jos $X$:n alkiot ovat vasemmalla olevan verkon solmut ja jos vaadimme permutaatiolta $a$, että jos $x$ ja $y$ ovat naapureita, eli niiden välillä on kaari, niin myös $a(x)$ ja $a(y)$ ovat naapureita (eli vaadimme, että $a$ on verkko-isomorfismi) niin tilanne muuttuu.
Tässä tapauksessa $0$ voi kuvautua mille tahansa solmulle $0$, $1$, $2$ tai $3$. Mutta $a(1)$:n on oltava $a(0)$:n naapuri josta seuraa, että $a(1)=\Mod(a(0)+1,4)$ tai $\Mod(a(0)-1,4)$. Koska $a(2)$ ei saa olla $a(0)$:n naapuri niin $a(2)=\Mod(a(0)+2,4)$ ja samoin $a(3)=\Mod(a(1)+2,4)$.
Toisella tavalla: Verkkoa voi pyörittää "keskipisteen" ympäri $0$, $90$, $180$ tai $270$ astetta tai peilata $x$-akselin, $y$-akselin, suoran $y=x$ tai suoran $y=-x$ suhteen (kun ''keskipiste valitaan origoksi).
Meillä on siis seuraavat permutaatiot syklinotaatiolla: $(0)$, $(1\; 3)$, $(0\; 1\; 2\; 3)$, $(0\; 1)(2\; 3)$, $(0\; 2)(1\; 3)$, $(0\; 2)$, $(0\;3\;2\;1)$ ja $(0\; 3)(1\; 2)$ joista siis $(0)$, $(0\; 1\; 2\; 3)$, $(0\; 2)(1\; 3)$ ja $(0\;3\;2\;1)$ ovat rotaatioita ja $(1\; 3)$, $(0\; 1)(2\; 3)$, $(0\; 2)$ ja $(0\; 3)(1\; 2)$ peilauksia.
Näytä permutaatio:
Näiden permutaatioiden muodostama ryhmä on ns. diedriryhmä ja sitä merkitään $D_4$:llä (tai $D_{8}$:lla).
Seuraavaksi käytämme Pólyan lausetta laskemaan monellako tavalla voimme värittää solmut niin, että yksi on musta, yksi valkoinen ja kaksi punaista. Lisäksi pidämme kaksi väritystä samanlaisina jos rotaatiolla ja/tai peilauksella saadaan toinen toisesta. (Tähän ei Pólyan lausetta varsinaisesti tarvita koska on vain kaksi vaihtoehtoa: Punaiset solmut ovat joko vierekkäin tai vastakkain.)
Tätä varten meidän pitää ensin laskea ryhmän $D_4$ sykli-indeksi joka saadaan permutaatioiden sykli-indeksien keskiarvona ja permutaation sykli-indeksi on $t_1^{j_1}t_2^{j_1}\ldots t_n^{j_n}$ jos permutaatiolla on $j_k$ rataa, joiden pituus on $k$, $k=1,2,\ldots,n$. Tässä tapauksessa sykli-indeksiksi tulee Erilaisten väritysten lukumäärä on nyt termin $mvp^2$ kerroin polynomissa eli polynomissa \[ \frac 18(m+v+p)^4+ \frac 14 (m+v+p)^2(m^2+v^2+p^2)\\ +\frac 38(m^2+v^2+p^2)^2+ \frac 14(m^4+v^4+p^4) \] ja se on \[ \frac 18 \cdot \frac{4!}{1!\cdot 1!\cdot 2!} + \frac 14 \cdot 2+0+0=2. \]
Esimerkki: Pólyan lause ja ristinolla [+]
Meillä on $3\times 3$-ruudukko ja olemme kirjoittaneet $2$:een ruutuun $\B x$:n, $2$:een $\B o$:n ja $5$ ruutua ovat tyhjinä. Tämä on tehtävissä $\binom 9{2,2,5} =756$:lla eri tavalla jos paperi pidetään paikallaan. Mutta jos voimme kiertää paperia kulman $0$, $\frac \pi 2$, $\pi$ tai $\frac {3\pi}2$ verran keskipisteen ympäri niin näiden vaihtoehtojen lukumäärä pienenee ja jotta voisimme systemaattisella tavalla selvittää montako vaihtoehtoa meillä silloin on niin meidän pitää ensin selvittää miten $\frac \pi 2$ kulman rotaation generoima ryhmä toimii ruudukolla ja erityisesti mikä on tämän toiminnan sykli-indeksi. Eli meidän pitää määrittää erilaisten ratojen pituudet. Tulokset ovat seuraavanlaiset:
- Identiteettifunktiolla (rotaatio $0$) on $9$ rataa, joihin kaikkiin kuuluu $1$ ruutu.
- Kierrolla kulman $\frac \pi 2$ verran on $2$ rataa, joilla molemmilla on $4$ ruutua (toinen sisältää kulmaruudut, toinen niiden välillä olevat ruudut) ja $1$ rata johon kuuluu $1$ ruutu (ruutu keskellä). Sama pätee jos kierretään kulman $\frac {3\pi}2$ verran.
- Jos kiertokulma on $\pi$ niin saamme $4$ rataa, joilla molemmilla on $2$ ruutua (vastakkaiset kulmat ja vastakkaiset ruudut niiden välillä) sekä $1$ rata johon kuuluu $1$ ruutu.
Sykli-indeksiksi saamme näin ollen \begin{equation*} \zeta_{G,X}(t_1,t_2,\ldots ,t_9) = \frac 14 \left (t_1^9 +2t_1t_4^2+t_1t_2^4\right ). \end{equation*}
Jotta voisimme laskea ei-ekvivalenttien ''väritysten'' lukumäärää korvaamme muuttujan $t_j$ lausekkeella $x^j+o^j+t^j$ ja silloin termin $x^2o^2t^5$ kerroin on ei-ekvivalenttien ''väritysten'' lukumäärä kun meillä $2$ kappaletta $\B x$, $2$ kappaletta $\B o$, ja $5$ kappaletta $\B t$. Termin $x^2o^2t^5$ kerroin lausekkeessa $(x+o+t)^9$ on $\dbinom{9}{2,2,5}$, lausekkeesta $2(x+o+t)(x^4+o^4+t^4)^2$ ei tule yhtään $x^2o^2t^5$-termiä ja termin $x^2o^2t^5$ kerroin lausekkeessa $(x+o+t)(x^2+o^2+t^2)^2$ on termin $x^2o^2t^4$ kerroin lausekkeessa $(x^2+o^2+t^2)^2$ eli $\dbinom 4{1,1,2}$. Vaihtoehtojen lukumääräksi tulee siis
Esimerkki: Permutaation toiminta värityksillä ja Pólyan lause [+]
Alla olevan verkon solmut on väritetty värityksellä $\omega$ missä :
Tämän verkon solmujen permutaatiot $a$, jotka ovat sellaisia, että jos solmujen $x$ ja $y$ välillä on kaari, niin myös solmujen $a(x)$ ja $a(y)$ välillä on kaari ovat $(1)$, $(1\; 2)$, $(5\; 6)$, $(1\; 2)(5\; 6)$, $(3\; 4)(1\; 5)(2\; 6)$, $(3\; 4)(1\; 6)(2\; 5)$, $(3\; 4)(1\; 5\; 2\; 6)$ ja $(3\; 4)(1\; 6\; 2\; 5)$. Nämä permutaatiot ovat siis solmujen permutaatioita mutta ne toimivat värityksillä siten, että $a\omega(y)=\omega(a^{-1}y)$.
Näytä väritys $a\omega$ kun $a=$
Tässä tapauksessa ei ole kovin hankalaa löytää kaikki ne $5$ väritystä, jotka eivät ole ekvivalentteja näiden permutaatioiden toiminnassa ja joissa on $3$ punaista ja $3$ vihreätä solmua mutta seuraavaksi määritämme tämän lukumäärän toisella tavalla:
Burnsiden lemman nojalla ratojen lukumäärä ryhmän $G$ toiminnassa joukossa $\Omega$ on $\frac 1{\card{G}}\sum_{a\in G}\card{\Omega_a}$ missä $\Omega_a=\set{\omega \in \Omega\mid a\omega=\omega}$. Tässä tapauksessa $\Omega$ on verkon solmujen väritykset $\omega$, jotka värittävät kolme solmua punaiseksi ja kolme vihreiksi.
Jos nyt $a$ on esimerkiksi permutaatio $(3\; 4)(1\; 5\; 2\; 6)$ niin $\Omega_a=\emptyset$ koska ehdosta $a\omega=\omega$ seuraa, että $\omega$ saa saman arvon radan $\{3,4\}$ solmuilla ja saman arvon radan $\{1,5,2,6\}$ solmuilla ja tämä on mahdotonta jos vaaditaan, että solmuista kolme ovat punaisia ja kolme vihreitä. Tämän permutaation sykli-indeksi on $t_2t_4$ ja jos $t_2$:n paikalle sijoitetaan $p^2+v^2$ ja $t_4$:n paikalle $p^4+t^4$ saadaan polynomi $(p^2+v^2)(p^4+t^4)$ ja tässä polynomissa ei ole yhtään $p^3v^3$-termiä eli $p^3v^3$:n kerroin on $0$.
Jos sen sijaan tarkastelemme permutaatiota $a^2=(1\; 2)(6\; 5)$ niin silloin seuraavat väritykset muodostavat joukon $\Omega_{a^2}$ koska vaatimus on nyt, että kaikki alkiot samalla radalla saavat saman värin ja tässä tapauksessa radat ovat $\{1,2\}$, $\{5,6\}$, $\{3\}$ ja $\{4\}$:
Permutaation $a^2$ sykli-indeksi on $t_1^2t_2^2$ joten tässäkin tapauksessa $\card{\Omega_{a^2}}$ tulee olemaan termin $p^3v^3$ kerroin polynomissa
Ryhmän $G$ sykli-indeksi on $\zeta_{G,V}(t_1,t_2,t_4)=\frac 18\Bigl(t_1^6+t_1^2t_2^2+2t_1^4t_2+2t_2^3+2t_2t_4 \Bigr )$ ja termin $p^3v^3$ kerroin polynomissa $\zeta_{G,V}(p+v,p^2+v^2,p^4+v^4)$ on