Plan wykładu
Algebra z geometriÄ…
1 Struktury algebraiczne
Struktury algebraiczne
2 Główne typy struktur algebraicznych
3 Évariste Galois
4 Grupy
Adam DÄ…browski
5 Grupy abelowe
6 Niels Henrik Abel
Politechnika Poznańska
Wydział Informatyki
7 Pierścienie i ciała
Katedra Sterowania i Inżynierii Systemów
8 Ciała skończone (ciała Galois)
Pracownia Układów Elektronicznych i Przetwarzania Sygnałów
9 Moduł, przestrzeń wektorowa i algebra
11 pazdziernika 2010 10 Odwzorowania wzajemnie jednoznaczne zbioru na siebie
11 Grupy odwzorowań
0
1 12 Grupy permutacji
2
13 Działania na permutacjach
3
14 Transpozycje i permutacje cykliczne
4
15 Permutacje parzyste i nieparzyste
5
16 Studenckie Koło Naukowe Decybel
0 1 2 3 4 5
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 1 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 2 / 127
Struktura algebraiczna Główne typy struktur algebraicznych
Wyróżnia się siedem podstawowych typów struktur algebraicznych
Definicja
o hierarchicznie rosnącym stopniu skomplikowania: półgrupy, grupy,
Strukturą algebraiczną określoną w zbiorze A nazywa się zestaw
pierścienie, ciała, moduły, przestrzenie wektorowe i algebry. Pojęcia te
wprowadziÅ‚ do matematyki Évariste Galois.
(A, F1, F2, . . . , Fn, h1, h2, . . . , hm, g1, g2, . . . , gn)
W półgrupach i grupach występuje tylko jedno działanie wewnętrzne,
złożony ze zbioru A, zbiorów F1, F2, . . . , Fn, działań wewnętrznych w pierścieniach i ciałach dwa działania wewnętrzne. W pozostałych
trzech typach struktur algebraicznych jest jedno działanie zewnętrzne, przy
h1 : A × A A, h2 : A × A A, . . . , hm : A × A A ,
czym w modułach i przestrzeniach wektorowych wystepuje wraz z jednym
działaniem wewnętrznym, a w algebrach z dwoma działaniami
i działań zewnętrznych
wewnętrznymi.
g1 : F1 × A A, g2 : F2 × A A, . . . , gn : Fn × A A .
Najprostszą strukturą algebraiczną jest półgrupa.
Uwagi
Definicja półgrupy
Zazwyczaj zakłada się, że wymienione działania spełniają szereg warunków:
PółgrupÄ… nazywa siÄ™ zestaw (A, ×) zÅ‚ożony ze zbioru A i okreÅ›lonego w
łączność, przemienność, istnienie elementu neutralnego, istnienie
nim dziaÅ‚ania × , przy czym to dziaÅ‚anie jest Å‚Ä…czne.
elementów odwrotnych, rozdzielność jednych działań względem drugich.
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 3 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 4 / 127
Évariste Galois Trudny egzamin wstÄ™pny na PolitechnikÄ™ w Paryżu
Évariste Galois
Évariste Galois
Évariste Galois zginÄ…Å‚ w niewyjaÅ›nionych okolicznoÅ›ciach w wieku 21 lat,
być może w pojedynku, choć istnieje podejrzenie, że został zamordowany
Évariste Galois urodziÅ‚ siÄ™ 25. pazdziernika 1811 r. w Bourg-la-Reine k.
za sympatie republikańskie, a pojedynek jedynie upozorowano. Dwa razy
Paryża, a zmarł 31. maja 1832 r. w Paryżu francuski matematyk znany
był więziony za wystąpienia przeciw królowi Ludwikowi Filipowi.
z wielkich osiągnięć w dziedzinie algebry.
Ostatniej nocy przed śmiercią spisał swoje najważniejsze osiągnięcia
Twórca teorii grup oraz nowoczesnej teorii równań algebraicznych (teoria
matematyczne i dzięki temu przetrwały.
Galois). Pierwszy wprowadził pojęcie grupy, podgrupy i ciała. Ciała
Ten genialny matematyk dwukrotnie nie zdał egzaminu wstępnego do
skończone noszą nazwę ciał Galois.
l École Polytechnique w Paryżu.
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 5 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 6 / 127
Grupy Grupy abelowe
Definicja grupy
Definicja grupy abelowej
Zbiór G, a Å›ciÅ›lej zestaw (G, ·), w którym jest okreÅ›lone jedno dziaÅ‚anie
Grupę nazywa się abelową lub przemienną, jeśli oprócz trzech warunków
nazywa się grupą o ile są spełnione następujące warunki:
definiujacych grupę jest dodatkowo spełniony czwarty warunek:
dla dowolnych elementów a, b, c " G działanie jest łączne, tzn.
dla dowolnych elementów a, b " G działanie jest przemienne, tzn.
zachodzi równość
zachodzi równość
(a · b) · c = a · (b · c)
a · b = b · a
w G istnieje element neutralny e, tzn. dla każdego a " G są spełnione
Uwaga
równości
Działanie rozpatrywane w strukturze algebraicznej nazywanej grupą
a · e = e · a = a
oznaczano do tej pory przez · lub × czyli jak mnożenie. JeÅ›li jednak
dla każdego elementu a " G istnieje element odwrotny a " G taki, że
działanie to jest przemienne, czyli grupa jest abelowa, stosuje się często
oznaczenie dodawania + .
a · a = a · a = e
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 7 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 8 / 127
Niels Henrik Abel Niels Henrik Abel
Po śmierci ojca w 1820 roku musiałby przerwać naukę w szkole i zająć się
zarobkowaniem na utrzymanie matki i rodzeństwa, na szczęście Holmboe
pomógł mu uzyskać stypendium i rok pózniej Abel mógł podjąć studia
wyższe na Uniwersytecie w Christianii, które ukończył w 1822. W roku
1823 przebywał przez 29 dni na wyspie Jan Mayen należącej do Norwegii,
gdzie żył w odosobnieniu od świata zewnętrznego. W latach 1825-1827
Niels Henrik Abel (ur. 5 sierpnia 1802 r. w Findö koÅ‚o Stavanger,
przebywał na koszt państwa w Berlinie i Paryżu. Od 1827 roku był
Norwegia, zm. 6 kwietnia 1829 r. w Frolandsvark pod Arendal),
docentem uniwersytetu w Christianii. Jeszcze w szkole Abel podjÄ…Å‚
matematyk norweski. Udowodnił niemożliwość rozwiązania równania
badania nad rozwiązaniem równań piątego stopnia przez pierwiastniki,
algebraicznego stopnia wyższego niż cztery przez pierwiastniki, prowadził
następnie zainteresował się równaniami całkowymi i całkami eliptycznymi,
badania w dziedzinie teorii szeregów i całek eliptycznych.
które doprowadziły go do funkcji eliptycznych. W 1824 r. podjął na nowo
Pochodził z biednej rodziny. Uczył się w szkole katedralnej w Christianii
badania nad rozwiązalnością równań algebraiczych stopnia 5 i przy pomocy
(obecnie Oslo) i od najmłodszych lat wykazywał wielkie zdolności
stworzonej niezależnie od Galois teorii grup udało mu się udowodnić, że w
matematyczne. W wieku 15 lat pod kierunkiem swego nauczyciela Bernta
ogólnym przypadku równanie takie nie daje się rozwiązać przez
Holmboe a Abel zaczął studiować matematykę wyższą, czytając dzieła
pierwiastniki. Inne jego prace dotyczyły zbieżności szeregów liczbowych i
Eulera, Lagrange a i Laplace a. W wieku lat 16 udało mu się udowodnić
potęgowych.
wzór dwumianowy dla dowolnego wykładnika rzeczywistego.
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 9 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 10 / 127
Niels Henrik Abel Pierścień
Definicja pierścienia
Zestaw (A, +, ·), w którym sÄ… okreÅ›lone dwa dziaÅ‚ania (dodawanie
i mnożenie) nazywa się pierścieniem o ile są spełnione warunki:
dodawanie jest Å‚Ä…czne i przemienne,
w zbiorze A istnieje element neutralny dla dodawania, czyli 0,
"a"A"-a"A a +(-a) =(-a) +a = 0 ,
mnożenie jest łączne,
mnożenie jest rozdzielne względem dodawania, czyli
W 1829 Uniwersytet Berliński, w uznaniu jego zasług, zaproponował mu
objęcie katedry matematyki. Niestety, kilka dni po otrzymaniu tej
"a,b,c"A a(b + c) =ab + ac
wiadomości Abel zmarł na gruzlicę, której nabawił się wskutek złych
warunków życia w dzieciństwie i młodości.
oraz
W 2001 r. rząd Norwegii zdecydował o ustanowieniu Nagrody Abela, która
"a,b,c"A (a + b)c = ac + bc
jest przyznawana za najwybitniejsze osiągnięcia w dziedzinie matematyki.
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 11 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 12 / 127
Ciało Ilorazowe struktury algebraiczne
Dzięki relacji równoważności R elementów zbioru A, działania w nim
zdefiniowane zawężamy do odpowiednich działań w zbiorze ilorazowym
Definicja ciała
A/R, czyli tworzymy tzw. ilorazowÄ… strukturÄ™ algebraicznÄ….
Zestaw (A, +, ·), w którym sÄ… okreÅ›lone dwa dziaÅ‚ania (dodawanie
i mnożenie) nazywa się ciałem o ile są spełnione warunki:
Przykład
definiowana struktura jest pierścieniem, Przekształcając pierścień liczb całkowitych Z za pomocą relacji
parzystości, oznaczanej symbolem mod 2, otrzymuje się tzw. strukturę
mnożenie jest przemienne,
binarną ze zbiorem ilorazowym Z/mod 2 = {0, 1}, oznaczanym w skrócie
w zbiorze A istnieje element neutralny dla mnożenia, czyli 1,
przez Z2. Dodawanie i mnożenie określają tabelki:
"a"A\{0}"a-1 a · a-1 = a-1 · a = 1 .
"A + 0 1 · 0 1
0 0 1 0 0 0
Przykład
1 1 0 1 0 1
Zbiór liczb całkowitych z dodawaniem i mnożeniem tworzy pierścień.
Zbiory liczb wymiernych, rzeczywistych i zespolonych tworzą ciała z tymi
Nadając symbolom 0 i 1 znaczenie stanów logicznych odpowiednio fałsz
działaniami.
i prawda , dodawanie + nazywa siÄ™ operacjÄ… xor (po polsku albo)
a mnożenie · nazywa siÄ™ operacjÄ… and (po polsku i).
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 13 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 14 / 127
Arytmetyki modularne Skończone struktury algebraiczne
Relację parzystości mod 2 można uogólnić na dowolny moduł naturalny n. Rzędem elementu a grupy skończonej G nazywa się najmniejszą liczbę
naturalną n taką, że an = e (na = 0 w zapisie addytywnym). Rzędem
Definicja
grupy skończonej G nazywamy liczbę elementów zbioru G. Rząd elementu
Dwie liczby całkowite są równoważne mod n, jeśli przy dzieleniu ich przez
a jest rzędem podgrupy generowanej przez ten element.
n otrzymuje siÄ™ te same reszty.
Charakterystyką pierścienia z jedynką (czyli także ciała) nazywa się
najmniejszą liczbę naturalną p taką, że p-krotna suma jedności jest równa
Reszty przy dzieleniu przez n obejmujÄ… zakres 0, 1, , . . . , n - 1. Pod
zeru, tzn. 1 + 1 + · · · + 1 = 0 JeÅ›li tak zdefiniowana liczba p nie istnieje,
pojęciem tzw. arytmetyki modularnej rozumie się działania (dodawanie
p składników
i mnożenie) w strukturze ilorazowej Zn = Z/mod n utworzonej z klas
to mówi się, że pierścień ma charakterystykę równą zeru. Dowodzi się, że
abstrakcji pierścienia liczb całkowitych Z względem relacji mod n.
charakterystyka dowolnego pierścienia nie zawierającego właściwych
Przykład dzielników zera (czyli każdego ciała) jest równa zeru lub jest liczbą
pierwszÄ….
Arytmetyki modularne stosuje się w obliczeniach komputerowych i często
Dzielnik zera w pierścieniu to element a, dla którego istnieje element b = 0
w życiu codziennym. Mając rejestry b bitowe realizujemy arytmetykę
taki, że ab = 0. Jeśli dzielnik zera jest różny od zera, to nazywamy go
mod 2b. Dni tygodnia liczymy mod 7, miesiÄ…ce zaÅ› mod 12. Wskazania
właściwym dzielnikiem zera.
sekundnika i dużej wskazówki tarczy zegarowej ustalamy mod 60, a małej
Wykazuje się, że jeśli ciało ma dodatnią charakterystykę p, to każdy
wskazówki mod 12, choć godziny w ciagu doby zliczamy mod 24.
niezerowy element ma rząd p w grupie addytywnej tego ciała.
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 15 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 16 / 127
Dzielniki zera w pierścieniu Pierścień (ciało) bez dzielników zera
Przykład
Przykład
Zbadajmy pierścień Z5 = Z/mod 5. Jest to struktura algebraiczna złożona
Zbadajmy pierścień Z4 = Z/mod 4. Jest to struktura algebraiczna złożona
ze zbioru {0, 1, 2, 3, 4} oraz dodawania i mnożenia określonych za pomocą
ze zbioru {0, 1, 2, 3} oraz dodawania i mnożenia określonych za pomocą
tabelek:
tabelek:
+ 0 1 2 3 4 · 0 1 2 3 4
+ 0 1 2 3 · 0 1 2 3
0 0 1 2 3 4 0 0 0 0 0 0
0 0 1 2 3 0 0 0 0 0
1 1 2 3 4 0 1 0 1 2 3 4
1 1 2 3 0 1 0 1 2 3
2 2 3 4 0 1 2 0 2 4 1 3
2 2 3 0 1 2 0 2 0 2
3 3 4 0 1 2 3 0 3 1 4 2
3 3 0 1 2 3 0 3 2 1
4 4 0 1 2 3 4 0 4 3 2 1
Zauważmy, że 2 · 2 = 0. Zatem 2 jest wÅ‚aÅ›ciwym dzielnikiem zera w tym
Wszystkie niezerowe elementy grupy addytywnej mają rząd równy 5, czyli
pierścieniu.
rząd grupy. Charakterystyka rozważanego pierścienia (ciała) jest równa 5.
Ilustracja na pierwszym przezroczu tego wykładu przedstawia mnożenie
Jednocześnie w grupie multiplikatywnej element 1 ma rząd równy 1,
mod 6. Należy znalezć właściwe dzielniki zera w tej strukturze.
elementy 2, 3 mają rząd równy 4, a element 4 ma rząd równy 2.
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 17 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 18 / 127
Ciała Galois Ciało GF (4) a pierścień Z4
CiaÅ‚a skoÅ„czone sÄ… nazywane ciaÅ‚ami Galois na cześć Évariste a Galois, PrzykÅ‚ad
który je odkrył.
Elementy ciała GF (4) są pierwiastkami {0, 1, a, b} wielomianu
Galois wykazał, że charakterystyka ciała skończonego jest zawsze liczbą
pierwszą, a zatem każde ciało o charakterystyce p > 0 zawiera w sobie x4 - x = x(x - 1)(x2 + x + 1) =x(x - 1)(x - a)(x - b) .
jako podciało ciało Zp = Z/mod p. Liczba elementów dowolnego ciała
Dodawanie i mnożenie są określone tabelkami:
Galois jest liczbą pierwszą p lub dowolną naturalną potęgą liczby
pierwszej. Ciała Galois o tej samej liczbie elementów są izomorficzne. Ciała
+ 0 1 a b · 0 1 a b
o pn elementach oznaczamy przez GF (pn).
0 0 1 a b 0 0 0 0 0
Dowodzi się, że elementy ciała GF (pn) są pierwiastkami wielomianu
n
1 1 0 b a 1 0 1 a b
xp - x, który rozkłada się na czynniki o współczynnikach w ciele GF (p).
a a b 0 1 a 0 a b 1
Przykład b b a 1 0 b 0 b 1 a
Najprostszym ciałem Galois jest ciało GF (2), które jest po prostu znaną
Zauważmy, że elementy a i b są pierwiastkami wielomianu x2 + x + 1.
nam już binarną strukturą algebraiczną z dodawaniem xor i mnożeniem
Ta struktura różni się od poprzednio analizowanego pierścienia Z4, np. nie
and. Charakterystyka tego ciała jest równa dwa.
ma w niej właściwych dzielników zera.
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 19 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 20 / 127
Moduł i przestrzeń wektorowa Algebra
Definicja algebry
Definicja modułu
Zestaw (A, F, +, ×, ·) zÅ‚ożony z pierÅ›cienia (A, +, ×) i ciaÅ‚a F oraz
Zestaw (A, F, +, ·) zÅ‚ożony ze zbioru A, pierÅ›cienia F z jedynkÄ…,
z mnożenia zewnętrznego nazywa się algebrą o ile są spełnione
z dodawania wewnętrznego w zbiorze A i mnożenia zewnętrznego nazywa
wszystkie warunki przestrzeni wektorowej,
się modułem o ile są spełnione warunki:
"x"F"a,b"A a(xb) =(xa)b = x(ab) .
dodawanie jest Å‚Ä…czne i przemienne,
w zbiorze A istnieje element neutralny dla dodawania, czyli 0,
Uwagi
"a"A"-a"A
a +(-a) =(-a) +a = 0 ,
Omówiliśmy algebrę, więc może to już koniec naszej nauki? Nie to
mnożenie jest rozdzielne względem dodawań, tzn.
dopiero poczÄ…tek! Dalej zajmiemy siÄ™ grupami permutacji.
"x"F"a,b"A x(a + b) =xa + xb ,
Dziś na Politechnikę Poznańską przyjechałem o godzinie 8:00 rano
i ze względu na wykład z Algebry bedę tu do godziny 15:00.
"x,y"F"a"A (x + y)a = xa + ya ,
Ukochaną Alma Mater opuszczę więc po siedmiu godzinach pracy. Na
"x,y"F"a"A x(ya) =(xy)a ,
tarczy mojego zegarka mała wskazówka będzie jednak pokazywać
"a"A1a = a .
liczbę 3, ponieważ
8 + 7 = 3 mod 12
Uwaga: Definicja przestrzeni wektorowej różni się tym, że F jest ciałem.
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 21 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 22 / 127
Pojęcie permutacji Wzajemnie jednoznaczne odwzorowanie zbioru na siebie
Definicja
Relację R określoną na zbiorze A nazywa się odwzorowaniem
(przekształceniem, transformacją) Ć : A A , zbioru A w siebie, jeśli
"a"A"b"AaRb oraz "a"A"b,c"AaRb i aRc Ò! b = c .
co zapisuje się jako b = Ć(a). Jeśli
"b"A"a"A Ć(a) =b
to odwzorowanie h : A A przekształca zbiór A na siebie. Jeśli istnieje
Definicja
jeden i tylko jeden taki element a, to odwzorowanie nazywamy wzajemnie
Permutatio po Å‚acinie oznacza wymianÄ™, przestawienie, podstawienie,
jednoznacznym (jedno-jednoznacznym, różnowartościowym lub
alegoriÄ™.
odwracalnym). Wówczas istnieje odwzorowanie odwrotne Ć-1 : A A
Permutacja w algebrze to wzajemnie jednoznaczne przekształcenie
zbioru A na siebie takie, że
pewnego zbioru na siebie. Najczęściej ten termin jest używany
w odniesieniu do zbiorów skończonych.
"b"A"a"A a = Ć-1(b)
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 23 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 24 / 127
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A
A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 25 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 26 / 127
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 27 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 28 / 127
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 29 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 30 / 127
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 31 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 32 / 127
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 33 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 34 / 127
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 35 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 36 / 127
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 37 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 38 / 127
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 39 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 40 / 127
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 41 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 42 / 127
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 43 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 44 / 127
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 45 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 46 / 127
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 47 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 48 / 127
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 49 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 50 / 127
Ilustracja odwzorowania za pomocą strzałek Ilustracja odwzorowania za pomocą strzałek
Strzałka odwzorowania a strzałka transferu Strzałka odwzorowania a strzałka transferu
Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza Strzałka we wzorze Ć : a " A b = Ć(a) " A oznacza
przyporzÄ…dkowanie elementowi a " A elementu b " A przyporzÄ…dkowanie elementowi a " A elementu b " A
Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego Jeśli zbiór A jest przeliczalny, to numerując (porządkując) jego
elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A elementy, wzajemnie jednoznaczne odwzorowanie zbioru A na A
można zilustrować, zmieniając porządek elementów. Wówczas element można zilustrować, zmieniając porządek elementów. Wówczas element
b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest b zajmuje miejsce elementu a zgodnie ze strzałką transferu, która jest
przeciwna do strzałki odwzorowania. przeciwna do strzałki odwzorowania.
A = p(A)
A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 51 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 52 / 127
Czy wiedza na temat permutacji może przynieść sławę? Składanie odwzorowań
Rozważmy dwa wzajemnie jednoznaczne odwzorowania dowolnego zbioru
TAK!
A na siebie:
Ć : a " A Ć(a) " A i È : b " A È(b) " A .
Rysunek ilustruje składanie tych odwzorowań traktowane jako mnożenie,
przy czym
(È · Ć)(·) =È(Ć(·)) .
A
Zdjęcie przedstawia pomnik
Mariana Adama Rejewskiego w Bydgoszczy
kryptologa, który dzięki wiedzy dotyczącej teorii permutacji złamał
kody hitlerowskiej maszyny o nazwie Enigma, szyfrujÄ…cej teksty.
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 53 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 54 / 127
Składanie odwzorowań Składanie odwzorowań
Rozważmy dwa wzajemnie jednoznaczne odwzorowania dowolnego zbioru Rozważmy dwa wzajemnie jednoznaczne odwzorowania dowolnego zbioru
A na siebie: A na siebie:
Ć : a " A Ć(a) " A i È : b " A È(b) " A . Ć : a " A Ć(a) " A i È : b " A È(b) " A .
Rysunek ilustruje składanie tych odwzorowań traktowane jako mnożenie, Rysunek ilustruje składanie tych odwzorowań traktowane jako mnożenie,
przy czym przy czym
(È · Ć)(·) =È(Ć(·)) . (È · Ć)(·) =È(Ć(·)) .
A A
A
A A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 55 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 56 / 127
Składanie odwzorowań Składanie odwzorowań
Rozważmy dwa wzajemnie jednoznaczne odwzorowania dowolnego zbioru Rozważmy dwa wzajemnie jednoznaczne odwzorowania dowolnego zbioru
A na siebie: A na siebie:
Ć : a " A Ć(a) " A i È : b " A È(b) " A . Ć : a " A Ć(a) " A i È : b " A È(b) " A .
Rysunek ilustruje składanie tych odwzorowań traktowane jako mnożenie, Rysunek ilustruje składanie tych odwzorowań traktowane jako mnożenie,
przy czym przy czym
(È · Ć)(·) =È(Ć(·)) . (È · Ć)(·) =È(Ć(·)) .
A A A AA A
A A A A
A
A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 57 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 58 / 127
Składanie odwzorowań Grupy odwzorowań
Rozważmy dwa wzajemnie jednoznaczne odwzorowania dowolnego zbioru
A na siebie:
Składanie odwzorowań jako mnożenie
Ć : a " A Ć(a) " A i È : b " A È(b) " A .
W zbiorze wszystkich wzajemnie jednoznacznych odwzorowań dowolnego
Rysunek ilustruje składanie tych odwzorowań traktowane jako mnożenie,
zbioru A na siebie, Ć : a " A Ć(a) " A, skÅ‚adanie odwzorowaÅ„ È(Ć(a))
przy czym
można traktować jako działanie o cechach mnożenia, przy czym
(È · Ć)(·) =È(Ć(·)) .
(È · Ć)(·) =È(Ć(·)):
A AA A
dziaÅ‚anie È · Ć jest Å‚Ä…czne,
istnieje element neutralny, którym jest odwzorowanie
A
A
identycznościowe (neutralne),
dla każdego wzajemnie jednoznacznego odwzorowania istnieje
odwzorowanie odwrotne, w którym po prostu zmieniono kierunek
przyporządkowania elementów.
A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 59 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 60 / 127
Odwzorowanie odwrotne Odwzorowanie odwrotne
Odwzorowanie odwrotne do wzajemnie jednoznacznego odwzorowania Ć(·) Odwzorowanie odwrotne do wzajemnie jednoznacznego odwzorowania Ć(·)
dowolnego zbioru A na siebie dowolnego zbioru A na siebie
Ć : a " A Ć(a) " A Ć : a " A Ć(a) " A
to odwzorowanie È(·) to odwzorowanie È(·)
È = Ć-1 : b = Ć(a) " A È(b) =a " A È = Ć-1 : b = Ć(a) " A È(b) =a " A
Odwzorowanie odwrotne polega na zmianie kierunku przyporzÄ…dkowania Odwzorowanie odwrotne polega na zmianie kierunku przyporzÄ…dkowania
elementów. elementów.
A A
A A
A A
A A
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 61 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 62 / 127
Grupy symetryczne Grupy permutacji
Definicja
Wzajemnie jednoznaczne odwzorowanie zbioru A = {a1, a2, . . . , an} na
Twierdzenie
siebie, p : A A, nazywa siÄ™ permutacjÄ… p tego zbioru.
Zbiór wszystkich wzajemnie jednoznacznych odwzorowań dowolnego zbioru
A na siebie jest grupą ze względu na składanie (mnożenie) odwzorowań.
Notacja
PermutacjÄ™ przyporzÄ…dkowujÄ…cÄ… elementowi ak, k = 1, 2, . . . , n, element
Definicja
aik , ik = 1, 2, . . . , n, co zapisujemy aik = p(ak), oznaczamy symbolicznie:
Grupę wzajemnie jednoznacznych odwzorowań dowolnego zbioru A na a1 a2 . . . an
siebie nazywa siÄ™ grupÄ… symetrycznÄ… zbioru A i oznacza siÄ™ symbolem SA. a ai2 . . . ain
i1
1 2 . . . n
lub prościej
i1 i2 . . . in
a nawet po prostu (i1 i2 . . . in)
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 63 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 64 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 2 4 3 1 3 1 4 2
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 65 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 66 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 2 4 3 1 3 1 4 2
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 67 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 68 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 2 4 3 1 3 1 4 2 3
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 69 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 70 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 4 3 1 3 1 4 2 3
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 71 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 72 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 4 3 1 3 1 4 2 3
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 73 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 74 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 2 4 3 1 3 1 4 2 3 2
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 75 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 76 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 2 4 3 1 3 1 4 2 3 2
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 77 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 78 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 2 4 3 1 3 1 4 2 3 2 1
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 79 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 80 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 2 4 3 1 3 1 4 2 3 2 1
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 81 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 82 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykład Przykład
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 2 4 3 1 3 1 4 2 3 2 1
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 83 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 84 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Obliczmy iloczyn następujących permutacji
Przykład
1 2 3 4 1 2 3 4 1 2 3 4
Obliczmy iloczyn następujących permutacji
· =
2 4 3 1 3 1 4 2 3 2 1 4
1 2 3 4 1 2 3 4 1 2 3 4
· =
Zmieniając porządek czynników otrzymujemy
2 4 3 1 3 1 4 2 3 2 1 4
1 2 3 4 1 2 3 4 1 2 3 4
· =
3 1 4 2 2 4 3 1
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 85 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 86 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 3 1 4 2 2 4 3 1
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 87 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 88 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 3 1 4 2 2 4 3 1
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 89 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 90 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 3 1 4 2 2 4 3 1 1
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 91 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 92 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 3 1 4 2 2 4 3 1 1
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 93 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 94 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 3 1 4 2 2 4 3 1 1 2
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 95 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 96 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 2 3 1 4 2 2 4 3 1 1 2
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 97 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 98 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 2 3 1 4 2 2 4 3 1 1 2
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 99 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 100 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 2 4 3 1 4 2 2 4 3 1 1 2 4
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 101 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 102 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 2 4 3 1 4 2 2 4 3 1 1 2 4
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 103 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 104 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań). Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady Przykłady
Obliczmy iloczyn następujących permutacji Obliczmy iloczyn następujących permutacji
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
2 4 3 1 3 1 4 2 3 2 1 4 2 4 3 1 3 1 4 2 3 2 1 4
Zmieniając porządek czynników otrzymujemy Zmieniając porządek czynników otrzymujemy
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
3 1 4 2 2 4 3 1 1 2 4 3 1 4 2 2 4 3 1 1 2 4 3
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 105 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 106 / 127
Mnożenie permutacji Mnożenie permutacji
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Przykłady
Mnożenie permutacji to ich składanie (tzn. składanie odwzorowań).
Obliczmy iloczyn następujących permutacji
Przykłady
1 2 3 4 1 2 3 4 1 2 3 4
Obliczmy iloczyn następujących permutacji
· =
2 4 3 1 3 1 4 2 3 2 1 4
1 2 3 4 1 2 3 4 1 2 3 4
· =
Zmieniając porządek czynników otrzymujemy
2 4 3 1 3 1 4 2 3 2 1 4
1 2 3 4 1 2 3 4 1 2 3 4
Zmieniając porządek czynników otrzymujemy
· =
3 1 4 2 2 4 3 1 1 2 4 3
1 2 3 4 1 2 3 4 1 2 3 4
· =
Mnożenie przez permutację neutralną
3 1 4 2 2 4 3 1 1 2 4 3
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
· = · =
1 2 3 4 3 1 4 2 3 1 4 2 1 2 3 4 3 1 4 2
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 107 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 108 / 127
Ilustracja notacji uproszczonej Działania na permutacjach zapis uproszczony
Mnożenie
Przykłady
zauważmy, że
PermutacjÄ™ (2 4 3 1) · (3 1 4 2) =(3 2 1 4)
1 2 3 4
natomiast
2 4 3 1
(3 1 4 2) · (2 4 3 1) =(1 2 4 3)
w uproszczeniu zapisujemy jako
Mnożenie permutacji w ogólności nie jest przemienne!
(2 4 3 1)
Odwracanie permutacji
a permutacjÄ™
ZamieniajÄ…c rolami liczbÄ™ z jej pozycjÄ… otrzymuje siÄ™ permutacjÄ™
1 2 3 4
odwrotnÄ…, np.
3 1 4 2
(3 1 4 2)-1 =(2 4 1 3)
zapisujemy w uproszczeniu jako
Permutacja identycznościowa (neutralna) element jednostkowy
(3 1 4 2)
p · (1 2 . . . n) =(1 2 . . . n) · p = p
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 109 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 110 / 127
Transpozycje Permutacje cykliczne
Definicja
Permutację p " Sn nazywamy cykliczną, jeśli dla pewnych różnych
Definicja
elementów permutacji neutralnej k1, k2, . . . , km, m n zachodzi:
PermutacjÄ™
p : k1 k2 , p : k2 k3 , . . . , p : km-1 km , p : km k1
(1 . . . i - 1 j i + 1 . . . j - 1 i j + 1 . . . n) ,
a pozostałe elementy nie zmieniają swoich pozycji. Liczbę m nazywamy
przy czym n 2, nazywamy transpozycją i oznaczamy w skrócie
rzędem permutacji cyklicznej p.
(i j) lub (j i)
Uwaga
Uwaga Permutację cykliczną p oznaczamy w skrócie jako (k1 k2 . . . km) lub
równoważnie (k2 k3 . . . km, k1) lub . . . lub (km k1 k2 . . . km-1)
Zauważmy, że
(i j)-1 =(i j)
Przykład
(2 4 3 1 5 6 7 8 9) =(1 2 4) =(2 4 1) =(4 1 2).
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 111 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 112 / 127
Wnioski dotyczÄ…ce permutacji cyklicznych Enigma hitlerowska maszyna szyfrujÄ…ca za pomocÄ…
permutacji cyklicznych
Przykład
Skrócone oznaczenie permutacji cyklicznych jest wygodne lecz może
niekiedy być zródłem nieporozumień, np. (1 3 2) może oznaczać
permutację trójelementową lub permutację cykliczną o większej
liczbie elementów, w której 1 zmienia się w 3, 3 zmienia się w 2, a 2
zmienia siÄ™ w 1.
Jednoelementowa permutacja cykliczna jest permutacjÄ… jednostkowÄ…
(identycznościową), np. (1 2 3 4) =(1) =(2) =(3) =(4) .
Transpozycja jest dwuelementowÄ… permutacjÄ… cyklicznÄ….
Permutacje cykliczne, które nie mają elementów wspólnych są
nazywane permutacjami rozłącznymi lub niezależnymi.
Iloczyn permutacji rozłącznych jest przemienny, np.
(2 1 4 3) =(1 2) · (3 4) =(3 4) · (1 2)
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 113 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 114 / 127
Marian Adam Rejewski Permutacje cykliczne do szyfrowania tekstu
Polski matematyk i kryptolog Marian Adam Rejewski (który urodził się 16.
sierpnia 1905 r. w Bydgoszczy, studia wyższe z zakresu filozofii ukończył
na Uniwersytecie Poznańskim w 1929 r., zmarł 13. lutego 1980 r. w
Warszawie) po raz pierwszy złamał kod Enigmy już w 1932 r. Dzięki temu
sukcesowi i dalszym wieloletnim pracom wspólnie z Henrykiem Zygalskim
i Jerzym Różyckim nad łamaniem kodów ciągle ulepszanych wersji Enigmy Przykład permutacji cyklcznej wykorzystywanej do szyfrowania tekstu
wywiad brytyjski był w stanie odczytywać zaszyfrowaną korespondencję za pomocą maszyny Enigma
niemiecką. To w istotny sposób przyczyniło się do wygrania II wojny
światowej przez aliantów.
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 115 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 116 / 127
Potęgowanie permutacji cyklicznych Dekompozycja permutacji cyklicznych
Twierdzenie
Uwaga
Każdą permutację cykliczną p rzędu m można przedstawić w postaci
Niech p będzie permutacją cykliczną rzedu m. Zauważmy, że:
iloczynu m - 1 transpozycji.
p2 : k1 k3 , p : k2 k4 , . . . , p : km-1 k1 , p : km k2
p3 : k1 k4 , p : k2 k5 , . . . , p : km-1 k2 , p : km k3
Dowód
.
.
Niech permutacja p ma postać (k1 k2 . . . km). Wówczas
.
pm-1 : k1 km, p : k2 k1, . . . , p : km-1 km-2, p : km km-1
p =(k1km) · (k1km-1) · . . . · (k1k3) · (k1k2) .
pm : k1 k1, p : k2 k2, . . . , p : km-1 km-1, p : km km
Istotnie, permutacja (k1k2) ustawia docelowo element k2 na pozycji k1, a
jednocześnie chwilowo element k1 na pozycji k2. Na pozycji k2
Wnioski
powinien znalezć się jednak element k3. Dokonuje się to właśnie poprzez
pm jest permutacją identycznościową
pomnożenie przez permutację (k1k3), która wstawia element k3 wmiejsce,
pm-1 = p-1
gdzie był do tej pory element k1. Dalsze kroki są analogiczne.
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 117 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 118 / 127
Przykład dekompozycji permutacji cyklicznej Dekompozycja permutacji na permutacje cykliczne
Twierdzenie
Dowolna permutacja p jest cykliczna lub można ją rozłożyć na iloczyn
Przykład
niezależnych (rozłącznych) permutacji cyklicznych. Iloczyn permutacji
Zauważmy, że
rozłącznych jest przemienny.
(2 3 1 4) =(1 2 3)
Dowód
oraz
Wybierzmy najmniejszą spośród liczb, które przy permutacji p nie
(1 2) =(2 1 3 4)
przechodzÄ… w siebie. Ta liczba przechodzi w innÄ…, a ta w jeszcze innÄ…. W
i
końcu cykl się zamyka, tworząc permutację cykliczną p1, bo permutacja p
(1 3) =(3 2 1 4)
ma skończoną liczbę elementów. Jeśli w permutacji p wszystkie liczby nie
wzięte w ten sposób pod uwagę przechodzą w siebie, to p = p1. Jeśli nie,
zatem
to bierzemy najmniejszą spośród nich i kontynuujemy ten proces, tworząc
permutacje cykliczne p2, p3 itd. Proces ten kończy się na permutacji
(1 3) · (1 2) =(3 2 1 4) · (2 1 3 4) =(2 3 1 4) =(1 2 3)
cyklicznej pl, bo permutacja p ma skończoną liczbę elementów. Zatem
p = p1 · p2 · . . . · pl. Permutacje p1, p2, . . . , pl sÄ… rozÅ‚Ä…czne, bo nie majÄ…
elementów wspólnych i dlatego ich iloczyn jest przemienny.
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 119 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 120 / 127
Dekompozycja permutacji na permutacje cykliczne Dekompozycja permutacji na transpozycje
Wniosek
Przykład
Każdą permutację można przedstawić w postaci iloczynu transpozycji.
(2 4 3 1 7 8 5 9 6) =
Przykład
=(1 2 4) · (5 7) · (6 8 9)
(2 4 3 1 7 8 5 9 6) =(1 2 4) · (5 7) · (6 8 9)
=(5 7) · (6 8 9) · (1 2 4)
ale
=(6 8 9) · (1 2 4) · (5 7)
(1 2 4) =(1 4) · (1 2)
=(1 2 4) · (6 8 9) · (5 7)
oraz
=(6 8 9) · (5 7) · (1 2 4)
(6 8 9) =(6 9) · (6 8)
=(5 7) · (1 2 4) · (6 8 9)
zatem
(2 4 3 1 7 8 5 9 6) =(1 4) · (1 2) · (5 7) · (6 9) · (6 8)
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 121 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 122 / 127
Permutacje parzyste i nieparzyste Permutacje parzyste i nieparzyste
Permutacje parzyste
Wnioski
Permutację nazywa się parzystą, jeśli jest ona iloczynem parzystej liczby
Transpozycje sÄ… permutacjami nieparzystymi.
transpozycji.
m elementowa permutacja cykliczna jest nieparzysta, gdy liczba m
jest parzysta i odwrotnie.
Permutacje nieparzyste
n elementów tworzy n! permutacji, w tym dla n 2 jest (1/2) · n!
W przeciwnym przypadku permutacjÄ™ nazywa siÄ™ nieparzystÄ….
permutacji parzystych i tyle samo nieparzystych.
Wyznacznik liczbowej macierzy kwadratowej jest sumÄ… wszystkich
Przykład
możliwych iloczynów elementów tej macierzy po jednym z każdego
Daną permutację można rozłożyć na transpozycje na różne sposoby, np.
wiersza i po jednym z każdej kolumny, przy czym jeśli np. wiersze
uporządkuje się po kolei, to kolumny występują w kolejnościach
(2 1 4 3) =(1 2) · (3 4) =(1 3) · (1 2) · (2 4) · (2 3)
tworzących wszystkie możliwe permutacje; iloczyny odpowiadające
permutacjom parzystym występują ze znakiem + , a odpowiadające
lecz zawsze liczba tych transpozycji jest dla danej permutacji parzysta
permutacjom nieparzystym sÄ… brane ze znakiem - .
bądz nieparzysta. Powyższa, przykładowa permutacja jest zatem parzysta.
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 123 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 124 / 127
Wyznacznik Zabawa w permutacje
Definicja wyznacznika
a11 a12 · · · a1n
a21 a22 · · · a2n
= (-1)ka1p(1) · a2p(2) · . . . · anp(n)
.
.
.
p"SA
an1 an2 · · · ann
SA jest zbiorem wszystkich n elementowych permutacji p, zaÅ› k jest liczbÄ…
transpozycji składających się na permutację p.
Przykład
a11 a12 a13
+a11 · a22 · a33 + a13 · a21 · a32 + a12 · a23 · a31
Ucząc się o permutacjach, można zagrać w bierki!
a21 a22 a23 =
-a13 · a22 · a31 - a11 · a23 · a32 - a12 · a21 · a33
Trzeba znalezć taką kolejność wyjmowania bierek,
a31 a32 a33
aby nie poruszyć tych, które jeszcze pozostały w stosie.
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 125 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 126 / 127
Inna zabawa w permutacje ... Studenckie Koło Naukowe Decybel ZAPRASZAMY!
www.decybel.put.poznan.pl
PrzewodniczÄ…cy:
Andrzej Namerła
andrzej.namerla@put.poznan.pl
Opiekun:
Profesor Adam DÄ…browski
Sekcja Teleinformatyki,
Technik Internetowych
i Mikroprocesorów
Sekcja Telewizji i Systemów
Wizyjnych Robotów
Sekcja Biometrii i Interfejsów
Człowiek-Komputer
Sekcja Akustyki Technicznej
i Psychoakustyki
to tasowanie kart!
Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 127 / 127 Adam Dąbrowski (Politechnika Poznańska) Algebra z geometrią 11 pazdziernika 2010 128 / 127
Wyszukiwarka
Podobne podstrony:
IX Struktury algebraiczneAlgebra 0 03 struktury algebraicznestruktury algebraiczneWykład 1 struktury algebraiczneWykład 2 struktury algebraiczne IIWykład 2 struktury algebraiczne IIF1 17 Algebra Boole a 1F1 17 Algebra Boole a 1Cin 10HC [ST&D] PM931 17 317 Prawne i etyczne aspekty psychiatrii, orzecznictwo lekarskie w zaburzeniach i chorobach psychiczn17 (30)więcej podobnych podstron