Šesta lekcija: Delovanja grup in preštevanje orbit

Pritisnite F11

Iz varnostnih razlogov je mogoče celozaslonski način vključiti samo s pritiskom na gumb F11 na tipkovnici.

Ko ste enkrat v celozaslonskem načinu, ga izključite spet s pritiskom na F11.

Šesta lekcija: Delovanja grup in preštevanje orbit

Avtor: Primož Potočnik

Sodelujoče organizacije

Izvedbo projekta je omogočilo sofinanciranje Evropskega sklada za regionalni razvoj in Ministrstva za visoko šolstvo, znanost in tehnologijo. Pri tehnični izvedbi projekta so sodelovali: Fakulteta za matematiko in fiziko Univerze v Ljubljani, Društvo matematikov, fizikov in astronomov Slovenije ter DMFA-založništvo.

5.1 Permutacije

Bijektivno preslikavo iz množice $\Omega$ v množico $\Omega$ imenujemo tudi permutacija množice $\Omega$ . Ker lahko takšno bijektivno preslikavo enolično predstavimo z urejeno $n$ -terico njenih, paroma različnih slik, je permutacij $n$ -elementne množice natanko toliko kot je vseh takšnih $n$ -teric, torej $n!$ .

Množico vseh permutacij množice $\Omega$ bomo označili s Sym( $\Omega$ ), identično preslikavo iz $\Omega$ v $\Omega$ pa z $id_{\Omega}$ . Za zapis permutacij uporabljamo več različnih načinov, za nas pa bo najprimernejši ciklični zapis permutacije, ki ga bomo predstavili na naslednjem primeru.

Naj bo $\Omega = \{1,2,3,4,5,6\}$ in naj bo $\pi: \Omega \to \Omega$ permutacija podana s

$\pi(1) =3, \pi(2) =6, \pi(3) =5, \pi(4) =4, \pi(5) =1, \pi(6) =2.$

Tedaj je ciklični zapis permutacije $\pi$ enak

$\pi = (1,3,5)(2,6)(4).$

Pri tem števila v prvem oklepaju beremo kot: “ $1$ se preslika v $3$ , $3$ se preslika v $5$ in $5$ se preslika v $1$ ”. Drugi oklepaj bi pomenil: “ $2$ se preslika v $6$ in $6$ se preslika v $2$ ”. Zadnji oklepaj pa se bere kot: “ $4$ se prelika v $4$ ”. Pri tem posameznim “oklepajem” rečemo cikli permutacije, številu elementov v posameznem oklepaju pa dolžina cikla. Seveda ciklični zapis permutacije ni enolično določen: permutacijo $\pi$ bi prav tako lahko zapisali na naslednje načine:

$\pi = (5,1,3)(2,6)(4)= (3,5,1)(6,2)(4)= (6,2)(3,5,1)(4)= (6,2)(4)(3,5,1).$

Kratek premislek pokaže, da lahko permutacijo $\pi$ zapišemo v ciklični obliki na $(3 \cdot 2) \cdot 3! = 18$ načinov.

Kadar je iz konteksta razvidno, katere elemente vsebuje množica $A$ , katere elemente permutacija permutira, cikle dolžine 1 iz cikličnega zapisa permutacije navadno izpuščamo. Tako je običajnejši zapis permutacije $\pi$ naslednji:

$\pi = (1,3,5)(2,6).$

5.2 Množenje permutacij in simetrična grupa

Naj bo $\Omega$ končna množica, in $Sym(\Omega)$ množica vseh permutacij množice $\Omega$ . Obstajata dva standardna načina, kako definirati množenje na $Sym(\Omega)$ :

Ker so permutacije preslikave, jih lahko komponiramo, kot smo to vajeni pri preslikavah. Na primer, če je $\Omega = \{1,2,3,4,5\}$ , $g = (1,3,4)(2,5)$ in $h = (2,4,5)$ , potem je

$g \circ h = (1,3,4,2)$ in $h \circ g = (1,3,5,4).$

Poleg operacije komponiranja $\circ: Sym(\Omega) \times Sym(\Omega) \to Sym(\Omega),\circ: (g,h) \mapsto g \circ h$ pa lahko na množici $Sym(\Omega)$ definiramo še binarno operacijo imenovano komponiranje z desne:

$\cdot : Sym(\Omega) \times Sym(\Omega) \to Sym(\Omega)$ , $\cdot : (g,h) \mapsto h \circ g$ .

Medtem ko je navadno komponiranje uglašeno z običajnim zapisom permutacij, saj velja $(g \circ h)(\alpha) = g(h(\alpha))$ , pa je desno komponiranje uglašeno z eksponentnim zapisom permutacij, saj je

$\alpha^{(g·h)} = (\alpha^g)^h$ , vendar $(g·h)(\alpha) =(h(g(\alpha))$ .

Operacijama $\circ$ in $\cdot$ rečemo tudi levo množenje in desno množenje permutacij.

VAJA: Preveri:

$(1,4,3)(2,5) \circ (1,2)(4,5) =(1,5,3)(2,4).$
$(1,4,3)(2,5) \cdot (1,2)(4,5) =(1,5)(2,4,3).$
$(1,3,5) \cdot (2,4) =(1,3,5)(2,4) =(1,3,5) \circ (2,4).$
$(1,3,4) \cdot (4,5) \ne (1,3,4) \circ (4,5).$

Ker za vsako permutacijo $g \in Sym(\Omega)$ velja $id_{\Omega} \circ g = g \circ id_{\Omega} = g$ in $id_{\Omega} \cdot g = g \cdot id_{\Omega} = g$ ter ker sta obe množenji (tako levo kot desno) asociativni, postane množica $Sym(\Omega)$ , skupaj z vsako od njiju, grupa, v kateri vlogo enote igra permutacija $id_{\Omega}$ .

Definicija 5.1
Grupi $(Sym(\Omega),\circ)$ in $(Sym(\Omega),\cdot)$ imenujemo leva simetrična grupa in desna simetrična grupa množice $\Omega$ in ju označimo s simboloma $Sym_L(\Omega)$ in $Sym_D(\Omega)$ .

Ker smo se odločili za eksponentni zapis permutacij, nam bosta ljubša desno množenje in desna simetrična grupa. Zato bomo grupo $Sym_D(\Omega)$ označevali kar z $S_{\Omega}$ , pikico pri desnem množenju pa, kot je to običajno, izpuščali. Podgrupi grupe $S_{\Omega}$ rečemo permutacijska grupa na množici $\Omega$ .

5.3 Delovanja grup

Dve permutaciji na množici $\Omega$ predstavljata isti element grupe $Sym(\Omega)$ natanko tedaj, ko elemente slikata na enak način. V kombinatoriki pa je velikokrat smiselno opazovati grupe, katerih elementi sicer permutirajo množico $\Omega$ , vendar tako, da smeta dva, sicer različna elementa grupe “delovati” na množici $\Omega$ na enak način. Da bomo lahko obravnavali tudi takšne situacije, vpeljimo pojem “delovanja grupe”.
Naj bo $G$ grupa in $\Omega$ množica. Delovanje grupe $G$ na množici $\Omega$ je poljubna preslikava

$\Phi: \Omega \times G \to \Omega$ , $(\omega,g) \mapsto \omega^g$ ,

ki zadošča pogojema:

$\omega^1 =\omega$ za vse $\omega \in \Omega$ ;
$\omega^{(gh)} = (\omega^g)^h$ za vse $\omega \in \Omega$ in $g,h \in G$ .

Delovanje grupe $G$ na $\Omega$ pa lahko opišemo tudi kot homomorfizem iz $G$ v simetrično grupo $S_{\Omega}$ na naslednji način. Naj bo $\Phi: \Omega \times G \to \Omega$ delovanje.
Definirajmo preslikavo

$\bar{\Phi}: G \to S_{\Omega}$ , $\bar{\Phi}(g) =(\omega \mapsto \omega^g)$ .

Ni se težko prepričati, da je $\bar{\Phi}$ je homomorfizm group.

Obratno, naj bo $\Psi: G \to S_{\Omega}$ poljuben homomorfizem grup. Definiramo delovanje grupe $G$ na $\Omega$ :

$\bar{\Psi}: \Omega \times G \to \Omega$ , $(\omega,g) \mapsto \omega^{\bar{\Psi}(g)}$ .

Pri tem velja naslednje: Če pričnemo z delovanjem $\Phi$ , mu priredimo homomorfizem $\bar{\Phi}$ in temu homomorfizmu spet priredimo delovanje $\bar{\Phi}$ , dobimo natanko začetno delovanje $\Phi$ .

$\bar{\bar\Phi} = \Phi.$

To kaže na to, da lahko delovanje grup enakovredno de?niramo tako, kot smo to storili v teh zapiskih, ali pa kot homomorfizem v simetrično grupo.
Če delovanje grupe $G$ na $\Omega$ predstavimo kot homomorfizem $\Psi: G \to S_{\Omega}$ , potem sliki homomorfizma $\Psi$ rečemo permutacijska reprezentacija grupe $G$ in jo označimo z $G^{\Omega}$ . Opazimo, da je $G^{\Omega}$ permutacijska grupa, ki vsebuje natanko tiste permutacije množice $\Omega$ , ki permutirajo tako, kot permutira kakšen element iz $g$ .

Množici vseh $g \in G$ , ki pribijejo vsak element množice $\Omega$ se imenuje jedro delovanja. Če na delovanje pogledamo kot na homomorfizem $\Psi: G \to S_{\Omega}$ , potem je jedro delovanja ravno jedro homorfizma $\Psi$ .

$Ker(\Psi)=\{g \in G : \Psi(g) =id\}.$

Iz 1. izreka o homomorfizmih iz teorije grup tedaj sledi $G^{\Omega} \equiv G/Ker(\Psi)$ .
Če jedro delovanja vsebuje le nedelavni element grupe, potem je delovanje zvesto. Če $G$ deluje zvesto na $\Omega$ , potem je pripadajoči homomorfizem $G \to S_{\Omega}$ is injektiven, in zato $G^{\Omega} = G$ . V tem smislu lahko zvesta delovanja enačimo s pripadajočimi permutacijskimi grupami.

5.4 Stabilizatorji in orbite delovanja

Naj grupa $G$ deluje na množici $\Omega$ in naj bo $\omega$ poljuben element množice $\Omega$ .
Množici

$G_{\omega} = \{g \in G : \omega^g = \omega\}$

vseh elementov grupe $G$ , ki element $a$ pribijejo, rečemo stabilizator elementa $\omega$ v grupi $G$ , množici slik

$\omega^G = \{\omega^g :g \in G\}$

pa rečemo orbita elementa $\omega$ pri delovanju grupe $G$ .

Za zgled si oglejmo klasični primer iz teorije grup. Za poljubno grupo $G$ in elementa $g,h \in G$ definirajmo

$h^g =g^{-1}hg.$

Z lahkoto se prepričamo, da smo s tem definirali delovanje grupe $G$ na množici $\Omega = G$ , ki ga imenujemo delovanje grupe $G$ na sebi s konjugacijo. Stabilizator $G_h$ elementa $h$ pri tem delovanju vsebuje vse tiste elemente $g \in G$ , za katere velja $g^{-1}hg = h$ , torej tiste $g \in G$ , ki komutirajo s $h$ . Podobno, element $g \in G$ leži v jedru tega delovanja, če in samo če velja $g^{-1}hg = h$ za vsak $h \in H$ , torej če in samo če leži $g$ v centru grupe $G$ . Orbite $h^G$ imenujemo konjugiranostni razredi elementov grupe $G$ .
Definiramo lahko tudi delovanje grupe $G$ na množici $\Omega = \{H : H \le G\}$ vseh njenih podgrup s predpisom:

$H^g = g^{-1}Hg = \{g^{-1}hg :h \in H\}.$

Grupi $H^g$ pri tem rečemo konjugiranka grupe $H$ . Stabilizator $G_H$ podgrupe $H \in \Omega$ je enak normalizatorju grupe $H$ v $G$ .

Trditev 5.2
Naj grupe $G$ deluje na množici $\Omega$ . Tedaj za poljubna elementa $g \in G$ in $\omega \in \Omega$ velja

$G_{(\omega^g)} = (G_{\omega})^g.$

Stabilizatorja dveh elementov množice $\Omega$ , ki ležite v isti orbiti grupe $G$ , sta torej konjugirana.

Dokaz

Trditev 5.3
Množica orbit pri delovanju grupe $G$ na množici $\Omega$ predstavlja razbitje množice $\Omega$ .

Dokaz

Trditev 5.4
Naj grupa $G$ deluje na množici $\Omega$ in naj bo $\omega$ poljuben element množice $\Omega$ . Tedaj velja enakost

$\arrowvert G_{\omega} \arrowvert \arrowvert \omega^G \arrowvert = \arrowvert G \arrowvert.$

Dokaz

Opomba

Definicija 5.5
Delovanje grupe $G$ na množici $\Omega$ je tranzitivno, če je $\omega^G = \Omega$ za nek (in tedaj vsak) $\omega \in \Omega$ .

Dokaz

Vzemimo poljuben element $h \in G$ . Tedaj trditev neposredno sledi iz naslednje verige ekvivalenc:

$h \in G_{\omega} \Leftrightarrow \omega^h = \omega \Leftrightarrow \omega^{gg^{-1}hg} = \omega^g \Leftrightarrow g^{-1}hg \in G_{(\omega^g)}.$

Dokaz

Ker vsak element množice $\omega$ leži v orbiti $\omega^G$ , je unija vseh orbit pri delovanju grupe $G$ enaka $\Omega$ . Naj bosta $\omega^G$ in $\beta^G$ orbiti z nepraznim presekom. Dokazati moramo, da sta tedaj enaki. Res. Naj bo $\gamma \in \omega^G \cap \beta^G$ in naj bo $\delta$ poljuben element orbite $\omega^G$ . Tedaj obstajajo elementi $g,h,t \in G$ , da je $\gamma = \omega^g = \beta^h$ in $\delta = \omega^t$ . Sledi $\delta = \omega^t = (\beta^{hg^{-1}})^t = \beta^{hg^{-1}t}$ . S tem smo dokazali, da je $\omega^G \subseteq \beta^G$ . Če zamenjamo vlogi $\omega$ in $\beta$ , dokažemo vsebovanost še v drugo smer in s tem enakost orbit $\omega^G$ in $\beta^G$ . Orbite pri delovanju grupe $G$ torej res tvorijo razbitje množice $\Omega$ .

Dokaz

Označimo z $G(\omega \mapsto \beta)$ množico elementov grupe $G$ , ki preslikajo točko $\omega$ v izbrano točko $\beta$ množice $\Omega$ . Če $\beta$ ni element orbite $\omega^G$ , potem je množica $G(\omega \mapsto \beta)$ prazna. Predpostavimo sedaj, da je $\beta \in \omega^G$ , izberimo element $g \in G(\omega \mapsto \beta)$ in definirajmo preslikavo $f: G(\omega \mapsto \beta) \to G$ s predpisom $f(h) = hg^{-1}$ . Z lahkoto se prepričamo, da je preslikava $f$ injektivna in da je njena slika enaka stabilizatorju $G_{\omega}$ . Zato je moč množice $G(\omega \mapsto \beta)$ enaka redu stabilizatorja $G_{\omega}$ , brž ko $\beta$ pripada orbiti $\omega^G$ , in je enaka $0$ , če leži $\beta$ zunaj $\omega^G$ .
Seštejemo sedaj moči množic $G(\omega \mapsto \beta)$ po vseh $\beta \in \Omega$ in vsoto označimo z $S$ . K vsoti $S$ prispevajo le tisti elementi $\beta$ , ki ležijo v orbiti $\omega^G$ – vsak takšen natanko $\arrowvert G_{\omega} \arrowvert$ . Zato je ta vsota enaka $\arrowvert G_{\omega}\arrowvert \arrowvert \omega^G \arrowvert$ . Po drugo strani pa vsak element $g$ grupe $G$ leži v natanko eni množici $G(\omega \mapsto \beta)$ , namreč tisti pri kateri je $\beta = \omega^g$ . Zato je vsota $S$ enaka tudi $\arrowvert G \arrowvert$ . S tem je dokaz končan.

Opomba

Prijemu, ki smo ga uporabili v zgornjem dokazu, v kombinatoriki pogosto rečemo računovodsko pravilo (angl. counting principle). Računovodsko pravilo pravi, da je vsota elementov dane matrike enaka tako vsoti njenih vrstičnih vsot kot tudi vsoti njenih stolpčnih vsot. Pravilo lahko v zgornjem dokazu uporabimo na sledeč način: Definiramo matriko, katere vrstice so indeksirane z elementi množice $\Omega$ , stolpci z elementi grupe $G$ , na presečišču vrstice $\beta \in \Omega$ ter stolpca $g \in G$ pa stoji $0$ ali $1$ , odvisno od tega ali je $g \in G(\omega \mapsto \beta)$ ali ne. Vrstična vsota pri elementu $\beta \in \Omega$ je tedaj enaka $\arrowvert G(\omega \mapsto \beta) \arrowvert$ , vse stolpčne vsote pa so enake $1$ .

5.5 Preštevanje orbit in Cauchy-Frobeniusova lema

Pri preštevanju kombinatoričnih objektov nam je velikokrat v pomoč preprosta, vendar uporabna formula za izračun števila orbit grupe, ki se v literaturi pogosto pojavlja z imenom Burnsidova lema, ali pa (zgodovinsko pravilneje) Cauchy-Frobeniusova lema. Poglejmo, kaj pravi.

Izrek 5.6 (Cauchy-Frobeniusova lema)
Naj grupa $G$ deluje na množici $\Omega$ in naj $m$ označuje število orbit tega delovanja. Za element $g \in G$ naj $Fix(g)$ predstavlja množico elementov $\Omega$ , ki jih element $g$ pribije. Tedaj velja enakost

$m \arrowvert G \arrowvert = \sum_{g \in G} \arrowvert Fix(g) \arrowvert.$

Dokaz

Naj bodo $\Omega_1,...,\Omega_m$ orbite delovanja grupe $G$ na $\Omega$ . Oglejmo si množico

$\mathcal{M}=\{(a,g) :a \in \Omega, g \in G_a\}$

in preštejmo njene elemente na dva načina. Najprej opazimo, da je moč množice $\mathcal{M}$ enaka vsoti moči stabilizatorjev $G_a$ po vseh $a \in \Omega$ . Vemo tudi, da je moč stabilizatoja $\arrowvert G_a \arrowvert$ enaka $\arrowvert G \arrowvert / \arrowvert \Omega_i \arrowvert$ , kjer je $\Omega_i$ tista orbita, ki vsebuje element $a$ . Zato

$\arrowvert \mathcal{M} \arrowvert = \sum_{a \in \Omega} \arrowvert G_a \arrowvert = \sum^m_{i=1} \sum_{a \in \Omega_i} \frac{\arrowvert G \arrowvert}{\arrowvert \Omega_i \arrowvert} = \sum^m_{i=1} \arrowvert G \arrowvert = m \arrowvert G \arrowvert.$

Po drugi strani pa lahko elemente množice $\mathcal{M}$ preštejemo tako, da seštejemo moči množic

$\mathcal{M}_g =\{(a,g) :a \in \Omega, g \in G_a\}=\{(a,g) :a \in Fix(g)\}.$

Zato

$\arrowvert \mathcal{M} \arrowvert = \sum_{g \in G} \arrowvert \mathcal{M}_g \arrowvert = \sum_{g \in G} \arrowvert Fix(g) \arrowvert.$

S tem je izrek dokazan.

5.6 Delovanje grupe na funkcijah

Pričnimo z zgledom. Oglišča pravilnega šestkotnika bi radi pobarvali s tremi barvami: belo, rdečo in modro. Na koliko načinov lahko to storimo, če imamo dve barvanji enaki, brž ko lahko iz enega preidemo v drugega s pomočjo vrtenja šestkotnika okoli njegovega središča?
Prevedimo nalogo v matematični jezik. Označimo oglišča šestkotnika s števili $1,...,6$ , začenši z $1$ in nadaljujoč v pozitivni smeri z $2$ , $3$ itd. Barvanje šestkotnika si lahko predstavljamo kot funkcijo iz množice oglišč $N = \{1,...,6\}$ v množico barv $K = \{B,R,M\}$ .
Naj bo $G$ grupa vrtenj šestkotnika, predstavljena kot permutacijska grupa na množici oglišč. Če barvanje $\varphi: N \to K$ “zavrtimo” z rotacijo $g \in G$ , potem dobimo načeloma drugačno barvanje $\varphi^g: N \to K$ določeno s pravilom $\varphi^g(a) = \varphi(a^{g^{-1}})$ . Dve barvanji $_{\varphi1, \varphi2}: N \to K$ sta torej “enaki”, če obstaja permutacija $g \in G$ , za katero je ${_{\varphi2}} = {_{\varphi1}}^g$ . Ni težko videti, da je preslikava $K^N \times G \to K^N$ , $(\varphi,g) \mapsto \varphi^g$ , delovanje grupe $G$ na množici $K^N$ .
Iz zgoraj povedanega sledi, da sta dve barvanji šestkotnika “enaki” natanko tedaj, ko sta v isti orbiti tega delovanja. Če želimo rešiti zastavljeno nalogo, moramo torej prešteti število orbit induciranega delovanja grupe $G$ na $K^N$ . Odgovor ponuja naslednja posledica Cauchy-Frobeniusove leme.

Izrek 5.7
Naj bosta $N$ in $K$ končni množici in naj končna grupa $G$ deluje na množici $N$ . Za vsak $g \in G$ naj $c(g)$ označuje število orbit grupe $\langle g \rangle$ na množici $N$ . Tedaj je število orbit delovanja grupe $G$ pri njenem naravnem delovanju na množici preslikav $K^N$ enako

$\frac{1}{\arrowvert G \arrowvert} \sum_{g \in G} \arrowvert K \arrowvert^{c(g)}.$

Dokaz

Spomnimo se, da grupa $G$ deluje na množici $K^N$ funkcij iz $N$ v $K$ v skladu z naslednjim predpisom:

$\varphi^g(a) = \varphi(a^{g^{-1}})$ , $\varphi \in K^N$ , $g \in G$ , $a \in N$ .

Ni težko videti, da element $g \in G$ pribije funkcijo ${\varphi}: N \to K$ natanko tedaj, ko je $\varphi$ konstantna na vsaki orbiti grupe $\langle g \rangle$ . Takšna funkcija je enolično določena z naborom $c(g)$ elementov iz $K$ . Zato je funkcij, ki so konstantne na vsaki orbiti grupe $\langle g \rangle$ natanko $\arrowvert K \arrowvert^{c(g)}$ . Z drugimi besedami, $Fix(g) = \arrowvert K \arrowvert^{c(g)}$ . Če označimo število orbit grupe $G$ na $K^N$ z $m$ in uporabimo Cauchy-Frobeniusovo lemo (Izrek 5.6), dobimo

$m \arrowvert G \arrowvert = \sum_{g \in G} Fix(g) = \sum_{g \in G} \arrowvert K \arrowvert^{c(g)}.$

Zgornjo enakost delimo z $\arrowvert G \arrowvert$ in dobimo enakost, ki jo dokazujemo.

Kazalo

5.1 Permutacije
5.2 Množenje permutacij in simetrična grupa
5.3 Delovanja grup
5.4 Stabilizatorji in orbite delovanja
5.5 Preštevanje orbit in Cauchy-Frobeniusova lema
5.6 Delovanje grupe na funkcijah

Nazaj

Zapri

Pomoč
Komentarji
Velikost črk
Zapiski
Za učitelja
Natisni

Natisni trenutno prosojnico
Natisni celotno gradivo

Naprej

Šesta lekcija: Delovanja grup in preštevanje orbit

Vaš brskalnik je zastarel

Pritisnite F11

Šesta lekcija: Delovanja grup in preštevanje orbit

Avtor: Primož Potočnik

Sodelujoče organizacije

Hvala za ogled gradiva!

Veseli bomo vaših komentarjev. Obiščite nas na www.nauk.si.

Sodelujoče organizacije

Dokaz

Dokaz

Dokaz

Opomba

Dokaz

Dokaz