Posted on

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.

Posted on

Dua Soal Struktur Aljabar ONMIPA 2016

Pada tulisan kali ini akan dibahas tentang soal ONMIPA 2016 bidang matematika untuk sub-bidang struktur aljabar.

Soal Hari Pertama

Misalkan {x} pembagi nol kiri dan {y} pembagi nol kanan di suatu ring hingga {R}. Buktikan bahwa {xy} sekaligus merupakan pembagi nol kiri dan kanan.

Beberapa peserta berhasil menyelesaikan masalah ini. Solusi alamiah muncul dari sebuah wishful thinking, kalau saja {y} juga merupakan pembagi nol kiri, yakni ada {u\neq 0} sehingga {yu=0} maka {xy} akan menjadi pembagi nol kiri, karena {xyu=x(yu)=x\cdot 0=0}. Sekarang memangnya kenapa jika {y} bukan pembagi nol kiri ? Jika {y} bukan pembagi nol kiri maka pemetaan {s\mapsto ys} dari {R} ke {R} merupakan pemetaan yang injektif (periksa!). Karena {R} hingga maka pemetaan ini juga surjektif. Karena {x} pembagi nol kiri, maka ada {v\neq 0} sehingga {xv=0}. Karena {s\mapsto ys} surjektif, ada {t\in R} sehingga {yt=v}. Ini mengakibatkan {xyt=xv=0}. Jadi {xy} pembagi nol kiri.

Untuk menunjukkan bahwa {xy} juga merupakan pembagi nol kanan, kami serahkan kepada pembaca.

Cara lain yang lebih teoretis adalah dengan pertama membuktikan lemma berikut

Bukti Lain

Lemma 1 {a\neq 0} merupakan pembagi nol kanan jika dan hanya jika {Ra\subset R} (subset sejati). Proof: Jika {a} bukan pembagi nol kanan, maka pemetaan {u\mapsto ua} tidak injektif dan akibanya tidak surjektif (karena {R}) hingga. dengan demikian {Ra} subset sejati dari {R}. Sebaliknya jika {Ra} subset sejati dari {R} maka {u\mapsto ua} tidak surjektif dan akibatnya tidak injektif. Berarti ada {u\neq v} sehingga {ua=va}, yang berakibat {(u-v)a=0}. Jadi {a} pembagi nol kanan. \Box Untuk pembagi nol kiri kita punya lema yang serupa. Lemma 2 {a\neq 0} merupakan pembagi nol kiri jika dan hanya jika {aR\subset R}. Sekarang jika {x} pembagi nol kiri dan {y} pembagi nol kanan maka {xR\subset R} dan {Ry\subset R}. Karena {(xy)R=x(yR)\subseteq xR\subset R} maka {xy} pembagi nol kiri. Demikian pula karena {R(xy)=(Rx)y\subseteq Ry\subset R} maka {xy} pembagi nol kanan.

[collapse]

Soal tentang struktur aljabar berikutnya adalah sebagai berikut:

Soal Hari Kedua

Misalkan {G} grup berorde {n} dan {p} adalah bilangan prima terkecil sehingga {p} membagi {n}. Jika {H} adalah satu-satunya subgrup dari {G} berorde {p}, tunjukkan bahwa {gh=hg} untuk setiap {g\in G} dan {h\in H}.

Bukti 1

Ambil {g\in G}. Perhatikan bahwa {gHg^{-1}} juga merupakan subgrup berorde {p}. Dari kondisi yang diberikan soal kita peroleh {gHg^{-1}=H}. Akibatnya pemetaan {f:H-\{e\}\rightarrow H-\{e\}} melalui {f(h)=ghg^{-1}} terdefinisi dengan baik. Mudah diperiksa bahwa pemetaan ini merupakan suatu pemetaan bijektif. Karenanya kita bisa melihat {f} sebagai permutasi atas {p-1} unsur, yakni {f\in S_{p-1}}. Karena {|S_{p-1}|=(p-1)!} maka {f^{(p-1)!}= \text{pemetaan identitas }}. Perhatikan bahwa {f^{n}(h)=g^nh(g^{-1})^n=h} (karena {g^n=e} untuk setiap {g\in G}). Dengan demikian orde {f} sekaligus membagi {(p-1)!} dan membagi {n}. Jika orde {f} adalah {t\neq 1} maka {t} mempunyai faktor prima {q}. Karena {t\mid (p-1)!} dan {t\mid n} maka {q\mid n} dan {q\mid (p-1)!} sehingga {q\leq p-1} adalah bilangan prima yang kurang dari {p} yang membagi {n} (kontradiksi!). Jadi haruslah orde {f} adalah 1 atau dengan kata lain {ghg^{-1}=h\Leftrightarrow gh=hg}.

[collapse]
Bukti 2

Cara lain dengan menggunakan aksi grup adalah sebagai berikut. Tinja aksi dari {G} terhadap {H} dengan konjugasi {g\cdot h=ghg^{-1}} untuk setiap {g\in G} dan {h\in H}. Aksi ini terdefinisi dengan baik karena {gHg^{-1}=H}. Ambil {h\neq e} di {H}. Menurut teorema orbit-stabilizer kita peroleh \displaystyle |G|=|\text{orbit}(h)||G_h| dengan {\text{orbit }(h)=\{ghg^{-1}\mid g\in G\}} dan {G_h=\{g\in G\mid ghg^{-1}=h\}}. Karena {h\neq e} maka {ghg^{-1}\neq e} untuk setiap {g\in G} atau dengan kata lain {e\not \in \text{orbit }(h)}. Jadi {|\text{orbit} (h)|\leq p-1}. Jika {|\text{orbit} (h)|> 1} maka ada prima {q} sehingga {q\mid |\text{orbit} (h)| \mid n}. Jadi {q\mid n} dan {q\leq p-1} yang bertentangan dengan fakta bahwa {p} adalah prima terkeil yang membagi {n}. Jadi haruslah {|\text{orbit} (h)|=1}. Karena {h\in \text{orbit} (h)} maka haruslah {ghg^{-1}=h \Leftrightarrow gh=hg} untuk setiap {g\in G}.

[collapse]