Grup Permutasi dan Simetri

1. Konsep Dasar

A. Definisi Permutasi

Misal S ≠ ∅. Permutasi di S adalah fungsi bijektif yang memetakan dari S ke S.

B. Definisi Grup Permutasi dan Simetri

Grup simetri di S adalah grup semua permutasi di S, disimbolkan dengan Sim(S). Setiap subgrup dari grup simetri disebut grup permutasi. Untuk |S| = n, dapat disimbolkan Sim(S) sebagai Sₙ.

C. Penyajian Permutasi dalam Matriks

Misal τ ∈ Sₙ. Permutasi τ dapat disajikan sebagai matriks dua baris, dimana baris pertama berisikan 1, 2, 3, ..., n; adapun baris kedua berisikan τ(1), τ(2),  ..., τ(n).

Sebagai contoh, permutasi

menyatakan permutasi yang memetakan 1 ke 2, 2 ke 3, 3 ke 4 dan 4 ke 1.

Sedangkan komposisi dibaca dari kanan ke kiri, contohnya

Sedangkan invers dengan menukar baris, contohnya:

Secara umum, mudah dimengerti bahwa banyak kemungkinan permutasi di Sₙ adalah n!, karena permutasi ini seperti menyusun n objek.

D. Penyajian Permutasi dalam Siklus

Selain dalam bentuk matriks, permutasi juga dapat dinyatakan dalam bentuk siklus. Secara umum, permutasi dinyatakan sebagai komposisi dari beberapa siklus.

Orde dari siklus sama dengan panjang siklus, dimana orde dari (a₁ a₂ ... aₖ) adalah k.

Sebagai contoh, permutasi yang memetakan 1 ke 2, 2 ke 3, 3 ke 4 dan 4 ke 1 dapat dituliskan sebagai siklus (1 2 3 4).

Sedangkan komposisi (1 3 4 2)(1 2 3 4) = (1)(4 2 3), bentuk ini dapat disederhanakan menjadi (2 3 4), dimana elemen 1 yang tidak ditukar dengan elemen lain tidak perlu dituliskan.

Untuk invers dengan membalik urutan, contohnya (1 3 4 2)⁻¹ = (2 4 3 1) = (1 2 4 3).

E. Siklus Saling Lepas

1. Definisi Siklus Saling Lepas

Misal siklus a = (a₁ a₂ ... aₖ) dan b = (b₁ b₂ ... bₗ). Keduanya dikatakan saling lepas jika himpunan {a₁, a₂, ..., aₖ} dan {b₁, b₂, ..., bₗ} saling lepas.

Secara umum, permutasi dapat dinyatakan sebagai komposisi dari beberapa siklus yang saling lepas.

Misal diberikan permutasi α ∈ S₉ sebagai berikut:

kita dapat menyatakan α = (1 5 6)(2 8)(3 7 4 9).

2. Sifat Komutatif

Jika α dan β adalah permutasi-permutasi di Sₙ yang saling asing, maka komposisinya bersifat komutatif, artinya α ∘ β = β ∘ α.

Bukti:

Ambil sebarang a ∈ Iₙ dengan sifat α(a) ≠ a. Karena α dan β saling asing diperoleh β(a) = a. Misalkan α(a) = b, maka

(α ∘ β)(a) = α(β(a)) = α(a) = b

dan

(β ∘ α)(a) = β(α(a)) = β(b).

Jika α(b) = b, maka α(b) = α(a) = b sehingga a = b. Padahal a ≠ b, yaitu ditemukan suatu kontradiksi. Akibatnya haruslah α(b) ≠ b, sehingga β(b) = b. Jadi

(β ∘ α)(a) = β(α(a)) = β(b) = b.

Akibatnya (α ∘ β)(a) = (β ∘ α)(a).

Misalkan β(a) ≠ a. Dengan argumentasi yang mirip dengan sebelumnya diperoleh kesimpulan (α ∘ β)(a) = (β ∘ α)(a). Jadi α ∘ β = β ∘ α. □

F. Penggeseran Simbolis Siklus

Penggeseran simbolis menyatakan siklus yang sama.

Sebagai contoh, siklus (1 2 3 4) bisa juga dinyatakan sebagai (2 3 4 1), (3 4 1 2), maupun (4 1 2 3). Semuanya sama-sama memetakan 1 ke 2, 2 ke 3, 3 ke 4, dan 4 ke 1.

2. Transposisi

A. Definisi Transposisi

Transposisi adalah siklus yang hanya terdiri dari dua elemen.

Transposisi juga dapat disebut sebagai penukaran.

Contoh: siklus yang memetakan 1 ke 2 dan 2 ke 1, disimbolkan (1 2), siklus ini juga dapat dikatakan menukar 1 dengan 2.

B. Invers Transposisi

Invers dari transposisi adalah dirinya sendiri.

Misal suatu transposisi menukar elemen a dan b, disimbolkan (a, b). Sebagaimana bentuk umum untuk invers adalah dengan membalik urutan menjadi (b, a), yang mana ini sama dengan (a, b) menurut fakta penggeseran.

C. Eksistensi Transposisi

"Setiap permutasi dapat dinyatakan sebagai komposisi dari transposisi."

Untuk permutasi identitas, sangat mudah menyatakannya, yaitu cukup dengan mengkomposisikan dua transposisi yang sama.

Untuk transposisi, juga mudah, yaitu dengan mengkomposisikan dirinya sebanyak tiga kali.

Adapun permutasi yang lebih rumit, kita perlu mencarinya dengan lebih kreatif. Secara umum, cara menyatakannya tidaklah tunggal.

Sebagai contoh (1 3 4 2) = (1 2)(1 4)(1 3) = (1 4)(1 2)(1 3)(2 3)(2 4).

D. Permutasi Ganjil dan Permutasi Genap

"Banyak transposisi yang diperlukan untuk menyatakan suatu permutasi tertentu di Sₙ sebagai komposisi transposisi selalu genap atau selalu ganjil."

Permutasi yang dapat dinyatakan sebagai komposisi sebanyak genap transposisi disebut permutasi genap, sedangkan permutasi yang dapat dinyatakan sebagai komposisi sebanyak ganjil transposisi disebut permutasi ganjil.

Invers dari permutasi genap adalah permutasi genap dan invers dari permutasi ganjil adalah permutasi ganjil.

E. Siklus Sebagai Komposisi Transposisi

Siklus (a₁ a₂ ... aₖ₋₁ aₖ) dapat dinyatakan sebagai (a₁ aₖ)(a₁ aₖ₋₁)···(a₁ a₂).

Akibatnya, siklus ganjil merupakan permutasi genap dan siklus genap merupakan permutasi ganjil.

F. Subgrup Permutasi Genap

"Misal himpunan Aₙ ⊂ Sₙ adalah himpunan semua permutasi genap di Sₙ. Himpunan ini membentuk subgrup dengan banyak anggotanya ½·n!."

Komposisi sesama permutasi genap menghasilkan permutasi genap.

Komposisi sebanyak ganjil permutasi ganjil menghasilkan permutasi ganjil dan komposisi sebanyak genap permutasi ganjil menghasilkan permutasi genap.

Komposisi permutasi genap dengan permutasi ganjil menghasilkan permutasi ganjil.

3. Lebih Lanjut Permutasi

A. Kelas Ekivalensi / Orbit

Setiap permutasi τ dari himpunan S = {1, 2, ..., n} membangkitkan kelas-kelas ekivalensi yang saling asing dari S. Dua elemen a, b ∈ S yang berada di kelas yang sama, dinotasikan a ~ b, jika terdapat bilangan bulat k sehingga b = τᵏ(a), yang artinya b dapat diperoleh dengan mengenakan τ pada a sebanyak k kali. Perlu diketahui bahwa relasi "~" merupakan relasi ekivalensi, dimana:

1. Refleksif

Untuk sebarang a ∈ S, jelas bahwa a = ι(a) = τ⁰(a), yang berarti a ~ a.

2. Simetris

Untuk sebarang a, b ∈ S; dengan a ~ b, terdapat bilangan bulat k sehingga b = τᵏ(a).

Karena τ bijektif, τᵏ juga bijektif, sehingga memiliki invers, yaitu τ⁻ᵏ, sehingga a = τ⁻ᵏ(b).

Jadi, jika a ~ b maka b ~ a.

3. Transitif

Untuk sebarang a, b, c ∈ S; dengan a ~ b, terdapat bilangan bulat k sehingga b = τᵏ(a); juga b ~ c, terdapat bilangan bulat l sehingga c = τˡ(b) = τˡ(τᵏ(a)) = τˡ⁺ᵏ(a).

Jadi, jika a ~ b dan b ~ c, maka a ~ c.

Misal diberikan permutasi τ. Kelas-kelas saling asing dari S yang dibentuk oleh "~" disebut orbit dari τ.

Sebagai contoh, diberikan permutasi α ∈ S₉ sebagai berikut:

Kita dapat menyatakan 6 = α²(1), berarti 1 ~ 6, juga 3 = α³(7), berarti 7 ~ 3, dan lain-lain. Selengkapnya, kita memperoleh kelas-kelas {1, 5, 6}, {2, 8}, dan {3, 7, 4, 9}.

Orbit dari α adalah {1, 5, 6}, {2, 8}, dan {3, 7, 4, 9}.

B. Grup Selang-Seling

Misal himpunan Aₙ ⊂ Sₙ adalah himpunan semua permutasi genap di Sₙ. Himpunan ini membentuk subgrup yang disebut sebagai grup selang-seling (alternating group).

Contoh:

S₃ terdiri dari e, (1 2), (1 3), (2 3), (1 2 3), dan (1 3 2).

Perhatikan bahwa e = (1 2)(1 2), (1 2 3) = (1 3)(1 2), (1 3 2) = (1 2)(1 3).

Jadi, A₃ = {e, (1 2 3), (1 3 2)}.

C. Eksistensi Siklus-3

Jika n > 2, maka Aₙ dibangun oleh siklus-3 di Sₙ.

Bukti:

Perhatikan suatu elemen di Aₙ yang merupakan hasil kali berikut (a b) ∘ (c d) atau (a b) ∘ (a c) dengan a, b, c, d berbeda-beda. Perhatikan juga bahwa

(a b) ∘ (a c) = (a c b)

dan

(a b) ∘ (c d) = (a c b) ∘ (a c d).

Jadi terbukti setiap elemen di Aₙ dibangun oleh siklus-3. □

D. Konjugat Permutasi

1. Definisi

Diberikan α, β ∈ Sₙ. Permutasi α dan β dikatakan konjugat jika (∃γ ∈ Sₙ) ∋ γ ∘ α ∘ γ⁻¹ = β.

2. Perolehan Konjugat

Diberikan siklus σ = (a₁ a₂ ... aₖ) di Sₙ. Untuk sebarang α ∈ Sₙ diperoleh:

α ∘ σ ∘ α⁻¹ = (α(a₁) α(a₂) ... α(aₖ)).

4. Grup Dihedral

A. Definisi Grup Dihedral

Grup dihedral adalah grup simetri dari poligon beraturan yang meliputi refleksi dan rotasi.

B. Anggota Grup Dihedral

Grup dihedral dari segi-n beraturan, disimbolkan Dₙ, terdiri dari n rotasi dan n refleksi, sehingga memiliki sebanyak 2n anggota.

Elemen-elemen dari Dₙ adalah rotasi r₀, r₁, ..., rₙ₋₁ dan refleksi s₀, s₁, ..., sₙ₋₁.

C. Pengenaan Fungsi Dihedral pada Titik

Misal titik-titik pada segi-n beraturan disimbolkan v₀, v₁, v₂, ..., vₙ₋₁; dikenakan rotasi menjadi:

rₖ(vₘ) = vₖ₊ₘ; dimana k + m merupakan hasil penjumlahan modular pada ℤₙ.

Tentu saja sangat mudah dimengerti bahwa r₀ merupakan elemen identitas Dₙ.

Sedangkan hasil refleksi dari titik-titik v₀, v₁, v₂, ..., vₙ₋₁ adalah:

sₖ(vₘ) = vₖ₋ₘ; dimana k – m merupakan hasil pengurangan modular pada ℤₙ.

D. Komposisi Fungsi Dihedral

Perhatikan bahwa

rᵢrⱼ(vₘ) = rᵢ(vⱼ₊ₘ) = vᵢ₊ⱼ₊ₘ = rᵢ₊ⱼ(vₘ)

rᵢsⱼ(vₘ) = rᵢ(vⱼ₋ₘ) = vᵢ₊ⱼ₋ₘ = sᵢ₊ⱼ(vₘ)

sᵢrⱼ(vₘ) = sᵢ(vⱼ₊ₘ) = vᵢ₋ⱼ₋ₘ = sᵢ₋ⱼ(vₘ)

sᵢsⱼ(vₘ) = sᵢ(vⱼ₋ₘ) = vᵢ₋ⱼ₊ₘ = rᵢ₋ⱼ(vₘ)

Jadi, hasil komposisi fungsi-fungsi dihedral adalah:

rᵢrⱼ = rᵢ₊ⱼ;    rᵢsⱼ = sᵢ₊ⱼ;    sᵢrⱼ = sᵢ₋ⱼ;     sᵢsⱼ = rᵢ₋ⱼ; dengan operasi indeksnya merupakan penjumlahan dan pengurangan modular.

Beberapa poin yang kita peroleh:

• Komposisi sesama rotasi bersifat komutatif, adapun komposisi dengan adanya refleksi tidak komutatif.

• Komposisi dua fungsi sejenis menghasilkan rotasi, sedangkan komposisi dua fungsi tidak sejenis menghasilkan refleksi.

Jika dikembangkan lebih lanjut, hasil komposisi yang lebih rumit bergantung pada banyaknya fungsi refleksi. Untuk komposisi rumit dengan sebanyak ganjil refleksi menghasilkan refleksi, sedangkan komposisi rumit dengan sebanyak genap refleksi menghasilkan rotasi.

E. Invers Fungsi Dihedral

Invers dari rₖ adalah r₋ₖ = rₙ₋ₖ, sedangkan invers dari refleksi adalah dirinya sendiri.

F. Grup Rotasi

Misal rot(Dₙ) menyatakan subset dari Dₙ yang beranggotakan rotasi pada Dₙ. Kita memperoleh bahwa rot(Dₙ) merupakan subgrup dari Dₙ, dimana operasi komposisi rotasi bersifat tertutup, asosiatif, memiliki elemen identitas (yaitu r₀) dan invers.