Teorema Cauchy dan Kesederhanaan A5

Pada artikel ini kita akan buktikan Teorema Cauchy dan kemudian kita gunakan aplikasi sederhananya untuk menunjukkan bahwa grup alternating {A_5} sederhana. Bukti yang akan di berikan mengikuti buktinya McKay. Beliau membuktikan lemma yang lebih kuat berikut.

Lemma 1 (Mckay) Misalkan {G} suatu grup berorde {n} dan {p} adalah bilangan prima pembagi {n}. Maka banyaknya solusi dari {x^p=e} di {G} ada sebanyak {kp} untuk suatu {K\neq 0}.

Proof: Tinjau himpunan {S=\{(a_1,\ldots,a_p) : a_i\in G \text{ dan } a_1\cdots a_p=e\}}. Definisikan operator {\sigma}, operator pergeseran melingkar, melalui {\sigma(a_1,a_2,\ldots, a_p)=(a_p,a_1,\ldots, a_{p-1})}. Definisikan relasi ekivalen di {S}, dua tupel ekivalen jika kita bisa menerapkan operator {\sigma} beberapa kali kepada tupel yang satu untuk mendapatkan tupel yang lain. Perhatikan bahwa jika semua {a_1=\cdots=a_p} maka kelas ekivalen dari {(a_1,\ldots, a_p)} hanya berisi satu unsur. Jika ada dua komponen yang berbeda, yakni {a_i\neq a_j} untuk suatu {i,j}, setiap menerapkan operator {\sigma} kita akan memperoleh tupel yang baru. Baru setelah menerapkan {\sigma} sebanyak {p} kali kita kembali ke tupel semula. Dengan demikian dalam situasi ada dua komponen yang berbeda, kelas ekivalennya mengandung {p} unsur.

Sekarang perhatikan bahwa agar {a_1\cdots a_p=1} kita bisa memilih {a_1,\ldots, a_{p-1}} sembarang dan kemudian {a_p} ditentukan oleh pemilihan dari {a_1,\ldots, a_{p-1}} kita, yakni {a_p=(a_1\cdots a_{p-1})^{-1}}. Dengan demikian banyaknya anggota di {S} adalah sama dengan banyaknya cara memilih {a_1,\ldots, a_{p-1}} yakni sebanyak {n^{p-1}}.

Kelas-kelas ekivalen dari relasi ekivalen di atas mempartisi {S}. Misalkan ada {r} kelas ekivalen yang beranggotakan 1 unsur dan {t} kelas ekivalen yang beranggotakan {p} unsur. Akibatnya {r+tp=n^{p-1}}. Perhatikan bahwa menurut Teorema Little Fermat berlaku {n^{p-1}\equiv n {\pmod p}}. Karena {p} membagi {n} maka {p} membagi {n^{p-1}}. Akibatnya {p} juga membagi {r}. Perhatikan bahwa \{(e,e,\ldots,e)\} merupakan salah satu kelas ekivalen yang beranggotakan satu unsur. Dengan demikian {r\neq 0} dan {r=kp} dengan {k\neq 0}. \Box

Theorem 2 (Cauchy) Misalkan {G} grup dengan orde {n} dan {p} bilangan prima yang membagi {n}. Maka ada unsur di {G} yang berorde {p}.

Proof: Dari bukti Lemma McKay di atas kita melihat bahwa banyaknya solusi {x^p} dengan {x\neq e} ada sebanyak {kp-1\neq 0}. \Box

Dalam tulisan ini kita akan membuktikan bahwa {A_5}, grup yang memuat semua permutasi genap di {S_5}, merupakan grup yang simple.

Untuk bukti kesederhanaan {A_5} kita menggunakan argumen di bukunya Martin Isaacs Algebra. Dalam bukti ini akan dihindari penggunaan teorema Sylow yang biasanya belum diperoleh pada kuliah teori grup di tingkat sarjana.

Kita akan menggunakan lema berikut dalam pembuktian

Lemma 3 Dua unsur di {S_n} saling konjugat jika dan hanya jika keduanya mempunyai struktur putaran (cycle) yang sama.

Theorem 4 {A_5} merupakan grup yang sederhana.

Proof: Unsur-unsur di {A_5} mempunyai struktur putaran salah satu diantara struktur: {1^5, 1\cdot 2^2, 1^2\cdot 3, 5}. Masing-masingnya terdapat {1,15,20,24} unsur di {A_5} dengan struktur putaran tersebut.

Misalkan {N} adalah subgrup normal dari {A_5} dengan {N\neq {1}} dan {N\neq A_5}. Perhatikan bahwa {|A_5|=60=2^2\cdot 3\cdot 5}. Akibatnya faktor prima dari {|N|} adalah 2,3 atau 5.

Jika {3\mid |N|} maka menurut teorema Cauchy, ada unsur berorde 3 yang merupakan unsur di {N}. Unsur tersebut jelas adalah unsur yang mempunyai struktur putaran {1^2\cdot 3}. Berdasarkan lema semua unsur yang mempunyai struktur putaran ini saling konjugat satu sama lain. Karena subgrup normal {N} tertutup secara konjugasi maka {N} memuat semua unsur yang memiliki struktur putaran {1^2\cdot 3}. Khususnya {|N|>20}. Karena {|N|} membagi 60, maka haruslah {|N|=30}.

Jika {5\mid |N|}, kembali dengan teorema Cauchy, {N} memiliki unsur berorde 5 dan haruslah unsur dengan struktur putaran 5. Dengan kenormalan {N} maka ke 24 unsur yang memiliki struktur putaran 5 semuanya termuat di {N}. Jadi {|N|>24} dan karena {|N|} membagi {60} maka haruslah {|N|=30}.

Dengan demikian jika {3\mid |N|} atau {5\mid |N|} maka {|N|=30} yang mengakibatkan {3} dan {5} keduanya membagi {|N|}. Akan tetapi ini berarti semua unsur dengan struktur putaran {1^2\cdot 3} dan {5} termuat di {N}. Jadi {|N|>20+24=44} yang tidak mungkin karena {|N|=30}.

Sekarang misalkan {2\mid |N|}, maka dengan argumen yang serupa semua unsur dengan struktur putaran {1\cdot 2^2} semuanya terkandung di {N}. Jadi {|N|>15}. Ini berakibat {|N|=30} Tapi sudah kita tunjukkan di atas hal tersebut tidak mungkin. \Box

Rendered by QuickLaTeX.com

Mewarnai Kalung dengan Cauchy-Frobenius

1. Formula Cauchy-Frobenius

Misalkan grup {G} beraksi pada himpunan {\Omega}. Kita hendak menghitung banyaknya orbit dari aksi ini. Untuk setiap {g\in G} definisikan {\text{Fix}(g):=\{\alpha \in \Omega \mid \alpha\cdot g=\alpha\}} dan untuk setiap {\alpha \in \Omega} definisikan {G_\alpha:=\{g\in G\mid \alpha\cdot g=\alpha\}}.

Untuk menghitung banyaknya orbit dari aksi, pertama kita tinjau himpunan

\displaystyle  \mathcal{S}:=\{(\alpha,g)\mid \alpha\cdot g=\alpha\}

Kita akan menghitung banyaknya kardinalitas dari {\mathcal{S}}. Misalkan unsur-unsur di {\Omega} adalah {\alpha_1,\ldots, \alpha_s} dan unsur-unsur di {G} adalah {g_1,\ldots, g_t}. Definisikan matriks {M=(m_{ij})} dengan

\displaystyle  m_{ij}:=\begin{cases}1& \text{ jika } (\alpha_i,g_j)\in \mathcal{S}\\ 0&\text{ jika } (\alpha_i,g_j)\not\in \mathcal{S} \end{cases}

Banyaknya angka 1 pada baris ke-{i} adalah banyaknya {g\in G} sehingga {\alpha_i\cdot g=\alpha_i}, yakni {|G_{\alpha_i}|}. Sehingga banyaknya total angka 1 yang terdapat pada matriks {M} adalah

\displaystyle  \sum_{i=1}^s |G_{\alpha_i}|=\sum_{\alpha \in \Omega} |G_\alpha|.

Di lain pihak kita bisa menghitung banyaknya angka 1 pada {M} kolom-demi kolom. Banyaknya angka 1 pada kolom ke-{j} sama dengan banyaknya {i=1,\ldots,s} sehingga {(\alpha_i,g_j)\in S}, yakni sebesar {|\text{Fix}(g_i)|}. Dengan demikian banyaknya total angka 1 pada matriks {M} adalah

\displaystyle  \sum_{j=1}^t |\text{Fix}(g_j)|=\sum_{g\in G} |\text{Fix}(g)|.

Karena kedua hal di atas menghitung dua objek yang sama, maka

\displaystyle  \sum_{g\in G} |\text{Fix}(g)|=\sum_{\alpha \in \Omega} |G_\alpha|

Bagi kedua ruas dengan {|G|} kita peroleh

    \begin{align*} \frac{1}{|G|}\sum_{g\in G} |\text{Fix}(g)|&=\sum_{\alpha \in \Omega} \frac{|G_\alpha|}{|G|}\\ &=\sum_{\alpha \in \Omega} \frac{1}{|O_\alpha|} \end{align*}

Misalkan {O_1,O_2,\ldots, O_k} adalah orbit-orbit yang mempartisi {\Omega}. Maka

    \begin{align*} \sum_{\alpha \in \Omega} \frac{1}{|O_\alpha|}&=\sum_{i=1}^k \sum_{\alpha \in O_i} \frac{1}{|O_\alpha|}\\ &= \sum_{i=1}^k \frac{|O_i|}{|O_i|}\\ &=k\\ &= \text{banyaknya orbit} \end{align*}

Dengan demikian

\displaystyle  \text{banyaknya orbit }=\frac{1}{|G|}\sum_{g\in G} |\text{Fix}(g)|.

Berikut contoh aplikasi sederhana dari Teorema Cauchy-Frobenius yang dikenal juga sebagai Teorema Frobenius yang menurut beberapa matematikawan merupakan pengatributan yang keliru kepada Burnside.

Example 1 Misalkan kita ingin membuat kalung manik-manik yang terdiri dari 6 butiran manik-manik. Jenis manik-manik yang tersedia ada 2 warna, berwarna hitam dan putih. Kita ingin menghitung banyaknya cara membuat manik-manik seperti itu. Perhatikan bahwa dua kalung manik-manik kita anggap sama jika kita bisa merotasi kalung yang satu untuk mendapatkan konfigurasi manik-manik pada kalung kedua.

Kita tinjau himpunan semua warna kalung sebagai himpunan

\displaystyle C=\{(c_1,c_2,\ldots, c_6)\mid c_i=1 \text{ atau } c_i=0\}

dengan {c_i=1} jika manik-manik {i} berwarna hitam dan {c_i=0} jika manik-manik {i} berwarna putih. Himpunan semua rotasi pada 6 buah manik-manik bisa kita nyatakan sebagai grup {G=\langle \tau \rangle} dengan {\tau} adalah putaran {(1\,2\,3\,4\,5\,6)}. Perhatikan bahwa {G=\{\text{id},\tau,\tau^2\tau^3,\tau^4,\tau^5\}} dengan {\tau} bisa kita anggap juga sebagai rotasi sebesar {60^\circ} searah jarum jam.

Disini kita melihat bahwa {G} beraksi pada {C} dengan rotasi. Misalkan diberikan kalung dengan konfigurasi {c=(1,1,0,1,0,0)} maka semua hasil rotasi dari {c} dianggap sebagai konfigurasi kalung yang sama atau dengan kata lain mereka semua tinggal dalam satu orbit. Pewarnaan kalung yang berbeda menyatakan orbit yang lain. Dengan demikian yang kita cari adalah banyaknya orbit dari aksi {\langle \tau\rangle} terhadap {C}.

Kita akan menghitung banyaknya orbit ini dengan menggunakan Teorema Cauchy-Frobenius dengan cara menghitung {|\text{Fix}(\tau^i)|} untuk {i=0,1,2,3,4,5}.

  1. Pertama kita akan menghitung banyaknya unsur di {\text{Fix (id)}}. Oleh pemetaan {\text{id}} setiap {c\in C} dipetakan ke dirinya sendiri. Semua konfigurasi kalung yang mungkin merupakan anggota {\text{Fix(id)}}. Dengan {|\text{Fix (id)}|=|C|=2^6}.
  2. Oleh {\tau} konfigurasi {(c_1,c_2,c_3,c_4,c_5,c_6)} dibawa ke konfigurasi {(c_6,c_1,c_2,c_3,c_4,c_5)}. Dengan demikian {(c_1,\ldots,c_6)\in \text{Fix}(\tau)} jika {c_6=c_1} kemudian {c_1=c_2} dan seterusnya sehingga berturut-turut kita memiliki {c_6=c_1=c_2=c_3=c_4=c_5}. Dengan demikian pewarnaan kalung bergantung pada salah satu manik-manik saja, misal {c_1}. Banyaknya cara untuk mewarnai {c_1} dengan dua warna adalah {2^1} cara. Jadi {|\text{Fix}(\tau)|=2^1}. Dengan cara yang serupa, karena {\tau^5=\tau^{-1}} adalah rotasi 60 derajat berlawanan arah kita dapatkan pula {|\text{Fix}(\tau^5)|=2^1}.
  3. Jika {c\in \text{Fix}(\tau)} maka konfigurasi {(c_1,c_2,c_3,c_4,c_5,c_6)} haruslah sama dengan {(c_5,c_6,c_1,c_2,c_3,c_4)} dengan demikian {c_1=c_5=c_3} dan {c_2=c_4=c_6}. Jadi pewarnaan kalung ditentukan oleh warna {c_1} dan {c_2}. Ada {2^2} cara untuk mewarnai {c_1} dan {c_2}. Dengan demikian {|\text{Fix}(\tau^2)|=2^2}. Dengan cara yang sama {|\text{Fix}(\tau^4)|=|\text{Fix}(\tau^{-2})|=2^2}.
  4. Oleh {\tau^3}, {(c_1,c_2,c_3,c_4,c_5,c_6)} di petakan menjadi {(c_4,c_5,c_6,c_1,c_2,c_3)}. Jadi haruslah {c_1=c_4,c_2=c_5} dan {c_3=c_6}. Pewarnaan kalung ditentukan oleh pewarnaan {c_1,c_2,c_3}, Jadi {|\text{Fix}(\tau^3)|=2^3}.

Sekarang menurut Teorema Cauchy-Frobenius banyaknya pewarnaan kalung adalah

    \[  \frac{1}{6}\left(2^6+2^1+2^1+2^2+2^2+2^3\right)=14.\]

Jadi ada 14 konfigurasi kalung yang mungkin.