szyfrowanie

Nasza ocena:

5
Pobrań: 14
Wyświetleń: 777
Komentarze: 0
Notatek.pl

Pobierz ten dokument za darmo

Podgląd dokumentu
szyfrowanie - strona 1 szyfrowanie - strona 2 szyfrowanie - strona 3

Fragment notatki:


Wyklad 7 13 listopada 2012 1 Lemat Burnside’a Twierdzenie 1.1 (Lemat Burnside’a) Niech G bedzie grupa sko´ nczona dzia- lajaca na zbiorze sko´ nczonym X. W´ owczas liczba N orbit zbioru X ze wzgledu na G wynosi N = 1 |G| g∈G |F ix g| W dowodzie lematu Burnside’a korzystamy z Bardzo Wa˙znego Twierdzenia udowodnionego podczas wykladu poprzedniego. Dla wygody przypominam wiec to twierdzenie (w postaci, kt´ ora nazwali´ smy wnioskiem). Wniosek 1.2 Je´ sli sko´ nczona grupa G dziala na zbiorze X, w´ owczas dla ka˙zdego x ∈ X |G| = |Gx| · |Orb x| (1) Dow´ od Lematu Burnside’a przeprowadzimy metoda, kt´ ora w kombina- toryce jest znana pod nazwa metody podw´ ojnego zliczania. Ta metoda polega na oczywistej zasadzie, ˙ze je´ sli liczymy liczno´ s´ c jakiego´ s zbioru na dwa sposoby to wynik za ka˙zdym razem musi by´ c ten sam (oczywi´ scie zakladamy, ˙ze obie metody sa poprawne). Policzymy liczbe element´ ow zbioru S = {(x, g) ∈ X × G : g(x) = x} Utw´ orzmy zero-jedynkowa macierz M = (mg,x)g∈G,x∈X zdefiniowana wzo- rem mg,x = 1 je´ sli g(x) = x 0 je´ sli g(x) = x O takiej macierzy m´ owimy, ˙ze ma wiersze indeksowane elementami zbioru G, za´ s kolumny indeksowane elementami zbioru X. Liczba element´ ow zbioru S jest oczywi´ scie r´ owna liczbie jedynek w macierzy M . Liczbe te mo˙zna obliczy´ c na dwa sposoby. 1 2 PODGRUPY NORMALNE 2 Spos´ ob 1. Sumujemy wyrazy w ka˙zdym wierszu macierzy S otrzymujac dla wiersza o indeksie g x∈X mg,x = |F ix g| a nastepnie liczymy sume wszystkich wierszy i mamy w wyniku |S| = g∈G |F ix g| Spos´ ob 2. Sumujemy wyrazy w ka˙zdej z kolumn otrzymujac dla kolumny o ideksie x g∈G mg,x = |Gx| i nastepnie sumujemy po wszystkich x ∈ X co daje w wyniku |S| = x∈X |Gx| Powiedzmy, ˙ze mamy N orbit (rozlacznych i dajacych w sumie caly zbi´ or X) O1, O2, ..., ON . Mo˙zemy teraz napisa´c g∈G |F ix g| = x∈X |Gx| = N i=1( x∈Oi |Gx|) Dla ka˙zdej z orbit Oi wybierzmy (dokladnie jeden) element xi ∈ Oi. Skoro, na mocy wniosku 1.2, dla ka˙zdego x ∈ X prawdziwy jest wz´ or |Gx| · |Orb x| = |G|, mamy tak˙ze |Gx| = |Gx i | dla ka ˙ zdego x ∈ Oi. Stad (i korzystajac ponownie z wniosku 1.2) otrzymujemy g∈G |F ix g| = N i=1(|Oi| · |Gxi |) = N · |G| Co ko´ nczy dow´ od naszego twierdzenia. 2 Podgrupy normalne Ju˙z wiemy (dowiedzieli´ smy sie tego przy okazji dowodu twierdzenia Lagrange’a), ˙ze dla dowolnej podgrupy H grupy multyplikatywnej G relacja:

(…)

… przez element a ∈ G nazywamy
z
zbi´r aAa−1 .
o
Twierdzenie 3.1 Je´li H jest podgrupa grupy G, g ∈ G, w´wczas gHg −1 jest
s
o
podgrupa grupy G.
4
TWIERDZENIA SYLOWA
4
Twierdzenie 3.2 Niech G bedzie grupa i H podgrupa grupy G. H jest podgrupa normalna grupy G wtedy i tylko wtedy gdy gHg −1 = H dla ka˙ dego g ∈ G.
z
Normalizatorem podgrupy1 H w grupie G nazywamy zbi´r
o
NG (H) = {g ∈ G : gHg −1 = H}
Twierdzenie…
... zobacz całą notatkę

Komentarze użytkowników (0)

Zaloguj się, aby dodać komentarz