I PENDAHULUAN menyelesaikan permasalahan-permasalahan matematika khususnya pada bidang riset operasi, salah satunya adalah mengaplikasikan sifat-sifat matriks kuasidefinit pada metode titik interior (interior-point method). Semua bahasan materi tentang matriks kuasidefinit pada karya ilmiah ini direkonstruksi dari tulisan Robert J. Vanderbei (1995) yang berjudul Symmetric Quasidefinite Matrices.
1.1 Latar Belakang Matriks merupakan istilah yang digunakan untuk menunjukkan jajaran persegi panjang dari bilangan-bilangan dan setiap matriks akan mempunyai baris dan kolom. Salah satu jenis matriks yang banyak digunakan adalah matriks simetrik. Matriks simetrik adalah matriks yang sama dengan transposnya yaitu matriks yang kolom-kolomnya adalah barisbaris matriks itu sendiri. Matriks yang dibahas pada tulisan ini adalah matriks kuasidefinit yang dipartisi menjadi empat blok dan memuat matriks definit positif. Matriks ini mempunyai sifatsifat yang dapat diterapkan untuk
1.2 Tujuan Tujuan dari karya ilmiah ini adalah untuk membuktikan beberapa sifat dari matriks kuasidefinit.
II LANDASAN TEORI Maksud dari bab ini adalah mengingatkan kembali tentang pengertian matriks, jenisjenis matriks dan memberikan penjelasan tentang matriks definit positif dan semidefinit positif serta beberapa sifatnya yang akan berguna dalam memahami tulisan ini secara keseluruhan.
1 , jika
1
dengan 1
det
,
1, … ,
adalah kofaktor-kofaktor yang diasosiasikan dengan entri-entri dalam baris pertama dari .
2.1 Matriks dan Determinan
[Leon 2001]
Definisi 2.1 (Matriks) Matriks merupakan kumpulan bilangan yang disusun dalam bentuk persegi panjang atau bujur sangkar dan setiap matriks akan mempunyai baris dan kolom. Secara umum matriks yang berukuran dapat ditulis dengan adalah unsur dengan matriks pada baris ke- dan kolom ke- , dan 1,2, … , ; 1,2, … , . Matriks dapat ditulis dalam bentuk:
Berikut ini akan diberikan pengertian beberapa jenis matriks dan sifat-sifatnya yang berhubungan dengan tulisan ini. Definisi 2.3 (Matriks Transpos) Transpos dari suatu matriks berukuran adalah matriks berukuran , ditulis yang diperoleh dengan mengganti setiap baris dari menjadi kolom dan , sebaliknya, sehingga jika maka . [Leon 2001] Teorema 2.1 (Beberapa Aturan Aljabar pada Matriks Transpos) 1. 2. 3.
[Leon 2001] Definisi 2.2 (Determinan) Determinan dari suatu matriks berukuran , dinyatakan sebagai det adalah suatu skalar yang diasosiasikan dengan matriks dan didefinisikan sebagai berikut:
[bukti lihat Leon 2001]
, jika
det
2 Contoh 2.3:
Definisi 2.4 (Matriks Simetrik) Suatu matriks berukuran simetrik jika .
disebut
invers
Contoh 2.1: Misalkan matriks Karena matriks
4 2 2 2 10 2 . 2 2 5 , maka matriks
adalah
Matriks
[Leon 2001]
2 3
2 4 3 1
dari
4 1 2 3
disebut matriks simetrik. Definisi 2.5 (Matriks Satuan) Matriks satuan adalah matriks berukuran dengan, 1, jika 0, jika dan berlaku matriks berukuran
untuk sembarang . [Leon 2001]
Definisi 2.6 (Matriks Permutasi) Suatu matriks berukuran disebut matriks permutasi, jika pada setiap baris dan kolomnya mempunyai tepat satu entri yang benilai 1 (satu) dan entri yang lainnya bernilai 0 (nol). [Horn & Johnson 1985] Contoh 2.2:
0 1 1 0 0 0 matriks permutasi dan 1 1 1 0 1 1 0 2 2 2 0 0 3 3 3 2 2 1 1 3 3 adalah suatu permutasi 1 1 1 2 2 2 . 3 3 3 Matriks
1 0
4 1
0 . 1
Teorema 2.2 (Sifat Matriks Invers) Jika adalah suatu matriks yang mempunyai invers (invertible), maka untuk sembarang skalar taknol k, matriks . [Anton 2000] Bukti: Jika k adalah sembarang skalar taknol, maka untuk membuktikan teorema di atas, sesuai dengan Definisi 2.7 akan ditunjukkan bahwa: . a. .
0 0 1 0 0 1 2 1 3 dari
adalah suatu
1 2 3
1 2 3
1 2 3
baris matriks
Definisi 2.7 (Matriks Taksingular dan Matriks Invers) Suatu matriks berukuran dikatakan taksingular atau mempunyai invers (invertible) jika terdapat matriks sehingga . Matriks disebut sebagai invers perkalian dari . [Leon 2001]
karena
. b. . . Jadi terbukti bahwa
.
Teorema 2.3 Suatu matriks berukuran singular, jika dan hanya jika det
■
adalah 0. [Leon 2001]
(bukti di Lampiran 1) Karena implikasi suatu pernyataan setara dengan kontraposisinya, ~ ~ dan ~ ~ maka ~ ~ . Jadi pernyataan pada Teorema 2.3 setara dengan pernyataan: Suatu matriks berukuran taksingular, jika dan hanya jika det
adalah 0.
3 Teorema 2.4 Jika adalah matriks taksingular, maka merupakan matriks taksingular dan . [Anton 2000] Bukti: Sesuai dengan Definisi ditunjukkan Teorema 2.1 diperoleh: •
2.7
akan . Dari
.
■
Definisi 2.10 (Submatriks) Suatu submatriks dari matriks adalah matriks yang diperoleh dengan menghilangkan baris dan/atau kolom dari . Perlu diketahui bahwa sembarang matriks adalah submatriks dari matriks itu sendiri, yaitu dengan menghilangkan 0 (nol) baris dan 0 (nol) kolom. [Harville 2008] Contoh 2.6: Misalkan diberikan matriks
• Jadi terbukti bahwa
Definisi 2.8 (Matriks Segitiga) Suatu matriks berukuran disebut matriks segitiga atas (upper triangular) jika 0 untuk dan matriks segitiga bawah (lower triangular) jika 0 untuk . disebut juga matriks segitiga (triangular) jika matriks segitiga atas atau matriks segitiga bawah. [Leon 2001]
2 1 2 3 1 2 0 6 . 1 3 6 9 Jika baris kedua dari matriks dihilangkan, maka diperoleh submatriks 2 1
Jika baris kedua, kolom pertama dan kolom ketiga dari matriks dihilangkan, maka akan diperoleh submatriks
Contoh 2.4: 3 2 0 2 0 0
1 1 0 dan 6 1 0
0 2 5
1 3
0 0 0
keduanya adalah matriks segitiga. Yang pertama adalah matriks segitiga atas dan yang kedua adalah matriks segitiga bawah. Definisi 2.9 (Matriks Diagonal) Suatu matriks berukuran matriks diagonal jika 0 untuk
disebut .
[Leon 2001] Contoh 2.5: 1 0
0 1
1 0 0
0 0 2 0 0 3
0 0 0
0 0 3 0 0 0
semuanya adalah matriks diagonal. Suatu matriks diagonal adalah matriks segitiga atas juga matriks segitiga bawah. 2.2 Submatriks Berikut ini akan diberikan pengertian tentang submatriks dan jenis-jenisnya yang berhubungan dengan tulisan ini.
1 2 3 . 3 6 9
3 . 9
Definisi 2.11 (Submatriks Utama) Misalkan himpunan bagian dari 1, 2, … , dan didefinisikan sebagai matriks yang diperoleh dengan menghilangkan baris dan kolom dari matriks berukuran yang letaknya merupakan komplemen dari himpunan pada . Maka disebut submatriks utama (principal submatrix) dari matriks . Jadi submatriks diperoleh dengan menghilangkan utama | | baris dan kolom yang bersesuaian, dengan | | adalah banyaknya elemen dari . [Horn & Johnson 1985] Contoh 2.7: Misalkan matriks 4 2 2 10 2 2
2 2 . 5
Beberapa submatriks utama yang dimiliki matriks adalah:
4 2 10 merupakan submatriks utama yang diperoleh dengan menghilangkan baris dan kolom pertama dan ketiga; 4 2 ii) 1,3 merupakan sub2 5 matriks utama yang diperoleh dengan menghilangkan baris dan kolom kedua; dan 4 2 2 iii) 1,2,3 2 10 2 merupakan 2 2 5 submatriks utama yang diperoleh dengan menghilangkan 0 (nol) baris dan 0 (nol) kolom.
i)
Definisi 2.12 (Submatriks Utama yang Pertama) Diberikan suatu matriks berukuran . Misalkan adalah matriks yang terbentuk dengan menghilangkan baris terakhir dan kolom terakhir dari , maka disebut submatriks utama yang pertama (leading principal submatrix) dari dengan yang berukuran 1 ). [Leon 2001] Contoh 2.8: Dari Contoh 2.7, submatriks utama pertama dari matriks adalah 4 2 4 2 ; dan 2 10 2 10 2 2
yang 4 ; 2 2 . 5
Teorema 2.5 Jika semua submatriks utama yang adalah matriks pertama dari matriks taksingular, maka terdapat matriks segitiga bawah dan dengan entri-entri 1 pada diagonal utama (unit lower triangular matrix) dan matriks diagonal yang memenuhi . [Golub & van Loan 1985]
10 20 25 40 50 61 0 0 10 1 0 0 4 1 0
0 0 5 0 0 1
1 1 2 0 1 0 0 0 1
dengan 1 2 3 1 1 2
0 1 4 0 1 0
0 0 , 1 0 0 . 1
10 0 0
0 0 5 0 0 1
10 25 50
20 40 . 61
dan
Unsur-unsur matriks , dan ditentukan dengan eliminasi Gauss (Golub & van Loan 1985). Matriks pada Contoh 2.9 bukan matriks simetrik. Jika matriks simetrik (dan taksingular), maka Teorema 2.6 menjamin bahwa matriks . Teorema 2.6 Jika adalah matriks taksingular dan simetrik yang memenuhi , maka . [Golub & van Loan 1985]
Contoh 2.10: Misalkan diberikan matriks simetrik
Contoh 2.9: Misalkan diberikan matriks
10 20 30 1 2 3
(bukti di Lampiran 3)
(bukti di Lampiran 2)
10 20 30
Karena determinan submatriks utama yang pertama dari matriks adalah |10| 10 0; det 10 10 50 0; dan det 20 25 10 10 20 det 50 0, maka 20 25 40 30 50 61 semua submatriks utama yang pertama dari matriks merupakan matriks taksingular. Jadi matriks dapat difaktorisasi ke dalam bentuk perkalian sebagai berikut:
10 20 20 45 30 80
30 80 . 171
5 Karena det 50 0, maka dapat difaktorisasi ke dalam bentuk perkalian sebagai berikut:
Teorema 2.7 (Determinan Matriks yang Dipartisi) Misalkan adalah matriks segi yang dipartisi menjadi
10 20 30 1 2 3
20 30 45 80 80 171 0 0 10 1 0 0 4 1 0 .
0 0 5 0 0 1
1 2 3 0 1 4 0 0 1
dan
Operasi-
Berikut ini akan dijelaskan tentang partisi suatu matriks dan invers dari matriks yang dipartisi. Definisi 2.13 (Partisi Matriks) Matriks dapat dipartisi menjadi matriksmatriks yang lebih kecil dengan cara menggambar garis-garis horizontal antara baris-baris dan garis-garis vertikal antara kolom-kolom. Matriks-matriks yang lebih kecil seringkali disebut blok. [Leon 2001]
2 1 2 1
4 1 1 1
1 3 1 4
2 4 3 2
Jika garis-garis digambarkan antara baris kedua dan baris ketiga, serta antara kolom ketiga dan keempat, maka akan terbagi , , , menjadi empat blok, yaitu dan .
1 2 4 2 dengan
2 1 2 1 1 2 1 3 4 2
dan
4 1 1 1 2 4 , 1 1
2 , 4 2 1 1 4
1 , 1 3 2
matriks berukuran berukuran . Jika maka det
det
dan matriks matriks taksingular, det
. [Zhang 1999]
(bukti lihat Lampiran 4)
2.3 Partisi Matriks Operasinya
Contoh 2.11: Misalkan matriks 1 2 4 2
dengan
1 3 1 4
2 4 3 2
Teorema 2.8 Dipartisi)
(Invers
Misalkan
Matriks
yang
merupakan
matriks yang dipartisi dan mempunyai invers yang juga merupakan matriks matriks yang dipartisi dengan bentuk dengan , , dan adalah matriks segi. Jika adalah submatriks utama dari matriks , maka diperoleh: , , , . [Zhang 1999] (bukti di Lampiran 5) Teorema 2.9 dan Misalkan adalah matriks taksingular, serta dan berturut-turut adalah matriks berukuran dan . Jika matriks taksingular, maka
dengan adalah himpunan matriks bernilai real dan berukuran . [Zhang 1999] (bukti di Lampiran 6) 2.4 Matriks Definit Positif dan Semidefinit Positif Berikut ini akan diberikan pengertian tentang matriks definit positif dan semidefinit positif serta beberapa sifatnya. Terlebih dahulu akan dibahas pengertian bentuk kuadrat.
6 Definisi 2.14 (Bentuk Kuadrat) Suatu persamaan kuadrat dengan dua variabel dan adalah suatu persamaan berbentuk: 2
0. (1)
Persamaan (1) dapat ditulis ulang dalam bentuk: 0. (2) Misalkan
Teorema 2.10 Misalkan matriks simetrik berukuran dan adalah submatriks utama yang pertama dari matriks dengan 1,2, … , , maka adalah matriks definit positif jika dan 0. hanya jika det [bukti lihat Horn & Johnson 1985] Contoh 2.13: Misalkan diberikan 4 2 2 10 2 2
dan maka bentuk 2 dinamakan bentuk kuadrat yang berhubungan dengan persamaan (1). [Leon 2001] Definisi 2.15 (Matriks Definit Positif dan Semidefinit Positif) Suatu matriks simetrik berukuran disebut matriks definit positif, jika bentuk kuadrat 0 untuk semua taknol dalam . Jika bentuk kuadrat 0, maka disebut matriks semidefinit positif.
matriks simetrik 2 2 5
dan submatriks utama yang pertama dari matriks seperti pada Contoh 2.8. Karena determinan submatriks utama yang pertama dari matriks adalah: |4| 4 0; i) det 4 2 ii) det 36 0; dan 2 10 4 2 2 108 0 iii) det 2 10 2 2 2 5 maka sesuai dengan Teorema 2.10, matriks adalah matriks definit positif.
[Leon 2001]
Matriks-matriks definit positif mempunyai beberapa sifat, di antaranya:
2 1 merupakan 1 2 matriks definit positif karena bentuk kuadrat 2 1 1 2 2 2 2
Teorema 2.11 1. Jika adalah matriks definit positif, maka det 0. 2. Jika adalah matriks definit positif, maka matriks taksingular. [Leon 2001]
Contoh 2.12: Matriks
0 0 . 1 1 Matriks adalah matriks 1 1 semidefinit positif karena bentuk kuadrat 1 1 1 1 2
untuk
0
0. 1 3 Matriks bukan matriks 3 1 definit atau semidefinit positif karena bentuk 1 3 kuadrat 3 1 6 4 dapat bernilai positif atau negatif.
Bukti: 1. Jika
adalah matriks definit positif maka
sesuai dengan Teorema 2.10, det dengan maka det 2. Karena det
0
1,2, … , . Karena det
, jadi det
0.
0, maka terbukti matriks
definit positif adalah matriks taksingular. ■ Teorema 2.12 (Invers Matriks Definit Positif) Jika adalah matriks definit positif, maka matriks definit positif. [Horn & Johnson 1985]
7 Bukti: Perhatikan persamaan . Karena matriks definit positif, maka taksingular. Jadi terdapat yang merupakan solusi persamaan tersebut. Maka bentuk kuadrat . Karena adalah matriks definit positif, maka 0 untuk . Jadi 0, untuk semua di semua di . juga Untuk membuktikan bahwa matriks simetrik, maka akan ditunjukkan . Dari Teorema 2.4, dan karena adalah matriks definit positif, maka adalah matriks simetrik. Sehingga diperoleh . Jadi terbukti bahwa matriks simetrik. Oleh karena itu, terbukti bahwa adalah matriks definit positif. ■ Teorema 2.13 Jika matriks merupakan matriks definit positif berukuran dan matriks adalah sembarang matriks berukuran , maka adalah matriks semidefinit matriks positif. [Horn & Johnson 1985] Bukti: Karena matriks definit positif, maka 0 untuk semua di . Misalkan matriks sembarang. Bentuk adalah kuadrat matriks 0 untuk semua di . Karena dan sembarang maka terdapat kemungkinan . Oleh karena itu, bentuk kuadrat 0 untuk semua di . Untuk membuktikan bahwa juga matriks simetrik, maka akan ditunjukkan . Dari Teorema 2.1 diperoleh , dan karena adalah matriks definit positif, maka adalah matriks simetrik. Sehingga diperoleh dan terbukti matriks merupakan matriks simetrik. Jadi sesuai dengan Definisi 2.15, adalah matriks semidefinit positif. ■ Teorema 2.14 Semua submatriks utama dari matriks definit positif adalah matriks definit positif. [Horn & Johnson 1985]
Bukti: Misalkan adalah submatriks utama dari matriks definit positif (Definisi 2.11) dan misalkan adalah vektor dengan entri taknol yang berubah posisi menyesuaikan pada dan mempunyai entri nol selainnya. Didefinisikan sebagai vektor yang diperoleh dari dengan menghilangkan entri nol yang dimiliki oleh . Untuk membuktikan submatriks utama dari matriks definit positif juga merupakan matriks definit positif, sesuai dengan Definisi 2.15 akan diperlihatkan bahwa 0 untuk semua taknol dalam . Menurut definisi , , dan diperoleh 0 untuk taknol dalam . Jadi terbukti bahwa submatriks utama dari matriks definit positif juga merupakan matriks definit positif. ■ Contoh 2.14: Misalkan
diberikan matriks definit 4 2 2 positif 2 10 2 dan submatriks 2 2 5 utama matriks pada Contoh 2.7, maka akan diperlihatkan bahwa semua submatriks utama juga merupakan matriks definit positif. i) Submatriks utama berukuran 1 1
0 0
4 , 1
1
maka 4
dan
1 1
,
1 0
4 0.
dengan
Terbukti 1 adalah matriks definit positif. Dengan cara yang sama dapat ditunjukkan bahwa 2 dan 3 juga matriks definit positif (Lampiran 7). ii) Submatriks utama berukuran 2 1,2
4 2 , 2 10
1,2
,
maka
1,2
1,2
2 0
1,2
dan
8
4 2 dengan
4 2 2 10 4 10 9
0
0 dan
0.
iii) Submatriks utama berukuran 3 3 4 2 2 Karena 1,2,3 2 10 2 , 2 2 5 dan diketahui adalah matriks definit
Terbukti 1,2 adalah matriks definit positif. Dengan cara yang sama dapat ditunjukkan bahwa 1,3 dan 2,3 juga matriks definit positif (Lampiran 7).
positif, maka
1,2,3
juga merupakan
matriks definit positif.
III PEMBAHASAN Pada bab ini akan dijelaskan mengenai matriks kuasidefinit dan beberapa sifatnya antara lain: matriks kuasidefinit merupakan matriks taksingular; invers dari matriks kuasidefinit merupakan matriks kuasidefinit; dan matriks kuasidefinit merupakan matriks strongly factorizable; yang merupakan inti dari tulisan ini.
1 3 2 5 3 1 1 2 2 1 2 1 5 2 1 2 bukan merupakan matriks kuasidefinit karena 1 3 matriks bukan matriks definit 3 1 positif (Contoh 2.12). 3.2 Sifat-sifat Matriks Kuasidefinit
3.1 Matriks Kuasidefinit Definisi 3.1 Suatu matriks simetrik dikatakan kuasidefinit jika mempunyai bentuk: (3) dan dengan matriks definit positif dengan
adalah ,
0.
[Vanderbei 1995] Contoh 3.1: Misalkan diberikan matriks 2 1 2 1 2 2 2 2 4 4 5 2 2 7 2
4 5 2 10 2
2 7 2 . 2 5
merupakan matriks kuasidefinit dengan 2 1 matriks matriks definit 1 2 positif (Contoh 2.12) dan 4 2 2 2 10 2 juga matriks definit 2 2 5 positif (Contoh 2.13). Sedangkan matriks
Berikut ini akan dijelaskan sifat-sifat dari matriks kuasidefinit. Teorema 3.1 Matriks
kuasidefinit
merupakan matriks taksingular. [Vanderbei 1995] Bukti: Menurut Teorema 2.3, untuk membuktikan bahwa merupakan matriks taksingular adalah dengan menunjukkan bahwa det 0. Karena adalah matriks definit positif (oleh karena itu taksingular), maka – matriks taksingular (Teorema 2.2). Sesuai dengan Teorema 2.7 didapat det
det
det
. (4)
Karena – matriks taksingular, maka sesuai dengan Teorema 2.3, det 0. Begitu pula karena matriks merupakan matriks definit positif (bukti lihat Lampiran 8), maka det 0 (Teorema 2.11).
