Bagian 14.8 Sage

Kita mungkin mengira perlu berhati-hati terhadap cara Sage mendefinisikan konjugasi (\(gxg^{-1}\) dibandingkan dengan \(g^{-1}xg\)) dan perbedaan antara Sage dan teks dalam urutan hasil kali. Namun, jika Anda melihat definisi pusat dan subgrup pemusat, akan tampak bahwa perbedaan urutan apa pun tidak relevan. Berikut adalah perintah aksi grup untuk aksi khusus berupa konjugasi unsur-unsur grup.

Sage memiliki metode grup permutasi .center() yang mengembalikan subgrup titik tetap. Metode grup permutasi .centralizer(g) mengembalikan subgrup yang merupakan penstabil unsur grup g. Terakhir, orbit-orbit diberikan oleh kelas-kelas konjugasi, tetapi Sage tidak akan membanjiri Anda dengan kelas konjugasi lengkap dan sebagai gantinya mengembalikan daftar berisi satu unsur dari setiap kelas konjugasi, yaitu wakil-wakilnya, melalui metode grup permutasi .conjugacy_classes_representatives(). Anda dapat merekonstruksi kelas konjugasi secara manual dari suatu wakil, seperti yang kita lakukan dalam contoh berikut.

Berikut adalah contoh penggunaan perintah-perintah di atas. Perhatikan bahwa grup abelian bukan pilihan yang baik untuk contoh ini.

D = DihedralGroup(8)
C = D.center(); C

Subgroup generated by [(1,5)(2,6)(3,7)(4,8)]
of (Dihedral group of order 16 as a permutation group)

C.list()

[(), (1,5)(2,6)(3,7)(4,8)]

a = D("(1,2)(3,8)(4,7)(5,6)")
C1 = D.centralizer(a); C1.list()

[(), (1,2)(3,8)(4,7)(5,6), (1,5)(2,6)(3,7)(4,8), (1,6)(2,5)(3,4)(7,8)]

b = D("(1,2,3,4,5,6,7,8)")
C2 = D.centralizer(b); C2.order()

8

CCR = D.conjugacy_classes_representatives(); CCR

[(), (2,8)(3,7)(4,6), (1,2)(3,8)(4,7)(5,6), (1,2,3,4,5,6,7,8),
 (1,3,5,7)(2,4,6,8), (1,4,7,2,5,8,3,6), (1,5)(2,6)(3,7)(4,8)]

r = CCR[2]; r

(1,2)(3,8)(4,7)(5,6)

conj = []
x = [conj.append(g^-1*r*g) for g in D if not g^-1*r*g in conj]
conj

[(1,2)(3,8)(4,7)(5,6),
 (1,6)(2,5)(3,4)(7,8),
 (1,8)(2,7)(3,6)(4,5),
 (1,4)(2,3)(5,8)(6,7)]

Perhatikan bahwa dalam satu kelas konjugasi yang dikonstruksi, semua unsur memiliki struktur siklus yang sama, dan ini bukan suatu kebetulan. Perhatikan pula bahwa rep dan a merupakan unsur yang sama, dan hasil kali orde pemusat (\(4\)) dengan ukuran kelas konjugasi (\(4\)) sama dengan orde grup (\(16\)), yang merupakan variasi dari kesimpulan Teorema 14.1.11.

Verifikasikan bahwa berikut ini merupakan demonstrasi persamaan kelas dalam kasus khusus ketika aksinya adalah konjugasi, tetapi berlaku untuk sebarang grup, bukan hanya D.

sizes = [D.order()/D.centralizer(g).order()
             for g in D.conjugacy_classes_representatives()]
sizes

[1, 4, 4, 2, 2, 2, 1]

D.order() == sum(sizes)

True

Seperti telah disebutkan, aksi grup dapat menjadi lebih menarik lagi ketika himpunan yang dikenai aksi berbeda dari grup itu sendiri. Salah satu kelas contoh adalah grup simetri suatu bangun ruang geometris, dengan objek dalam himpunannya berupa titik-titik sudut bangun tersebut, atau mungkin aspek lain seperti rusuk, permukaan, atau diagonal. Dalam kasus ini, grup tersebut terdiri atas semua permutasi yang menggerakkan bangun ruang, tetapi membuatnya mengisi ruang yang sama seperti sebelum gerakan (“gerak kaku”).

Dalam bagian ini kita akan memeriksa sesuatu yang sangat serupa. Suatu graf adalah objek matematis yang terdiri atas simpul dan sisi, dengan satu-satunya struktur berupa apakah suatu pasangan simpul dihubungkan oleh sisi. Grupnya terdiri atas permutasi simpul yang mempertahankan struktur tersebut, yaitu permutasi simpul yang membawa sisi ke sisi dan pasangan bukan-sisi ke pasangan bukan-sisi. Hal ini sangat serupa dengan grup simetri, tetapi tidak terdapat gagasan bahwa suatu hubungan geometris harus dipertahankan.

Berikut adalah sebuah contoh. Anda perlu menjalankan sel komputasi pertama untuk mendefinisikan graf dan memperoleh representasi grafis yang baik.

Q = graphs.CubeGraph(3)
Q.plot(layout='spring')

A = Q.automorphism_group()
A.order()

48

Plot Anda seharusnya menyerupai simpul dan sisi kubus, tetapi mungkin tidak tampak sepenuhnya beraturan, dan hal itu tidak menjadi masalah, sebab geometrinya tidak relevan. Simpul-simpul diberi label berupa untai tiga digit biner, \(0\) atau \(1\text{,}\) dan sebarang dua simpul dihubungkan oleh suatu sisi jika untainya berbeda pada tepat satu posisi. Kita mungkin mengharapkan grup simetrinya berorde \(24\text{,}\) bukan berorde \(48\text{,}\) mengingat kemiripannya dengan kubus (dalam rupa maupun nama). Namun, ketika tidak dibatasi pada gerak kaku, kita memperoleh permutasi baru yang mempertahankan sisi. Salah satunya adalah mempertukarkan dua “permukaan yang berhadapan.” Temukan dua siklus-\(4\) yang saling berhadapan dan dicantumkan dalam urutan yang sama: \(000, 010, 110, 100\) dan \(001, 011, 111, 101\text{.}\) Perhatikan bahwa setiap siklus tampak sangat serupa, tetapi semua simpul pada siklus pertama berakhir dengan nol, sedangkan simpul-simpul pada siklus kedua berakhir dengan satu.

Kita dapat membuat secara eksplisit permutasi yang mempertukarkan kedua permukaan berhadapan ini dengan menggunakan versi teks permutasi dalam notasi siklus.

a = A("('000','001')('010','011')('110','111')('100','101')")
a in A

True

Kita dapat menggunakan grup ini untuk mengilustrasikan perintah Sage yang relevan bagi aksi grup.

A.orbits()

[['000', '001', '010', '100', '011', '101', '110', '111']]

len(A.orbits()[0])

Jadi, aksi ini hanya memiliki satu orbit (besar). Hal ini menyiratkan bahwa setiap simpul “serupa” dengan simpul lainnya. Ketika suatu grup permutasi berperilaku seperti ini, kita mengatakan bahwa grup tersebut transitif.

A.is_transitive()

True

Jika setiap simpul “sama”, kita dapat menghitung penstabil sebarang simpul, sebab semuanya akan isomorfik. Karena simpul \(000\) dalam arti tertentu merupakan yang paling sederhana, kita menghitung penstabilnya.

S = A.stabilizer('000')
S.list()

[(),
 ('001','010','100')('011','110','101'),
 ('001','100','010')('011','101','110'),
 ('010','100')('011','101'),
 ('001','010')('101','110'),
 ('001','100')('011','110')]

Fakta bahwa S memiliki \(6\) unsur tidaklah mengejutkan, sebab grup tersebut berorde \(48\) dan ukuran satu-satunya orbit adalah \(8\text{.}\) Namun, kita dapat melangkah lebih jauh. Tiga simpul graf yang terhubung langsung dengan \(000\) adalah \(100\text{,}\) \(010\text{,}\) \(001\text{.}\) Setiap automorfisme graf yang menetapkan \(000\) harus mempermutasikan ketiga simpul yang berdekatan tersebut. Terdapat \(3!=6\) cara yang mungkin untuk melakukan hal ini, dan Anda dapat memeriksa bahwa masing-masing muncul dalam salah satu dari enam unsur penstabil. Jadi, kita dapat memahami suatu grup transitif dengan meninjau penstabil yang lebih kecil, dan dalam kasus ini kita dapat melihat bahwa setiap unsur penstabil ditentukan oleh caranya mempermutasikan tetangga dari simpul yang distabilkan.

Grup transitif bersifat tidak lazim sekaligus penting. Sebagai pembanding, berikut adalah grup automorfisme graf yang jauh dari transitif (tanpa bersifat trivial). Lintasan adalah graf yang semua simpulnya berada pada satu garis. Jalankan sel komputasi pertama untuk melihat lintasan pada \(11\) simpul.

P = graphs.PathGraph(11)
P.plot()

A = P.automorphism_group()
A.list()

[(), (0,10)(1,9)(2,8)(3,7)(4,6)]

Grup automorfismenya terdiri atas automorfisme identitas trivial (yang selalu ada) dan suatu permutasi berorde \(2\) yang “membalik” lintasan dari ujung ke ujung. Grup tersebut jauh dari transitif dan memiliki banyak orbit.

A.is_transitive()

False

A.orbits()

((0, 10), (1, 9), (2, 8), (3, 7), (4, 6), (5,))

Sebagian besar penstabil bersifat trivial, dengan satu pengecualian. Sebagai subgrup dari grup berorde \(2\text{,}\) pilihannya memang tidak terlalu banyak.

A.stabilizer(2).list()

[()]

A.stabilizer(5).list()

[(), (0,10)(1,9)(2,8)(3,7)(4,6)]

Bagaimanakah contoh terakhir ini akan berbeda jika kita menggunakan lintasan pada \(10\) simpul?

CATATAN: Dahulu terdapat galat kecil yang menyebabkan penstabil dibuat sebagai subgrup dari grup simetris pada simbol yang jumlahnya lebih sedikit daripada seharusnya. Hal ini telah diperbaiki dalam Sage 4.8 dan versi yang lebih baru. Perhatikan keluaran yang benar berikut, dan Anda dapat memeriksa instalasi Anda dengan menjalankan perintah-perintah ini. Jika Anda tidak melihat singleton [4] dalam keluaran, Anda sebaiknya memperbarui Sage Anda.

G = SymmetricGroup(4)
S = G.stabilizer(4)
S.orbits()

((1, 2, 3), (4,))