Grupa permutacija

#fax #math #alg #laag [deo poglavlja "grupa"]

Def. je skup svih permutacija skupa , tj. skup svih bijekcija .
Ako je označavamo sa .

Ako je kompozicija funkcija, onda je grupa:

  • važi asocijativnost
  • neutral je funkcija , takva da
  • za svaku permutaciju , postoji obratna


Stav. Ako postoji bijekcija među skupovima i , onda

tada označavamo

Def. Permutacija, u kojoj , gde su svi različiti, a svi ostali se slikaju sami u sebe, zovemo ciklus dužine , a skup je nosač tog ciklusa.
Oznaka:

Stav. Red ciklusa dužine je .

Def. Ciklus dužine dva zove se transpozicija.

Def. Ciklusi su disjunktni ako su njima nosači disjunktni.

Stav. Ako su svi različiti onda

Teorema. Svaka permutacija iz može se predstaviti na jedinstven način (do na redosled) kao kombinacija disjunktnih ciklusa.

Stav. Svaka permutacija iz može se predstaviti kao kombinacija transpozicija.

Primeri:

  • Permutaciju predstavimo kao
    — kombinaciju disjunktnih ciklusa:
    — kombinaciju transpozicija:
  • Svi predstavnici ciklusa dužine 4 u :

Parnost permutacije

Def. Inverzija permutacije je par za koji važi i ,

— broj inverzija permutacije.

je parna permutacija ako je paran broj,
je neparna permutacija ako je neparan broj.

Stav. Ako je permutacija predstavljena kombinacijom parnog/neparnog broja transpozicija, onda je ona parna/neparna.

Ciklus dužine je parna/neparna permutacija ako je neparan/paran broj.


Skup svih parnih permutacija u je grupa

Stav.

Dokaz:
Skup parnih permutacija je podskup skupa permutacija.
mogu biti predstavljeni kao kompozicija parnog broja transpozicija.
Stoga i se predstavlja kompozicijom parnog broja transpozicija, tj. .
Imamo da je podgrupa od .

Neka je proizvoljna transpozicija, definišemo funkciju sa , koja jeste bijekcija, tada
Imamo da

Svojstva i

Lema. . Tada

Dokaz:
Jasno je da jednakost važi primenom fja na svaki .
Razmatramo primenu fja na :
Neka je i neka
Sa leve strane:
Sa desne strane:


Stav. Grupa je generisana:

  1. transpozicijama
  2. transpozicijama
  3. permutacijama i

Dokaz:

  1. Pokažemo da



    Tako možemo predstaviti svaku transpoziciju, a iz stava svaku permutaciju je moguće predstaviti kao kombinaciju transpozicija.
  2. Treba pokazati da je moguće izraziti svaku od transpozicija iz kao kombinaciju transpozicija iz
    Indukcijom:
    baza: već je izražena.
    hipoteza: neka je izražena .
    korak: pokazati da možemo izraziti i .




    Svaku permutaciju možemo izraziti kao kombinaciju transpozicija iz , a svaku od njih možemo izraziti transpozicijama iz
  3. Treba pokazati da je moguće izraziti svaku od transpozicija iz kao kombinaciju i .
    Indukcijom:
    baza: već je izražena.
    hipoteza: neka je izražena .
    korak: pokazati da možemo izraziti i .






    Izražavanje permutacije: kombinacija proizvoljnih transpozicija -> -> ->


Stav. Za grupa je generisana ciklusima dužine 3.

Dokaz: jeste generisan ciklusima dužine 3.
Iz dela prethodnog stava svaki element možemo dobiti kombinacijom navedenih transpozicija.
Jer , svaki element možemo razviti na paran broj transpozicija oblika .
Primenom na svaki uzastopni par, dobijamo tvrđenje.


Posledica. Ako su i disjunktni ciklusi iz , onda

Napomena: Ako su disjunktni ciklusi iz , onda

Napomena: Grupa i neka podgrupa grupe su izomorfni.