Algebra gyakorlat, 2. feladatsor, megoldásvázlatok
1.
a) b)
c)
(1 2)(2 3)(3 4)(4 5) = (1 2 3 4 5). Az állítás például k szerinti indukcióval könnyen belátható, az igazságtartalma közvetlenül is ellen®rizhet®: a jobboldalon a jobbról balra szorzás miatt x1 az x2 be megy az (x1 x2 ) ciklus miatt, x2 az x3 -ba megy az (x2 x3 ) ciklus miatt, stb. Végül az xk−1 az xk -ba megy az (xk−1 xk ) ciklus miatt, majd xk az (xk−1 xk ) ciklus miatt el®ször az xk−1 -be, majd az (xk−1 xk−2 ) ciklus miatt el®ször az xk−2 -be, stb. végül az (x2 x1 ) ciklus miatt az x1 -be. Tehát a jobboldal valóban az x1 . . . xk ciklust adja
meg. Az (ab) transzpozíció páratlan permutáció, hiszen az a és b cserél®dik (1 inverzió), valamint minden a < k < b inverzióban ál a csere utánl a-val és b-vel is, ezen utóbbi inverziók száma tehát páros. Az 5. feladat segítségével beláthattuk volna máshogy is: legyen g egy olyan permutáció, ami 1-et a-ba, 2-t b-be viszi, ekkor az 5. feladat alapján (ab) = g(12)g −1 , vagyis sg (ab) = sg (g) sg (12) sg g −1 = sg (12) .
d)
e) f)
2.
g) a)
b)
Tehát minden transzpozíciónak azonos az el®jele, az (12)-é pedig −1, hisz egyetlen inverzió van. Permutáció rendjét a diszjunkt ciklusokra vett felbontásból lehet legegyszer¶bben megállapítani: a rend megegyezik a diszjunkt ciklusok hosszainak legkisebb közös többszörösével. Vagyis o (g) = [4, 3] = 12, o (h) = [2, 3, 2] = 6, o (gh) = 8, o (g −1 ) = o (g) = 12. ) A permutáció paritását, vagy más néven el®jelét a következ®képp lehet kiszámolni legegyszer¶bben: páros hosszú ciklus páratlan permutáció, páratlan hosszú ciklus páros permutáció. Így sg(g) = −1, sg(h) = 1, sg(gh) = −1, sg(g −1 ) = sg(g) = −1. Nem áll el®. Ugyanis a hármas ciklusok páros permutációk, szorzatuk is páros permutáció, de az (12) páratlan permutáció. Az alábbi ciklusszerkezetek fordulnak el® S5 -ben, a hozzújuk tartozó rendek: id : 1
(ab) : 2
(ab)(cd) : 2
(abc)(de) : 6
(abcd) : 4
(abcde) : 5.
(abc) : 3
Van, pl. (12)(34567). 8 8 Ha 2 rendje 8 Z× p -ben, akkor 2 ≡ 1 (mod p), vagyis p | 2 − 1 = 255. Most 255 = = 3 · 5 · 17, vagyis p csak 3, 5, 17 valamelyike lehet. A p = 3 vagy p = 5 esetekben × Z5 = 4. a 2-nek legfeljebb 2 illetve 4 különböz® hatványa lehet, hiszen Z× = 2 , 3 × (Egyébként ellen®rizhet®, hogy Z× 3 -ben o(2) = 2, Z5 -ben o(2) = 4.) A p = 17 viszont jó lesz: a 8 jó kitev®, ezért o(2) | 8. Ha tehát o(2) 6= 8 lenne, akkor o(2) | 4 teljesülne, de 24 = 16 ≡ −1 (mod 17). Utóbbi érvelésb®l az is látszik, hogy 15 osztói nem lehetnek jók, hiszen ha p | 15, akkor 24 = 16 ≡ 1 (mod p), vagyis ekkor o(2) | 4 lenne. 5 5 Ha 3 rendje 5 Z× p -ben, akkor 3 ≡ 1 (mod p), vagyis p | 3 − 1 = 242. Most 242 = = 2·112 , vagyis p csak 11 lehet. (Ha p = 2, akkor Z× 2 egyetlen eleme az egységelem, aminek rendje 1.) Viszont p = 11 jó is: az 5 jó kitev®je a 3-nak Z× 11 -ben az el®bb látottak alapján, így o(3) | 5. Tehát o(3) ∈ { 1, 5 }, és o(3) 6= 1 miatt o(3) = 5. 1
2
c)
3.
a)
b)
6 6 Ha 2 rendje 6 Z× p -ben, akkor 2 ≡ 1 (mod p), vagyis p | 2 − 1 = 63. Most 63 = = 32 · 7, vagyis p csak 3, 7 valamelyike lehet. A p = 3 esetben a 2-nek legfeljebb 2 különböz® hatványa lehet, hiszen Z× 3 = 2. A p = 7 eset szintén nem jó, mert × 3 2 = 8 ≡ 1 (mod 7), vagyis Z7 -ben o(2) | 3, és így a 2 rendje nem lehet 6. Az egységelem rendje minden csoportban 1. Az egész számok csoportjában minden egyéb elem rendje végtelen. A (Zn , +) csoportban o (k) = n/ (n, k). A C× csoportban a primitív n-edik egységgyökök rendje n, a többi elem rendje végtelen, így az R× csoportban 1 rendje 1, a -1 rendje 2, a többi elem rendje végtelen. A Z× 5 csoportban o (2) = o (3) = 4, o (4) = 2. A Z× 8 csoportban az egységelem kivételével minden elem másodrend¶ (Klein csoport). A D3 csoportban a forgatások rendje 3 (két darab), a tükrözések rendje 2 (három darab). A D4 csoportban a két 90◦ -os forgatás rendje 4, a 180◦ -os forgatás rendje 2, a tükrözések rendje 2 (négy darab). A D6 csoportban a két 60◦ -os forgatás rendje 6, a két 120◦ -os forgatás rendje 3, a 180◦ -os forgatás rendje 2, a tükrözések rendje 2 (hat darab). Az S3 szimmetrikus csoportban a hármas ciklusok rendje 3 (két darab), a kettes ciklusok rendje 2 (három darab). Az A4 alternáló csoportban a hármas ciklusok rendje 3 (nyolc darab), a két diszjunkt kettes ciklus szorzataként el®álló permutációk rendje 2 (három darab). Végül, a kvaterniócsoportban az 1 rendje 1, a −1 rendje 2, a többi elem rendje 4. El®adáson szerepelt, hogy (Z4 , +) ' Z× 5 6' Z× 8 . El®bbire az izomor a például a
ϕ : (Z4 , +) → Z× 5,
g 7→ 2g
(mod 5).
× Továbbá, Z× 5 és Z8 nem izomofak, mert utóbbiban nincs negyedrend¶ elem, míg Z× 5 -ben van. A D6 és A4 nem izomorf, mert nem stimmelnek az elemrendek (az izomor a pedig meg®rizné ®ket): míg D6 -ban hét másodrend¶ elem van, addig A4 -ben csak három. Másképpen: D6 -ban van hatodrend¶ elem, míg A4 -ben nincs. A kvaterniócsoport nem izomorf a D4 -gyel, mert nem stimmelnek az elemrendek: pl. Q-ban csak egy másodrend¶ elem van, míg D4 -ben öt. A D3 és az S3 csoportok izomorfak. A D3 csoport a szabályos háromszög szimmetria csoportja, melynek elemei permutálják a háromszög csúcsait. Számozzuk meg a háromszög csúcsait az 1, 2, 3 számokkal, és tekintsük a
ϕ : D3 → S3 ,
c)
4.
a)
g 7→
1 2 3 g(1) g(2) g(3)
hozzárendelést. Könny¶ ellen®rizni, hogy ϕ bijektív és homomor zmus, tehát izomor zmus. Ciklikus lesz (Z4 , +) (generátora pl. 1), Z× 5 (generátora pl. 2), (Z, +) (generátora pl. 1). A többi csoport nem ciklikus, a többség azért, mert már nem is kommuta× tív. Z× 8 -ben nincs negyedrend¶ elem, végül R egy végtelen csoport, amiben van másodrend¶ elem, de az egyetlen végtelen ciklikus csoportban (azaz (Z, +)-ban) nincs másodrend¶ elem. A feladat valójában azt mondja, hogy minden Sn -beli permutációt felírhatunk az (12), (23), (34), . . . , (n−1 n) permutációk alkalmas szorzataként. Tegyük fel, hogy n darab könyvünk van felrakva egy polcra. A jótündér (k − 1 k) alakú ciklusokat tud alkalmazni, hiszen ez pont úgy permutálja a könyveket, hogy
3
megcseréli a k − 1. és a k . könyvet egymással. Így a feladat azt jelenti, hogy a könyvek tetsz®leges sorrendjéb®l kiindulva, azokat tetsz®leges másik sorrendbe átpakolhatja a jótündér úgy, hogy mindig csak két egymás mellett lev®t cserél meg. Ez viszont világos: a jótündér megkeresi azt a könyvet, amit az els® helyen volt, majd néhány szomszédos cserével a helyére viszi. Ezután megkeresi azt, amit a második helyen volt, azt is egyesével el®reviszi, stb. (n darab könyv esetén legfeljebb n − 1 + n − 2 + · · · + 1 = n(n − 1)/2 cserét kell végeznie, ez b®ven belefér, miel®tt kivirradna.) b) A feladat most azt mondja, hogy minden Sn -beli permutációt felírhatunk az (1 2), (1 3), (1 4), . . . , (1 n) permutációk alkalmas szorzataként. Tegyük fel, hogy n darab könyvünk van felrakva egy polcra. A jótündér testvére (1 k) alakú ciklusokat tud alkalmazni, hiszen ez pont úgy permutálja a könyveket, hogy megcseréli az els® és a k . könyvet egymással. Így a feladat azt jelenti, hogy a könyvek tetsz®leges sorrendjéb®l kiindulva, azokat tetsz®leges másik sorrendbe átpakolhatja a jótündér testvére úgy, hogy mindig csak az els® könyvet cseréli egy másikkal. Tehát: megkeresi a legutolsó helyre való könyvet, és azt kicseréli az els® könyvvel (ezzel az els® helyre kerül), majd a hátsó könyvvel cserélve az utolsó könyv a helyére kerül. Ezt követ®en ugyanezt megteszi az utolsó el®tti helyre való könyvvel, stb. (n darab könyv esetén legfeljebb 2n−1 cserét kell végeznie, ez b®ven belefér, miel®tt kivirradna.) 5. Általában, ha a h ∈ Sn az i-t a j -be viszi, akkor ghg −1 ∈ Sn a g(i)-t a g(j)-be viszi. Valóban: ghg −1 (g(i)) = g(h(i)) = g(j). Így már könny¶ kiszámolni ghg −1 -et: egyszer¶en a h felírásában az összes elemre rá kell alkalmazni g -t. Speciálisan, h és ghg −1 ciklusszerkezete mindig ugyanaz. A felsorolt példákban ghg −1 értékei sorban: (1543), (543) (21), (23451). (Vessük össze a mátrixoknál tanult bázistranszformációval! Ott a báziscsere egy alkalmas konjugálásnak felel meg. Itt más sorrendben felírva az { 1, 2, . . . , n } elemeit (g adja meg a másik sorrendet) szintén egy konjugálásnak felel meg. ) 6. Másolva az el®adáson a permutáció rendjér®l tanultakat: ϕ (1G ) = ϕ (1G · G 1G ) = ϕ (1G ) · H ϕ (1G ) ,
amit (ϕ (1G ))−1 -zel egyszer¶sítve H -ban kapjuk, hogy 1H = ϕ (1G ). Hasonlóan, 1H = ϕ (1G ) = ϕ g · G g −1 = ϕ (g) · H ϕ g −1 ,
vagyis ϕ (g −1 ) jó inverznek H -ban ϕ (g)-hez. Az inverz egyértelm¶sége miatt ϕ (g −1 ) éppen ϕ (g) inverze H -ban. 7. Tetsz®leges nem nulla determinánsú A, B mátrixra ellen®rizni kell a det(A · B) = det(A) · det(B)
összefüggést. Ez az ún. determinánsok szorzástétele, ami szerepelt korábban lineáris algebrából. 8. A b elem az a sorában éppen az a−1 b oszlopban szerepel, hiszen a(a−1 b) = (aa−1 )b = = b. Ha a b elem az x1 és az x2 oszlopban is szerepelne, akkor ax1 = h = ax2 -t balról egyszer¶sítve a−1 -zel kapnánk, hogy x1 = x2 . Oszlopokra az állítás analóg módon látható be.
4
9. A Z× n rendje ϕ (n). A Lagrange tétel következménye, hogy elem rendje osztja a csoport rendjét, így a 7 rendjét úgy könny¶ meghatározni, hogy ϕ (n) osztói közt megkeressük × a legkisebb k kitev®t, melyre 7k ≡ 1 mod n teljesül. A 7 rendje Z× 8 -ben 2, Z12 -ben 2, × × × × × Z16 -ben 2, Z20 -ben 4, Z24 -ben 2, Z27 -ben 9, Z32 -ben 4. 10. ghg −1 = (247) (38) (56). 11. Permutáció rendjét a diszjunkt ciklusokra vett felbontásból lehet legegyszer¶bben megállapítani: a rend megegyezik a diszjunkt ciklusok hosszainak legkisebb közös többszörösével. Eszerint o(h) = (2,3,2) = 6,
o(g 2 h) = (4,4) = 4,
o(hg) = (8) = 8,
o(g −1 hg) = (3,2,2) = 6,
o(g −1 h−1 gh) = (6, 2) = 6,
o(h−1 g −1 hg) = (6,2) = 6.
o(g) = (4, 3) = 12, o(hg 2 ) = (4, 4) = 4, o(h−1 gh) = (3, 4) = 12,
A permutáció paritását, vagy más néven el®jelét a következ®képp lehet kiszámolni legegyszer¶bben: páros hosszú ciklus páratlan permutáció, páratlan hosszú ciklus páros permutáció. Ennek alapján sg(g) = −1, sg(h) = 1, sg(g 2 h) = 1. Felhasználva, hogy az sg : Sn → {±1} függvény homomor zmus, könny¶ kiszámolni egy szorzat el®jelét, hiszen csak az el®jeleket kell összeszorozni. sg(hg 2 ) = 1 · (−1)2 = 1,
sg(hg) = 1 · (−1) = −1,
sg(g −1 hg) = (−1) · 1 · (−1) = 1,
sg(h−1 gh) = 1 · (−1) · 1 = −1,
sg(g −1 h−1 gh) = (−1) · 1 · (−1) · 1 = 1,
sg(h−1 g −1 hg) = 1 · (−1) · 1 · (−1) = 1.
× × 12. A (Z5 , +), (Z6 , +), (Z12 , +) és (Z, +) ciklikusak, generátoruk az 1. A Z× , Z× 5 , Z6 , Z7 × × és Z× 9 szintén ciklikusak. Ugyanis Z = { 1, −1 } generátora −1, Z5 egy generátora 2, × × × Z6 generátora 5, Z7 egy generátora 3, valamint Z9 egy generátora 2. A Z× 8 négyelem¶ × × csoport, de minden eleme másodrend¶. A Q , R és GL2 (Q) csoportok végtelenek, de van másodrend¶ elemük, tehát nem lehetnek (Z, +)-szal izomorfak (egyébként GL2 (Q) nem is kommutatív, a ciklikus csoportok pedig azok). Végül a (Q, +) és (C, +) csoportokról közvetlenül ellen®rizhet®, hogy nem generálhatóak egyetlen elemmel. 13. A mátrixszorzás asszociativitása szerepelt lineáris algebrából, az egységmátrix az egységelem. Amit ellen®rizni kell, hogy a felsorolt mátrixok közül bármely kett® szorzata is benne van Q-ban, ez megtehet®. A kvaterniócsoport egy másik szokásos megadása a következ® (ez szerepelt az el®adáson). A felírt mátrixok helyett rendre a ±1, ±i, ±j, ±k elemekkel számolunk, ez megad egy izomor át a két csoport között (a m¶velettartás könnyen ellen®rizhet®). Az ennek megfelel® Cayley táblázat: (Rövidítve, az el®jelekkel a szokásos módon bánunk, azaz + · + = − · − = +, + · − = − · + = −.)
Q 1 i j k
1 i j k 1 i j k i −1 k −j j −k −1 i k j −i −1
14. Ha t egy, a szabályos n-szöget helybenhagyó tükrözés, f pedig a szabályos n-szög középpontja körüli 2π/n szög¶ forgatás, akkor Dn = { 1, f, . . . , f n−1 , t, f t, . . . , f n−1 t }. Itt f rendje n, f k rendje a hatvány rendjéb®l n/ (n, k), valamit tf k rendje 2.
5
15. A 7 csak 7-es ciklusok rendje lehet S10 -ben. A hat rend¶ elemek azon permutációk, melyek diszjunkt ciklusokra való felbontásában csak 1-es, 2-es, 3-as és 6-os ciklusok szerepelnek, melyek legkisebb közös többszöröse 6. Az egyes ciklusfelbontásokra egyegy példa: (123456), (12)(345),
(123456)(78),
(12)(345)(67),
(12356)(78)(910), (123456)(789),
(12)(345)(67)(89),
(12)(345)(678),
(12)(345)(67)(8910).
16. S8 -ban nincs 11 és 13-ad rend¶ elem, ezekben ugyanis szükségszer¶en lennie kell 11 illetve 13 hosszú ciklusoknak. Nincs 14 rend¶ elem sem, mert egy ilyen vagy egy 14-es ciklus, vagy diszjunkt 2-es és 7-es ciklusok szorzata. A többi elemrendre van példa: 10 : (12)(345), 12 : (123)(4567), 15 : (123)(45678). 1 0 17. Másodrend¶ elemre példa . Ha A harmadrend¶, akkor A3 = I , amib®l 0 −1 2 (A − I)(A2 + A + I) = 0. Ha tehát A karakterisztikus polinomja x + x + 1, akkor 0 −1 A2 + A + I = 0, vagyis A3 = I . Ilyen mátrix például A = . 1 −1 Végül, ha B 5 = I , akkor legyen k(x) a B karakterisztikus polinomja, ekkor B gyöke k(x)-nek is és az x5 − 1 polinomnak is, így gyöke a legnagyobb közös osztójuknak is. Mivel x5 − 1 = (x − 1)(x4 + x3 + x2 + x + 1), és x − 1 és x4 + x3 + x2 + x + 1 irreducibilis, ezért (k(x), x5 − 1) = 1 vagy (k(x), x5 − 1) = x − 1 (ne felejtsük el, hogy k(x) másodfokú). El®bbi nem lehet, mert annak a polinomnak nem gyöke B . Utóbbinak pedig csak a B = I mátrix gyöke, aminek viszont a rendje 1.
18. A 6-ot nem tudjuk olyan pozitív egészek összegeként felbontani, melyek legkisebb közös többszöröse 12, így S6 -ban nincs 12-edrend¶ elem. Viszont S7 -ben van, például (1234)(567). A 12-edrend¶ elemek S7 -ben azon elemek, melyek el®állnak egy négyes és egy hármas (diszjunkt) ciklus szorzataként. Az ilyenek száma 7 4! 3! · · = 420. 4 3 4
(Vegyük észre, hogy ha rögzítünk k elemet, akkor éppen k!k darab különböz® k -as ciklus képezhet® bel®lük.) 19. n ≥ 9 esetén lesz Sn -ben 14-ed rend¶ elem, n ≥ 7 esetén lesz Sn -ben 7-ed rend¶ elem, n ≥ 49 esetén lesz Sn -ben 49-ed rend¶ elem, n ≥ 10 esetén lesz Sn -ben 30-ad rend¶ elem. 20. Képzeljünk az üres mez® helyére 16-t, ekkor minden kon gurációnak kölcsönösen egyértelm¶en megfelel egy S16 -beli permutáció. Minden f ∈ S16 permutációhoz jelölje if és jf a megfelel® kon gurációban az üres mez® (16-os) sor- és oszlopindexét, és tekintsük a P (f ) = (−1)if +jf · sgf függvényt. Nyilván P (f ) = ±1, és a P értéke nem változik meg egy tolás alkalmával. Valóban, egyrészt egy tolás során a sor- vagy oszlopindex pontosan 1-gyel változik, ami egy (−1)-gyel való szorzást jelent P (f )-en. Másrészt az f permutáció megszorzódik
6
egy alkalmas (k l) cserével, ahol k az üres mez® pozíciója, l pedig azon mez® pozíciója, amit az üres helyre tolunk. Mivel egy csere páratlan, ezért ez is egy (−1)-gyel való szorzást eredményez P (f )-en, így annak értéke egy tolás során valóban nem változik. Viszont P (id) = 1, de P ((14 15)) = −1, így az egyik állapotból a másik nem érhet® el tologatások segítségével.
