Grup Permutasi dan Grup Siklis Winita Sulandari
Grup Permutasi • Suatu Permutasi dari suatu himpunan berhingga S yang tidak kosong, dinyatakan sebagai suatu pemetaan bijektif dari himpunan S pada dirinya sendiri.
Definisi Fungsi Suatu fungsi f dari A ke B adalah suatu aturan yang memetakan setiap elemen A ke tepat satu elemen B, ditulis: f:A→B Jika f memetakan a ∈ A ke b ∈ B, ditulis f(a) = Ab B f a
f(a) b
3
Fungsi satu-satu dan onto 1. Fungsi f : A → B dikatakan satu-satu, jhj, jika f(a)=f(b), maka a=b. 2. Fungsi f : A → B dikatakan onto, jhj, untuk setiap b∈B, ada a∈A sedemikian sehingga b = f(a)
A
f
1
B 1
2
2
3
3
4
1 1
A 1 2 3 4
f
B 1 2 3
onto 4
Fungsi Komposisi Jika f dan g adalah fungsi-fungsi dengan f : A → B dan g : B → C, maka ada fungsi dari A ke C. Fungsi dari A ke C adalah fungsi komposisi yang terdiri dari f diikuti g, ditulis: (g⃘f)(a) = g(f(a)) = c, dengan a ∈ A dan c ∈ C.
gambar:
A
a
f
B
f (a)
g
C c g(f(a))
( g f )( a ) 5
Definisi Permutasi
Suatu permutasi pada A adalah fungsi dari A ke A yang sekaligus satu-satu dan onto, ditulis 11
f : A A onto
6
Contoh 1 Diberikan A = { 1, 2, 3, 4, 5 }. f adalah permutasi yang digambarkan sebagai:
A
f
1 2 3 4 5
A 1 2 3 4 5
atau
1 4 22 35 43 5 1
f ditulis dalam notasi baku sebagai berikut :
1 2 3 4 5 f 4 2 5 3 1 7
1 2 3 4 5 Dari: f 4 2 5 3 1
dapat diartikan bahwa:
f(1) = 4 f(2) = 2 f(3) = 5 f(4) = 3 f(5) = 1
8
Komposisi Permutasi (Teorema) Jika f dan g permutasi-permutasi pada A, maka f⃘g juga permutasi pada A. (
11
f g : A A onto
)
9
Contoh 2 1 2 3 4 5 Misalkan f dan 4 2 5 3 1 1 2 3 4 5 g 3 5 4 2 1 1 2 3 4 5 1 2 3 4 5 Maka f ⃘ g = 4 2 5 3 1 3 5 4 2 1 sehingga
Jadi
(f⃘g)(1) = f(g(1)) = f(3) = 5 (f⃘g)(5) = f(g(5)) = f(1) = 4, dsb.
1 2 3 4 5 f⃘g= 5 1 3 2 4 10
GRUP SIMETRIK
Diberikan A adalah himpunan berhingga {1,2,3, …,n}. Grup semua permutasi untuk A disebut grup simetrik pada n huruf, dan ditunjukkan dengan Sn. Perhatikan bahwa Sn mempunyai n! = n(n-1)(n-2)…(3)(2)(1). 11
Teorema 2.4.2 Karakteristik atau orde dari grup Sn adalah n!.
Contoh: Diberikan himpunan A = {1,2,3}. Contoh grup simetri A(S) = S3 , order A(S) 3! = 6 elemen. Didaftar permutasi-permutasi untuk A sbb: 12 3 12 3 o 1 2 3 , 1 1 3 2 1 2 3 1 2 3 1 2 3 1, 2 3 2 1 1 2 3 1 2 3 2 3 1 2 , 3 2 1 3 13
Dapat ditunjukkan
⃘
α0
α1
α2
β1
β2
β3
α0
α0
α1
α2
β1
β2
β3
α1
α1
α2
α0
β3
β1
β2
α2
α2
α0
α1
β2
β3
β1
β1
β1
β2
β3
α0
α1
α2
β2
β2
β3
β1
α2
α0
α1
β3
β3
β1
β2
α1
α2
α0
14
Perhatikan bahwa grup simetrik tersebut di atas tidaklah komutatif (contoh grup berhingga yang tidak komutatif) Jadi S3 mempunyai tingkat (order) minimal untuk sembarang grup yang tidak komutatif.
15
Soal latihan 1.
1 2 3 4 1 2 3 4 f dan g 2 1 4 3 3 1 4 2
Hitunglah komposisi sebagai berikut: a) f g b) g f c) f-1 d) g-1 e) f –1 g-1 f) (f g)-1
2.
1 2 3 4 1 2 3 4 f dan g 3 4 1 2 4 3 1 2 Hitung a) f g d) f g2
b) g-1 f-1 e) f g2
c) (g f )-1
Perkalian Langsung • Apabila terdapat dua buah grup G1 dan G2 maka dapat dibentuk grup baru dari kedua grup tersebut • produk Cartesius dari dua himpunan A dan B yang dinyatakan dengan AxB = {(ai, bi) / ai A, bi B}.
Teorema 2.5.2 Bila G dan H dua buah grup maka produk Cartesius G x H dengan operasi : ( gi , hi ) (gj , hj ) = (gi gj , hi hj ) untuk setiap (gi , hi ) dan (gj , hj ) G x H maka G x H merupakan grup dan disebut perkalian langsung (direct product) dari G dan H.
• Perhatikan operasi dalam grup • Contoh: 1 Dalam perkalian langsung Z x Z karena Z merupakan grup terhadap operasi + maka operasi dalam Z x Z berlaku sama. Misalkan (a,b) dan (c,d) unsur dalam Z x Z maka (a,b)(c,d) = (a + c,b + d) Z x Z.
Contoh 2: Misal grup ( Z3 , + ) dan grup permutasi (S2 ,) Z3 x S2 = { (1,i), (2,i), (3,i), (1,(1 2)),(2,(1 2)),(3,(1 2))}
sedang operasi unsur-unsurnya sebagai berikut: Misal, ( 2, i) ( (3,(1 2)) = ( 2 + 3, i (1 2)) = ( 2, (1 2 ))
• Apabila G dan H dua grup berhingga , maka orde dari G x H yaitu G x H = G.H
Latihan soal 1. Bila grup G mempunyai unsur identitas i dan grup H mempunyai unsur identitas e buktikan {( gi, e) / gi G } dan { (i, hi ) hi H } merupakan subgrup dari G x H 2. Tuliskan semua unsur dari grup S3 x Z2 dan tentukan subgrup yang mungkin dalam S3 x Z2.
Latihan soal 3. Hitunglah perkalian unsur-unsur sebagai berikut a. ((123),2)((23),3) dalam S3 x Z5 b. (2,3)(-1,5) dalam Q x Q* dimana Q* adalah himpunan bilangan rasional tanpa unsur nol.
GRUP SIKLIS
Himpunan dengan anggota-anggota berbentuk ai , i 0 ,1, 2 , 3 ,, n 1 dengan a0 an e , dan ai a j ai j , jika i j n ai a j ai jn , jika i j n
membentuk suatu grup siklik, a sebagai elemen pembangun atau penghasil atau “generator”, biasa ditulis G =
. 25
GRUP SIKLIS Definisi 2.6.1 Suatu grup G dan suatu unsur g G, jika grup G dapat dinyatakan sebagai G = { gn / n Z }, maka g dikatakan pembangun dari grup G dan grup G disebut grup siklis, biasanya dinotasikan G =
Perlu diingat... definisi grup siklis G = { gn / n Z } digunakan operasi perkalian, tetapi apabila grup G dengan operasi penjumlahan, maka definisi grup siklis menjadi G = { n g / n Z } =
Contoh: 1. Misalnya untuk n = 6, grup itu ialah G = { e , a , a2 , a3 , a4 , a5 } Grup semacam ini biasa dinyatakan dengan C6, yaitu grup siklis berorder 6, ( |G| = 6 ) Grup siklis berorde n dinyatakan dengan Cn. 2. Himpunan bilangan-bilangan bulat modulo n dengan operasi penjumlahan modulo n merupakan suatu grup siklis.
28
‣ Misalkan G = Z6 = { 0 , 1 , 2 , 3 , 4 , 5 }, adalah grup siklik dengan elemen pembangunnya 1, G = <1>, sebab: 10 = 0, 13 = 3, 11 = 1, 14 = 4, 12 = 2, 15 = 5. ‣ dapat juga dibangun oleh 5, G = <5>, sebab: 50 = 0, 51 = 5, 52 = 5 + 5 = 4, 53 = 5 + 5 + 5 = 3, 54 = 5 + 5 + 5 + 5 = 2, 55 = 5 + 5 + 5 +5 + 5 = 1. ‣ Apakah masih ada unsur pembangun lainnya? 29
3. (Z,+) adalah grup siklis dengan unsur pembangun 1 dan -1. 4. 3Z merupakan subgrup siklis yang dibangun oleh 3, sehingga 3Z = <3>
5. Himpunan operasi simetri dari bangun kitiran ini terdiri dari rotasi dengan titik pusat O, dengan sudut rotasi 90o, 180o, 270o, dan 360o O Jika (O,90o)=S, maka (O,180o)=S2, (O,270o)=S3, dan (O,360o)=I Jadi G = { I , S , S2 , S3 } merupakan grup siklis dengan pembangun S, G = <S>, dan order G sama dengan 4 Tentukan order dan invers dari S, S2, dan S3.
31
6. Perhatikan segi-5 beraturan dengan pusat O dan
3
4
O 5
72
2
o
1
sudut-sudut rotasi 72o, 144o, 216o, 288o, dan 360o.
Jika (O,72o)=S, maka (O,144o)=S2, (O,216o)=S3, (O,288o)=S4, dan (O,360o)=I
Sehingga { I , S , S2 , S3 , S4 } merupakan suatu grup siklis dengan order 5. Tampak pula, bahwa |S| = 5, |S2| = 5, |S3| = 5, |S4| = 5 Disamping S, maka S2, S3, dan S4 dapat menjadi pembangun. 32
Orde dari grup siklis Bila G grup siklis dibangun oleh unsur g, maka orde G adalah sama dengan orde dari unsur pembangunnya yaitu ( g )
Lemma 2.6.2 Bila G suatu grup , g G maka H={gn/nZ } merupakan subgrup terkecil dalam G yang dibangun oleh unsur g Lemma 2.6.3 Setiap grup siklis G = adalah grup abel
Lemma 2.6.5 Subgrup dari grup siklis adalah siklis Lemma 2.6.7 Dua grup siklis dengan orde yang sama akan berkorespondensi 1 - 1
Contoh • Z =<1> = <-1> dan 3Z subgrupdari Z dengan 3Z = <3> = <-3>. jika didefinisikan f: Z 3Z n Z, berlaku f(n) = 3n 3Z,
maka • f bersifat pada, karena bila diambil sebarang x 3Z haruslah x = 3m, untuk suatu m Z. Ini berarti ada m Z sedemikian hingga f(m) = x = 3m atau f pemetaan pada. • f juga pemetaan 1-1, karena bila diambil unsur f(n) = f(m) maka diperoleh 3n = 3m atau n=m. • Mengingat f pemetaan pada dan 1-1, maka f korespondensi 1-1.
Lemma 2.6.8 Bila G suatu grup sebarang, g G dan misalkan n , m Z sehingga gn = 1 dan juga gm = 1, maka gd = 1 di mana d = (m, n). Khususnya bila gs = 1 untuk suatu s Z, maka orde dari g membagi s. Dalam hal ini d = (m,n) dimaksudkan d merupakan pembagi persekutuan terbesar dari m dan n
Lemma 2.6.9 Misalkan G = < g > dengan n unsur, dan misalkan h = gs, s Z adalah unsur dalam G, maka h akan membangun subgrup siklis H dalam G yang berorde n/d, di mana d membagi persekutuan terbesar dari n dan s atau d = (n , s ).
Contoh • Grup (Z12,+) adalah grup siklis dan Z12=<1>=<5> =<7>=<11> FPB dari 3 dan 12 • misal diambil 3 Z12, karena 3 = (3,12) maka H=<3>={0,3,6,9} subgrup dari Z12 dengan orde 12/3 = 4 • misal diambil 4 Z12, karena 4 = (4,12) maka H=<4>={0,4,8} subgrup dari Z12 dengan orde 12/4 = 3 • Bagaimana dengan 5? H=<5>= Z12
Menentukan unsur pembangun Apabila g membangun grup siklis berhingga G berorde n, maka pembangun lainnya dari G adalah unsur-unsur berbentuk gs, di mana s relatif prim dengan n, atau (s,n) = 1.
Contoh • Tentukan semua subgrup yg mungkin dari Z18 Diperoleh: • Unsur pembangun Z18 adalah 1,5,7,11 • Subgrup dengan orde terbesar dibangun oleh unsur 2, dengan orde 18/2 =9, sehingga <2> = {0,2,4,6,8,10,12,14,16}
• Selanjutnya mencari semua subgrup dalam <2> • Menentukan unsur pembangun dari <2>, berupa 2h dg h relatif prim dg orde <2>, yaitu 9. diperoleh h = 1,2,4,5,7,8 sehingga <2>=<4>=<10>=<14>=<16> • Unsur yg tdk membangun <2> adalah 6 dan 12, sehingga <6> = {0,6,12} =<12> subgrup dr <2>
