Matriks yang semua entrinya berupa
\(0\) dan
\(1\) muncul dalam banyak konteks kombinatorial. Di sini kita menyajikan hasil klasik yang disebut teorema Gale-Ryser. Teorema ini membahas matriks nol–satu dengan string jumlah baris dan jumlah kolom yang ditentukan. Jika
\(M\) merupakan matriks berukuran
\(m\times n\) nol–satu, string
\(R=(r_1,r_2,\dots,r_m)\text{,}\) dengan
\(r_i=\sum_{1\le j\le n}m_{i,j}\text{,}\) disebut
string jumlah baris dari
\(M\text{.}\) String jumlah kolom \(C=(c_1,c_2,\dots,c_n)\) didefinisikan secara analog. Sebaliknya, misalkan
\(m\) dan
\(n\) bilangan bulat positif, serta
\(R=(r_1,r_2,\dots,r_m)\) dan
\(C=(c_1,c_2,\dots,c_n)\) string bilangan bulat tak negatif. Pertanyaannya adalah apakah terdapat matriks berukuran
\(m\times n\) nol–satu
\(M\) dengan string jumlah baris
\(R\) dan string jumlah kolom
\(C\text{.}\)
Untuk menangani masalah ini, kita berhenti sejenak guna mengembangkan beberapa materi latar tambahan. Perhatikan bahwa tanpa mengurangi keumuman kita dapat mengandaikan terdapat bilangan bulat positif
\(t\) sehingga
\(\sum_{i=1}^mr_i=\sum_{j=1}^nc_j=t\text{;}\) jika tidak, jelas tidak ada matriks nol–satu dengan string jumlah baris
\(R\) dan string jumlah kolom
\(C\text{.}\) Selain itu, kita dapat mengandaikan bahwa
\(R\) dan
\(C\) sama-sama merupakan string tak menaik, i.e.,
\(r_1\ge r_2\ge \dots\ge r_m\) dan
\(c_1\ge c_2\ge\dots\ge c_n\text{.}\)
Untuk melihatnya, perhatikan bahwa setiap kali dua baris dalam matriks nol–satu dipertukarkan, string jumlah kolom tidak berubah. Karena itu, setelah permutasi baris yang sesuai, kita dapat mengandaikan
\(R\) tak menaik. Proses yang sama kemudian diterapkan pada kolom.
Terakhir, mudah dilihat bahwa kita dapat mengandaikan semua entri dalam
\(R\) dan
\(C\) berupa bilangan bulat positif, sebab nol dalam string-string ini bersesuaian dengan baris nol atau kolom nol dalam matriks. Dengan demikian, string jumlah baris
\(R\) dan string jumlah kolom
\(C\) dapat dipandang sebagai partisi bilangan bulat
\(t\text{,}\) topik yang pertama kali kita perkenalkan dalam
Bab 8.
Sepanjang sisa bagian ini, misalkan
\(t\) bilangan bulat positif dan
\(\cgP(t)\) menyatakan keluarga semua partisi bilangan bulat
\(t\text{.}\) Terdapat urutan parsial alami pada
\(\cgP(t)\) yang didefinisikan dengan menetapkan
\(V=(v_1,v_2,\dots,v_m) \ge W=(w_1,w_2,\dots,w_n)\) jika dan hanya jika
\(m\le n\) dan
\(\sum_{1\le i\le j}v_i\ge \sum_{1\le i\le j}w_i\) untuk setiap
\(j=1,2,\dots,m\text{,}\) i.e., barisan jumlah parsial bagi
\(V\) selalu paling sedikit sebesar barisan jumlah parsial bagi
\(W\text{,}\) suku demi suku. Sebagai contoh, dalam
[provisional cross-reference: fig-partitionlattice] kita menampilkan urutan parsial
\(\cgP(7)\text{.}\)
GAMBAR BELUM TERSEDIA DALAM SUMBER
Dalam bukti teorema Gale-Ryser, kita perlu memahami sepenuhnya kapan suatu partisi menutupi partisi lainnya. Proposisi berikut dinyatakan secara khusus untuk menekankan hal tersebut; buktinya cukup dengan menelaah perincian definisi urutan parsial pada partisi.
Proposisi 16.11.
Misalkan \(V=(v_1,v_2,\dots,v_m)\) dan \(W=(w_1,w_2,\dots,w_n)\) partisi suatu bilangan bulat \(t\text{.}\) Jika \(V\) menutupi \(W\) dalam poset \(\cgP(t)\text{,}\) maka \(n\le m+1\) dan terdapat bilangan bulat \(i\) serta \(j\) dengan \(1\le i\lt j\le n\) sehingga pernyataan-pernyataan berikut berlaku.
-
\(v_\alpha=w_\alpha\text{,}\) apabila
\(1\le \alpha\lt i\text{.}\)
-
\(v_\beta=w_\beta\text{,}\) apabila
\(j\lt \beta\le m\text{.}\)
-
-
Salah satu dari (a)
\(j\le m\) dan
\(w_j=1+v_j\text{,}\) atau (b)
\(j=n=m+1\) dan
\(w_j=1\text{,}\) berlaku.
-
Jika
\(j>i+1\text{,}\) maka
\(w_\gamma=v_\gamma=v_i-1\) apabila
\(i\lt \gamma\lt j\text{.}\)
Untuk menggambarkan konsep ini, perhatikan bahwa
\((5,4,3)\) menutupi
\((5,3,3,1)\) dalam
\(\cgP(12)\text{.}\) Selain itu, kita melihat bahwa
\((6,6,4,3,3,3,1,1,1,1)\) menutupi
\((6,6,3,3,3,3,2,1,1,1)\) dalam
\(\cgP(29)\text{.}\)
Dengan suatu partisi
\(V=(v_1,v_2,\dots,v_m)\) dari
\(\cgP(t)\text{,}\) kita kaitkan
partisi dual \(W=(w_1,w_2,\dots,w_n)\) yang didefinisikan sebagai berikut: (1)
\(n=v_1\) dan, untuk setiap
\(j=1,\dots,n\text{,}\) \(w_j\) adalah banyaknya entri dalam
\(V\) yang paling sedikit sebesar
\(j\text{.}\) Sebagai contoh, partisi dual dari
\(V=(8,6,6,6,5,5,3,1,1,1)\) adalah
\((10,7,7,6,6,4,1,1)\text{.}\) Tentu saja, keduanya merupakan partisi dari
\(42\text{,}\) rahasia alam semesta! Selanjutnya, kita menyatakan dual dari partisi
\(V\) dengan
\(V^d\text{.}\) Perhatikan bahwa jika
\(W=V^d\text{,}\) maka
\(V=W^d\text{,}\) i.e., dual dari dual adalah partisi semula.
Subbagian 16.5.1 Syarat Perlu yang Jelas
Sekarang misalkan
\(M\) matriks berukuran
\(m\times n\) nol–satu dengan string jumlah baris
\(R=(r_1,r_2,\dots,r_m)\) dan string jumlah kolom
\(C=(c_1,c_2,\dots,c_n)\text{.}\) Seperti telah dicatat, kita mengandaikan semua entri dalam
\(R\) dan
\(C\) positif. Selanjutnya, kita mengubah
\(M\) untuk membentuk matriks baru
\(M'\) sebagai berikut: untuk setiap
\(i=1,2,\dots,m\text{,}\) kita menggeser
\(r_i\) buah satu pada baris
\(i\) sejauh mungkin ke kiri, i.e.,
\(m'_{i,j}=1\) jika dan hanya jika
\(1\le j\le r_i\text{.}\) Perhatikan bahwa
\(M\) dan
\(M'\) sama-sama mempunyai
\(R\) sebagai string jumlah baris. Namun, jika
\(C'\) menyatakan string jumlah kolom
\(M'\text{,}\) maka
\(C'\) merupakan string tak menaik, dan substring
\(C''\) dari
\(C'\) yang terdiri atas entri-entri positif adalah
\(R^d\text{,}\) partisi dual dari
\(R\text{.}\) Selain itu, untuk setiap
\(j=1,2,\dots,r_1\text{,}\) berlaku ketaksamaan
\(\sum_{1\le i\le j} c''_i\ge \sum_{1\le i\le j} c_i\text{,}\) sebab operasi menggeser satu ke kiri hanya dapat memperbesar jumlah parsial. Dengan demikian,
\(R^d\ge C\) dalam poset
\(\cgP(t)\text{.}\)
Jadi, berikut teorema Gale-Ryser.
Teorema 16.12. Gale-Ryser.
Misalkan
\(R\) dan
\(C\) partisi suatu bilangan bulat positif
\(t\text{.}\) Terdapat matriks nol–satu dengan string jumlah baris
\(R\) dan string jumlah kolom
\(C\) jika dan hanya jika
\(R^d\ge C\) dalam poset
\(\cgP(t)\text{.}\)
Bukti.
Keperluan syarat tersebut telah dibuktikan. Kita membuktikan kecukupannya. Bukti ini bersifat konstruktif. Dalam poset
\(\cgP(t)\text{,}\) misalkan
\(W_0>W_1>\dots>W_s\) suatu rantai sedemikian sehingga (1)
\(W_0=R^d\text{,}\) (2)
\(W_s=C\text{,}\) dan (3) jika
\(0\le p\lt s\text{,}\) maka
\(W_p\) menutupi
\(W_{p+1}\text{.}\) Kita mulai dengan matriks nol-satu
\(M_0\) yang mempunyai string jumlah baris
\(R\) dan string jumlah kolom
\(W_0\text{,}\) sebagaimana diilustrasikan dalam
[provisional cross-reference: fig-dualpartition] bagi partisi
\((8,4,3,1,1,1)\text{.}\) Jika
\(s=0\text{,}\) kita selesai. Jadi, andaikan untuk suatu
\(p\) dengan
\(0\le p\lt s\text{,}\) kita mempunyai matriks nol–satu
\(M_p\) dengan string jumlah baris
\(R\) dan string jumlah kolom
\(W_p\text{.}\) Misalkan
\(i\) dan
\(j\) bilangan bulat dari
Proposisi 16.11 yang menjelaskan cara
\(W_p\) menutupi
\(W_{p+1}\text{.}\) Pilih baris
\(q\) sedemikian sehingga entri
\(q,i\) dari
\(M_p\) adalah
\(1\text{,}\) sedangkan entri
\(q,j\) dari
\(M_p\) adalah
\(0\text{.}\) Pertukarkan kedua entri tersebut untuk membentuk matriks
\(M_{p+1}\text{.}\) Perhatikan bahwa pertukaran ini mungkin memang mengharuskan penambahan kolom baru pada matriks.
