Lewati ke konten utama

Bagian 5.1 Definisi dan Notasi

Secara umum, permutasi suatu himpunan \(X\) membentuk grup \(S_X\text{.}\) Jika \(X\) merupakan himpunan hingga, kita dapat mengasumsikan \(X=\{ 1, 2, \ldots, n\}\text{.}\) Dalam hal ini kita menulis \(S_n\) sebagai pengganti \(S_X\text{.}\) Teorema berikut menyatakan bahwa \(S_n\) merupakan grup. Grup ini kita sebut grup simetris pada \(n\) huruf.

Bukti.
Identitas \(S_n\) tidak lain adalah pemetaan identitas yang membawa \(1\) ke \(1\text{,}\) \(2\) ke \(2\text{,}\) \(\ldots\text{,}\) \(n\) ke \(n\text{.}\) Jika \(f : S_n \rightarrow S_n\) merupakan permutasi, maka \(f^{-1}\) ada, karena \(f\) injektif dan surjektif; jadi, setiap permutasi memiliki invers. Komposisi pemetaan bersifat asosiatif, sehingga operasi grup tersebut bersifat asosiatif. Bukti bahwa \(|S_n|= n!\) diserahkan sebagai latihan.
Subgrup dari \(S_n\) disebut grup permutasi.

Contoh 5.1.2.

Perhatikan subgrup \(G\) dari \(S_5\) yang terdiri atas permutasi identitas \(\identity\) dan permutasi
\begin{align*} \sigma & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 5 & 4 \end{pmatrix}\\ \tau & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 1 & 4 & 5 \end{pmatrix}\\ \mu & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 1 & 5 & 4 \end{pmatrix}\text{.} \end{align*}
Tabel berikut menunjukkan cara mengalikan elemen-elemen dalam grup permutasi \(G\text{.}\)
\begin{equation*} \begin{array}{c|cccc} \circ & \identity & \sigma & \tau & \mu \\ \hline \identity & \identity & \sigma & \tau & \mu \\ \sigma & \sigma & \identity & \mu & \tau \\ \tau & \tau & \mu & \identity & \sigma \\ \mu & \mu & \tau & \sigma & \identity \end{array} \end{equation*}

Catatan 5.1.3.

Walaupun wajar mengalikan elemen suatu grup dari kiri ke kanan, fungsi dikomposisikan dari kanan ke kiri. Misalkan \(\sigma\) dan \(\tau\) merupakan permutasi pada himpunan \(X\text{.}\) Untuk mengomposisikan \(\sigma\) dan \(\tau\) sebagai fungsi, kita menghitung \((\sigma \circ \tau)(x) = \sigma( \tau(x))\text{.}\) Artinya, kita menerapkan \(\tau\) terlebih dahulu, kemudian \(\sigma\text{.}\) Ada beberapa cara untuk mengatasi ketidakkonsistenan ini. Kita akan menggunakan konvensi mengalikan permutasi dari kanan ke kiri. Untuk menghitung \(\sigma \tau\text{,}\) terapkan \(\tau\) terlebih dahulu, kemudian \(\sigma\text{.}\) Artinya, dengan \(\sigma \tau (x)\) kita maksudkan \(\sigma( \tau( x))\text{.}\) (Cara lain untuk menyelesaikan masalah ini ialah menulis fungsi di sebelah kanan; yaitu, alih-alih menulis \(\sigma(x)\text{,}\) kita dapat menulis \((x)\sigma\text{.}\) Kita juga dapat mengalikan permutasi dari kiri ke kanan agar sesuai dengan cara biasa mengalikan elemen dalam grup. Semua metode ini memang pernah digunakan.

Contoh 5.1.4.

Perkalian permutasi biasanya tidak komutatif. Misalkan
\begin{align*} \sigma & = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \end{pmatrix}\\ \tau & = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \end{pmatrix}\text{.} \end{align*}
Maka
\begin{equation*} \sigma \tau = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \end{pmatrix}\text{,} \end{equation*}
tetapi
\begin{equation*} \tau \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 4 \end{pmatrix}\text{.} \end{equation*}

Subbagian 5.1.1 Notasi Siklus

Notasi yang sejauh ini kita gunakan untuk menyatakan permutasi terasa rumit, kalau tidak ingin disebut sangat merepotkan. Agar dapat bekerja secara efektif dengan grup permutasi, kita memerlukan cara yang lebih ringkas untuk menuliskan dan memanipulasi permutasi.
Suatu permutasi \(\sigma \in S_X\) merupakan siklus dengan panjang \(k\) jika terdapat elemen \(a_1, a_2, \ldots, a_k \in X\) sedemikian sehingga
\begin{align*} \sigma( a_1 ) & = a_2\\ \sigma( a_2 ) & = a_3\\ & \aatavdots{=}\\ \sigma( a_k ) & = a_1 \end{align*}
dan \(\sigma( x) = x\) untuk semua elemen lain \(x \in X\text{.}\) Kita akan menulis \((a_1, a_2, \ldots, a_k )\) untuk menyatakan siklus \(\sigma\text{.}\) Siklus merupakan unsur pembangun semua permutasi.

Contoh 5.1.5.

Permutasi
\begin{equation*} \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7\\ 6 & 3 & 5 & 1 & 4 & 2 & 7 \end{pmatrix} = (1\, 6\, 2\, 3\, 5\, 4 ) \end{equation*}
merupakan siklus dengan panjang \(6\text{,}\) sedangkan
\begin{equation*} \tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 4 & 2 & 3 & 5 & 6 \end{pmatrix} = (2\, 4\, 3) \end{equation*}
merupakan siklus dengan panjang \(3\text{.}\)
Tidak setiap permutasi merupakan siklus. Perhatikan permutasi
\begin{equation*} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 4 & 1 & 3 & 6 & 5 \end{pmatrix} = (1\, 2\, 4\, 3)(5\, 6)\text{.} \end{equation*}
Permutasi ini sebenarnya memuat satu siklus dengan panjang \(2\) dan satu siklus dengan panjang \(4\text{.}\)

Contoh 5.1.6.

Hasil kali siklus sangat mudah dihitung. Misalkan
\begin{equation*} \sigma = (1\, 3\, 5\, 2 ) \quad \text{dan} \quad \tau = (2\, 5\, 6)\text{.} \end{equation*}
Jika kita memandang \(\sigma\) sebagai
\begin{equation*} 1 \mapsto 3, \qquad 3 \mapsto 5, \qquad 5 \mapsto 2, \qquad 2 \mapsto 1\text{,} \end{equation*}
dan \(\tau\) sebagai
\begin{equation*} 2 \mapsto 5, \qquad 5 \mapsto 6, \qquad 6 \mapsto 2\text{,} \end{equation*}
maka untuk \(\sigma \tau\text{,}\) dengan mengingat bahwa kita menerapkan \(\tau\) terlebih dahulu kemudian \(\sigma\text{,}\) harus berlaku
\begin{equation*} 1 \mapsto 3, \qquad 3 \mapsto 5, \qquad 5 \mapsto 6, \qquad 6 \mapsto 2 \mapsto 1\text{,} \end{equation*}
atau \(\sigma \tau = (1 \, 3 \, 5 \, 6 )\text{.}\) Jika \(\mu = (1 \, 6 \, 3 \, 4)\text{,}\) maka \(\sigma \mu = (1\, 6\, 5\, 2)(3\, 4)\text{.}\)
Dua siklus dalam \(S_X\text{,}\) \(\sigma = (a_1, a_2, \ldots, a_k )\) dan \(\tau = (b_1, b_2, \ldots, b_l )\text{,}\) dikatakan saling lepas jika \(a_i \neq b_j\) untuk semua \(i\) dan \(j\text{.}\)

Contoh 5.1.7.

Siklus \((1\, 3\, 5)\) dan \((2\, 7 )\) saling lepas; namun, siklus \((1\, 3\, 5)\) dan \((3\, 4\, 7 )\) tidak saling lepas. Dengan menghitung hasil kalinya, kita peroleh
\begin{align*} (1\, 3\, 5)(2\, 7 ) & = (1\, 3\, 5)(2\, 7 )\\ (1\, 3\, 5)(3\, 4\, 7 ) & = (1\, 3\, 4\, 7\, 5)\text{.} \end{align*}
Hasil kali dua siklus yang tidak saling lepas mungkin dapat disederhanakan; hasil kali siklus-siklus yang saling lepas tidak dapat disederhanakan.

Bukti.
Misalkan \(\sigma = (a_1, a_2, \ldots, a_k )\) dan \(\tau = (b_1, b_2, \ldots, b_l )\text{.}\) Kita harus menunjukkan bahwa \(\sigma \tau(x) = \tau \sigma(x)\) untuk semua \(x \in X\text{.}\) Jika \(x\) tidak berada dalam \(\{ a_1, a_2, \ldots, a_k \}\) maupun \(\{b_1, b_2, \ldots, b_l \}\text{,}\) maka \(\sigma\) dan \(\tau\) keduanya menetapkan \(x\text{.}\) Artinya, \(\sigma(x)=x\) dan \(\tau(x)=x\text{.}\) Jadi,
\begin{equation*} \sigma \tau(x) = \sigma( \tau(x)) = \sigma(x) = x = \tau(x) = \tau( \sigma(x)) = \tau \sigma(x)\text{.} \end{equation*}
Jangan lupa bahwa kita mengalikan permutasi dari kanan ke kiri, berlawanan dengan urutan yang biasanya digunakan untuk mengalikan elemen grup. Sekarang andaikan \(x \in \{ a_1, a_2, \ldots, a_k \}\text{.}\) Maka \(\sigma( a_i ) = a_{(i \bmod k) + 1}\text{;}\) yaitu,
\begin{align*} a_1 & \mapsto a_2\\ a_2 & \mapsto a_3\\ & \aatavdots{\mapsto}\\ a_{k-1} & \mapsto a_k\\ a_k & \mapsto a_1\text{.} \end{align*}
Namun, \(\tau(a_i) = a_i\) karena \(\sigma\) dan \(\tau\) saling lepas. Oleh karena itu,
\begin{align*} \sigma \tau(a_i) & = \sigma( \tau(a_i))\\ & = \sigma(a_i)\\ & = a_{(i \bmod k)+1}\\ & = \tau( a_{(i \bmod k)+1} )\\ & = \tau( \sigma(a_i) )\\ & = \tau \sigma(a_i)\text{.} \end{align*}
Demikian pula, jika \(x \in \{b_1, b_2, \ldots, b_l \}\text{,}\) maka \(\sigma\) dan \(\tau\) juga komutatif.

Bukti.
Kita dapat mengasumsikan bahwa \(X = \{ 1, 2, \ldots, n \}\text{.}\) Jika \(\sigma \in S_n\) dan kita mendefinisikan \(X_1\) sebagai \(\{ \sigma(1), \sigma^2(1), \ldots \}\text{,}\) maka himpunan \(X_1\) hingga karena \(X\) hingga. Sekarang, misalkan \(i\) adalah bilangan bulat pertama dalam \(X\) yang tidak berada dalam \(X_1\) dan definisikan \(X_2\) dengan \(\{ \sigma(i), \sigma^2(i), \ldots \}\text{.}\) Sekali lagi, \(X_2\) merupakan himpunan hingga. Dengan melanjutkan cara ini, kita dapat mendefinisikan himpunan-himpunan hingga yang saling lepas \(X_3, X_4, \ldots\text{.}\) Karena \(X\) merupakan himpunan hingga, proses ini pasti berakhir dan hanya akan terdapat sejumlah hingga himpunan semacam itu, misalkan \(r\text{.}\) Jika \(\sigma_i\) adalah siklus yang didefinisikan oleh
\begin{equation*} \sigma_i( x ) = \begin{cases} \sigma( x ) & x \in X_i \\ x & x \notin X_i \text{,}\end{cases} \end{equation*}
maka \(\sigma = \sigma_1 \sigma_2 \cdots \sigma_r\text{.}\) Karena himpunan \(X_1, X_2, \ldots, X_r\) saling lepas, siklus \(\sigma_1, \sigma_2, \ldots, \sigma_r\) juga harus saling lepas.

Contoh 5.1.10.

Misalkan
\begin{align*} \sigma & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 4 & 3 & 1 & 5 & 2 \end{pmatrix}\\ \tau & = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 2 & 1 & 5 & 6 & 4 \end{pmatrix}\text{.} \end{align*}
Dengan menggunakan notasi siklus, kita dapat menulis
\begin{align*} \sigma & = (1 \, 6 \, 2 \, 4)\\ \tau & = (1 \, 3)(4 \, 5 \,6)\\ \sigma \tau & = (1 \, 3\, 6) ( 2\, 4\, 5)\\ \tau \sigma & = (1 \, 4\, 3 )(2 \, 5 \, 6)\text{.} \end{align*}

Catatan 5.1.11.

Mulai saat ini, penggunaan notasi siklus akan memudahkan kita dalam menyatakan permutasi. Ketika menggunakan notasi siklus, kita sering melambangkan permutasi identitas dengan \((1)\text{.}\)

Subbagian 5.1.2 Transposisi

Permutasi paling sederhana adalah siklus dengan panjang \(2\text{.}\) Siklus semacam itu disebut transposisi. Karena
\begin{equation*} (a_1, a_2, \ldots, a_n ) = (a_1, a_n ) (a_1, a_{n-1} ) \cdots ( a_1, a_3 ) (a_1, a_2 )\text{,} \end{equation*}
setiap siklus dapat ditulis sebagai hasil kali transposisi, kita memperoleh proposisi berikut.

Contoh 5.1.13.

Perhatikan permutasi
\begin{equation*} ( 1 \, 6 ) (2 \, 5\, 3) = (1 \, 6 )( 2 \, 3 )( 2 \, 5 ) = (1 \, 6 )( 4 \, 5 )(2 \, 3 )( 4 \, 5 )(2 \, 5 )\text{.} \end{equation*}
Seperti dapat kita lihat, tidak ada cara tunggal untuk menyatakan suatu permutasi sebagai hasil kali transposisi. Sebagai contoh, kita dapat menulis permutasi identitas sebagai \((1 \, 2 )(1 \, 2 )\text{,}\) sebagai \((1 \, 3 )(2 \, 4 )(1 \, 3 )( 2 \, 4 )\text{,}\) dan dengan banyak cara lainnya. Namun, ternyata tidak ada permutasi yang dapat ditulis sekaligus sebagai hasil kali sejumlah genap transposisi dan sejumlah ganjil transposisi. Sebagai contoh, kita dapat menyatakan permutasi \((1 \, 6)\) dengan
\begin{equation*} (2 \, 3 )(1 \, 6)( 2 \, 3) \end{equation*}
atau dengan
\begin{equation*} (3 \, 5) (1 \, 6) (1 \, 3) (1 \, 6) (1 \, 3) (3 \, 5) (5 \, 6)\text{,} \end{equation*}
tetapi \((1 \, 6)\) selalu merupakan hasil kali sejumlah ganjil transposisi.

Bukti.
Kita akan menggunakan induksi pada \(r\text{.}\) Suatu transposisi tidak mungkin merupakan identitas; jadi, \(r \gt 1\text{.}\) Jika \(r=2\text{,}\) pembuktian selesai. Andaikan \(r \gt 2\text{.}\) Dalam hal ini, hasil kali dua transposisi terakhir, \(\tau_{r-1} \tau_r\text{,}\) harus merupakan salah satu kasus berikut:
\begin{align*} (a, b)(a, b) & = \identity\\ (b, c)(a, b) & = (a, c)(b, c)\\ (c, d)(a, b) & = (a, b)(c, d)\\ (a, c)(a, b) & = (a, b)(b, c)\text{,} \end{align*}
dengan \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) dan \(d\) semuanya berbeda.
Persamaan pertama hanya menyatakan bahwa suatu transposisi merupakan invers dirinya sendiri. Jika kasus ini terjadi, hapus \(\tau_{r-1} \tau_r\) dari hasil kali untuk memperoleh
\begin{equation*} \identity = \tau_1 \tau_2 \cdots \tau_{r - 3} \tau_{r - 2}\text{.} \end{equation*}
Berdasarkan induksi, \(r - 2\) genap; jadi, \(r\) harus genap.
Dalam setiap tiga kasus lainnya, kita dapat mengganti \(\tau_{r - 1} \tau_r\) dengan ruas kanan persamaan yang bersesuaian untuk memperoleh hasil kali baru dari \(r\) transposisi bagi identitas. Dalam hasil kali baru ini, kemunculan terakhir \(a\) berada pada transposisi kedua dari belakang. Kita dapat melanjutkan proses ini dengan \(\tau_{r - 2} \tau_{r - 1}\) untuk memperoleh hasil kali dari \(r - 2\) transposisi atau hasil kali baru dari \(r\) transposisi dengan kemunculan terakhir \(a\) berada dalam \(\tau_{r - 2}\text{.}\) Jika identitas merupakan hasil kali dari \(r - 2\) transposisi, sekali lagi pembuktian selesai berdasarkan hipotesis induksi; jika tidak, kita mengulangi prosedur tersebut dengan \(\tau_{r - 3} \tau_{r - 2}\text{.}\)
Pada suatu tahap, kita akan memperoleh dua transposisi identik yang berdampingan dan saling menghapus, atau \(a\) akan digeser sehingga hanya muncul dalam transposisi pertama. Namun, kasus terakhir tidak mungkin terjadi, karena dalam keadaan ini identitas tidak akan menetapkan \(a\text{.}\) Oleh karena itu, permutasi identitas harus merupakan hasil kali dari \(r-2\) transposisi dan, sekali lagi berdasarkan hipotesis induksi, pembuktian selesai.

Bukti.
Andaikan
\begin{equation*} \sigma = \sigma_1 \sigma_2 \cdots \sigma_m = \tau_1 \tau_2 \cdots \tau_n\text{,} \end{equation*}
dengan \(m\) genap. Kita harus menunjukkan bahwa \(n\) juga merupakan bilangan genap. Invers dari \(\sigma\) adalah \(\sigma_m \cdots \sigma_1\text{.}\) Karena
\begin{equation*} \identity = \sigma \sigma_m \cdots \sigma_1 = \tau_1 \cdots \tau_n \sigma_m \cdots \sigma_1\text{,} \end{equation*}
\(n\) harus genap berdasarkan Lema 5.1.14. Bukti untuk kasus ketika \(\sigma\) dapat dinyatakan sebagai sejumlah ganjil transposisi diserahkan sebagai latihan.
Berdasarkan Teorema 5.1.15, kita mendefinisikan suatu permutasi sebagai genap jika dapat dinyatakan sebagai sejumlah genap transposisi, dan sebagai ganjil jika dapat dinyatakan sebagai sejumlah ganjil transposisi.

Subbagian 5.1.3 Grup Alternasi

Salah satu subgrup terpenting dari \(S_n\) adalah himpunan semua permutasi genap, \(A_n\text{.}\) Grup \(A_n\) disebut grup alternasi pada \(n\) huruf.

Bukti.
Karena hasil kali dua permutasi genap juga harus merupakan permutasi genap, \(A_n\) tertutup. Identitas merupakan permutasi genap sehingga berada dalam \(A_n\text{.}\) Jika \(\sigma\) merupakan permutasi genap, maka
\begin{equation*} \sigma = \sigma_1 \sigma_2 \cdots \sigma_r\text{,} \end{equation*}
dengan \(\sigma_i\) merupakan transposisi dan \(r\) genap. Karena invers setiap transposisi adalah dirinya sendiri,
\begin{equation*} \sigma^{-1} = \sigma_r \sigma_{r-1} \cdots \sigma_1 \end{equation*}
juga berada dalam \(A_n\text{.}\)

Bukti.
Misalkan \(A_n\) adalah himpunan permutasi genap dalam \(S_n\) dan \(B_n\) adalah himpunan permutasi ganjil. Jika kita dapat menunjukkan bahwa terdapat bijeksi di antara kedua himpunan ini, keduanya harus memuat jumlah elemen yang sama. Tetapkan suatu transposisi \(\sigma\) dalam \(S_n\text{.}\) Karena \(n \geq 2\text{,}\) transposisi \(\sigma\) semacam itu ada. Definisikan
\begin{equation*} \lambda_{\sigma} : A_n \rightarrow B_n \end{equation*}
dengan
\begin{equation*} \lambda_{\sigma} ( \tau ) = \sigma \tau \text{.} \end{equation*}
Andaikan \(\lambda_{\sigma} ( \tau ) = \lambda_{\sigma} ( \mu )\text{.}\) Maka \(\sigma \tau = \sigma \mu\) sehingga
\begin{equation*} \tau = \sigma^{-1} \sigma \tau = \sigma^{-1} \sigma \mu = \mu\text{.} \end{equation*}
Oleh karena itu, \(\lambda_{\sigma}\) injektif. Bukti bahwa \(\lambda_{\sigma}\) surjektif diserahkan kepada pembaca.

Contoh 5.1.18.

Grup \(A_4\) merupakan subgrup dari \(S_4\) yang terdiri atas permutasi genap. Terdapat dua belas elemen dalam \(A_4\text{:}\)
\begin{align*} & (1) && (1 \, 2)(3 \, 4) && (1 \, 3)(2 \, 4) && (1 \, 4)(2 \, 3)\\ & (1 \, 2 \, 3) && (1 \, 3 \, 2) && (1 \, 2 \, 4) && (1 \, 4 \, 2)\\ & (1 \, 3 \, 4) && (1 \, 4 \, 3) && (2 \, 3 \, 4) && (2 \, 4 \, 3)\text{.} \end{align*}
Salah satu latihan akhir bab akan meminta Anda menuliskan semua subgrup \(A_4\text{.}\) Anda akan menemukan bahwa tidak ada subgrup berorde 6. Apakah hal ini mengejutkan Anda?

Subbagian 5.1.4 Catatan Historis

Lagrange adalah orang pertama yang memandang permutasi sebagai fungsi dari suatu himpunan ke dirinya sendiri, tetapi Cauchy-lah yang mengembangkan teorema dasar dan notasi permutasi. Ia merupakan orang pertama yang menggunakan notasi siklus. Augustin-Louis Cauchy (1789–1857) lahir di Paris pada puncak Revolusi Prancis. Keluarganya segera meninggalkan Paris menuju desa Arcueil untuk menghindari Pemerintahan Teror. Salah satu tetangga keluarganya di sana adalah Pierre-Simon Laplace (1749–1827), yang mendorongnya meniti karier dalam matematika. Cauchy memulai karier sebagai matematikawan dengan menyelesaikan masalah geometri yang diberikan kepadanya oleh Lagrange. Cauchy menulis lebih dari 800 makalah tentang topik yang sangat beragam, seperti persamaan diferensial, grup hingga, matematika terapan, dan analisis kompleks. Ia merupakan salah satu matematikawan yang berperan menjadikan kalkulus rigor. Mungkin lebih banyak teorema dan konsep matematika yang menyandang nama Cauchy daripada nama matematikawan lainnya.
Sblm.Paling AtasLanjut