Sidang Tugas Akhir

Gresi Garnita
G54101029

Jumlah Maksimum Submatriks Ganjil Berukuran 2x2 dari Matriks-(0,1)

Matriks (0,1) adalah matriks yang unsur-unsurnya hanya terdiri dari angka 0 dan 1. Dari matriks ini akan ditentukan banyaknya submatriks ganjil berukuran 2 2× . Istilah submatriks ganjil pertama kali diperkenalkan oleh Pinelis pada tahun 1994 dalam karyanya yang berjudul Designs, Codes, and Cryptography. Dalam karyanya tersebut, Pinelis menotasikan N sebagai banyaknya submatriks yang mungkin diperoleh dari matriks (0,1) dan E sebagai submatriks genapnya, sehingga banyaknya submatriks ganjil dapat diperoleh dengan mengurangkan N oleh E . Akan tetapi pada tahun 2003, Mark dkk. menemukan formula (teorema) yang dapat langsung digunakan untuk mencari sumatriks ganjil tanpa harus menentukan N dan E terlebih dahulu, melainkan melalui matriks Hadamardnya. Matriks Hadamard adalah matriks yang unsurunsurnya hanya memuat angka 1 dan -1 dan memiliki sifat nI AAT = dan nI A AT = . Banyaknya submatriks ganjil dari matriks (0,1) merupakan perkalian antara kombinasi pemilihan 2 baris dari m baris dengan banyaknya kolom yang unsur-unsurnya sama dan banyanya kolom yang unsurunsurnya tidak sama. Banyaknya submatriks ganjil dari matriks (0,1) akan bernilai maksimum jika banyaknya kolom yang unsur-unsurnya sama dengan banyaknya kolom yang unsur-unsurnya tidak sama bernilai sama atau mendekati sama. Dengan demikian banyaknya submatriks ganjil berukuran 2 2× akan bernilai maksimum jika matriks Hadamard dari matriks (0,1) ada dan jika sembarang baris dari m baris di hapus dari matriks tersebut, maka matriks dengan m sisa penghapusannya akan tetap bernilai maksimum. Selain itu, jika matriks B yang diperoleh dari A dengan menukar setiap pasang baris, mengganti unsur 0 dengan 1 dan unsur 1 dengan 0, juga dengan melakukan transpose matriks, maka banyaknya submatriks ganjil pada kedua matriks tersebut adalah sama.