MATRIKS KUASIDEFINIT
SUGENG MULYADI
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2009
ABSTRAK SUGENG MULYADI. Matriks Kuasidefinit. Dibimbing oleh FARIDA HANUM dan SISWANDI. Matriks kuasidefinit adalah matriks simetrik yang dipartisi menjadi empat blok dan memuat matriks definit positif. Matriks ini, mempunyai sifat-sifat yang dapat diterapkan untuk menyelesaikan permasalahan-permasalahan matematika, khususnya pada bidang riset operasi. Sifat-sifat yang dibuktikan adalah: pertama, matriks kuasidefinit merupakan matriks taksingular; kedua, invers dari matriks kuasidefinit merupakan matriks kuasidefinit; dan ketiga, matriks kuasidefinit merupakan matriks strongly factorizable.
i
ABSTRACT SUGENG MULYADI. Quasidefinite Matrices. Supervised by FARIDA HANUM and SISWANDI. Quasidefinite matrix is a symmetric matrix partitioned into four blocks, which contain positive definite matrices. The matrix has properties which are applicable to solve mathematical problems, especially in operations research. There are three proven properties, i.e. quasidefinite matrix is a nonsingular matrix, the inverse of quasidefinite matrix is also a quasidefinite matrix, and quasidefinite matrix is a strongly factorizable matrix.
ii
MATRIKS KUASIDEFINIT
SUGENG MULYADI G5410130
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2009
iii
Judul : Matriks Kuasidefinit Nama : Sugeng Mulyadi Nrp : G54101030
Menyetujui,
Pembimbing I,
Pembimbing II,
Dra. Farida Hanum, M.Si. NIP. 19651019 199103 2 002
Drs. Siswandi, M.Si. NIP. 19640629 199103 1 001
Mengetahui, Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Dr.Drh. Hasim, DEA NIP. 19610328 198601 1 002
Tanggal Lulus : ………………………………
iv
RIWAYAT HIDUP Penulis dilahirkan di Bekasi pada tanggal 6 Juli 1984 dari pasangan Mujiono dan Pariyah. Penulis merupakan putra pertama dari tiga bersaudara. Pada tahun 2001, penulis lulus dari SMU Negeri I Cibinong dan pada tahun yang sama diterima di Institut Pertanian Bogor (IPB) melalui jalur Undangan Seleksi Masuk IPB (USMI-IPB). Penulis terdaftar sebagai mahasiswa Departemen Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor. Selama mengikuti perkuliahan, penulis pernah menjadi pengurus Gugus Mahasiswa Matematika. Selain itu, penulis pernah menjadi Ketua Masa Perkenalan Jurusan (MPJ) Departemen Matematika tahun 2003.
v
PRAKATA Alhamdulillahirobbil a’lamin, puji dan syukur penulis panjatkan ke hadirat Allah SWT atas segala nikmat, rahmat dan hidayah-Nya penulis dapat menyelesaikan skripsi ini. Shalawat serta salam semoga tercurah untuk nabi akhir zaman, yaitu Nabi Muhammad SAW, keluarga, sahabat dan umatnya hingga akhir zaman. Penulis menyadari bahwa terselesaikannya skripsi ini tidak terlepas dari doa, dukungan, bimbingan, arahan dan bantuan dari berbagai pihak baik langsung maupun tidak langsung. Oleh karena itu, penulis ingin menyampaikan rasa hormat dan ucapan terima kasih kepada kedua orang tua, Bapak, Ibu yang selalu mengawasi anaknya dari atas sana, Mama dan Adik-adik tersayang (Ayit dan Ie-ie) atas doa yang tidak pernah putus, lautan kasih sayang yang tidak pernah kering, perhatian dan dukungan baik materiil maupun spiritual. Kepada Ibu Dra. Farida Hanum, M.Si. selaku Dosen Pembimbing I penulis mengucapkan terima kasih atas doa, kesabaran, saran dan dukungan yang diberikan. Kepada Bapak Drs. Siswandi, M.Si. selaku Dosen Pembimbing II atas saran, kritik, motivasi dan bimbingan kepada penulis. Serta Ibu Dra. Nur Aliatiningtyas, MS. selaku Penguji atas saran, kritik dan motivasinya. Penulis juga mengucapkan terima kasih kepada Ibu Susi, Ibu Ade, Mas Yono, Mas Bono, Mas Deni, Mas Heri dan semua staf Departemen Matematika. Teman-teman Matematika angkatan 38: Hasif, Helmi, Firman, Ratna, Gresi, Linda, Yana, Isdad, Devi, Evi, Atin, Jati, Meryaldi dkk. Adik-adik kelas Matematika: Yusuf, Amin, Lela, Fitri, Rangga, Idris dkk. atas dukungan, motivasi, saran dan kritik kepada penulis. Terima kasih juga penulis ucapkan kepada Lina Muryani dan keluarga Citeureup atas kesabaran, semangat, saran dan bantuan yang diberikan selama ini. Dan semua pihak yang tidak dapat penulis sebutkan satu per satu. Penulis menyadari bahwa skripsi ini masih jauh dari sempurna. Oleh karena itu, dengan segala kerendahan hati, penulis menerima segala bentuk kritik dan saran yang membangun dari pembaca untuk perbaikan di masa yang akan datang.
Bogor, Agustus 2009
Sugeng Mulyadi
vi
DAFTAR ISI
Halaman Daftar Lampiran .............................................................................................................................. viii I
PENDAHULUAN 1.1 Latar Belakang ..................................................................................................................... 1 1.2 Tujuan .................................................................................................................................. 1
II LANDASAN TEORI 2.1 Matriks dan Determinan ...................................................................................................... 2.2 Submatriks ........................................................................................................................... 2.3 Partisi Matriks dan Operasi-Operasinya ............................................................................. 2.4 Matriks Definit dan Semidefinit Positif ..............................................................................
1 3 5 5
III PEMBAHASAN 3.1 Matriks Kuasidefinit ............................................................................................................ 8 3.2 Sifat-sifat Matriks Kuasidefinit ........................................................................................... 8 3.3 Faktorisasi Matriks Kuasidefinit ......................................................................................... 10 IV SIMPULAN DAN SARAN 4.1 Simpulan .............................................................................................................................. 13 4.2 Saran .................................................................................................................................... 13 DAFTAR PUSTAKA ..................................................................................................................... 14 LAMPIRAN .................................................................................................................................... 15
vii
DAFTAR LAMPIRAN Halaman 1 2 3 4 5 6 7 8 9 10
Pembuktian Teorema 2.3 ........................................................................................................... Pembuktian Teorema 2.5 ........................................................................................................... Pembuktian Teorema 2.6 ........................................................................................................... Pembuktian Teorema 2.7 ........................................................................................................... Pembuktian Teorema 2.8 ........................................................................................................... Pembuktian Teorema 2.9 ........................................................................................................... Tambahan Contoh 2.14 ............................................................................................................ Tambahan Bukti Teorema 3.1 ................................................................................................... Tambahan Bukti Teorema 3.2 ................................................................................................... Tambahan Bukti Teorema 3.3 ...................................................................................................
16 18 20 20 23 24 25 26 27 28
viii
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).
9 Jadi det 0. terbukti bahwa matriks taksingular. Teorema 3.2 Invers dari
Dengan demikian, merupakan matriks ■
matriks
kuasidefinit ,
adalah dengan:
(6) (7) ,
(8)
dari Teorema 2.9, Persamaan (6) akan menjadi: . (9) Dan
merupakan matriks kuasidefinit.
dengan Teorema 2.8 bahwa , (10)
dengan: (11) (12) ,
. matriks semidefinit berukuran , maka 0 dan karena matriks definit positif berukuran , maka 0, sehingga bentuk kuadrat 0 untuk sembarang vektor taknol di . Jadi terbukti bahwa matriks merupakan matriks definit positif. d. Untuk membuktikan matriks simetrik akan ditunjukkan: . Dari Teorema 2.1, didapat . Karena matriks definit positif, maka . matriks simetrik, jadi Sedangkan sesuai dengan Teorema 2.1, matriks Karena positif
[Vanderbei 1995] Bukti: Sesuai
ii) Akan dibuktikan merupakan matriks definit positif. a. Karena matriks definit positif matriks berukuran , maka definit positif berukuran (Teorema 2.12). matriks definit positif b. Karena berukuran dan sembarang matriks berukuran , maka matriks semidefinit positif berukuran (Teorema 2.13). c. Misalkan adalah vektor taknol sembarang di . Maka
(13)
dari Teorema 2.9, Persamaan (11) akan menjadi: . (14) (bukti perhitungan di atas pada Lampiran 9) Untuk
membuktikan
bahwa
merupakan matriks kuasidefinit, berdasarkan Definisi 3.1 akan ditunjukkan bahwa dan adalah matriks definit positif sebagai berikut: i) Matriks merupakan invers dari matriks (Sifat 3.1). Karena matriks adalah matriks definit positif dan sesuai dengan Teorema 2.12, maka matriks adalah matriks definit positif.
. Karena definit positif, maka simetrik, jadi Jadi Sehingga terbukti bahwa merupakan simetrik. Jadi terbukti bahwa adalah matriks positif. e. Karena matriks adalah invers dari menurut Teorema 2.12, maka adalah definit positif.
matriks matriks . . matriks matriks matriks definit
maka matriks matriks
10 Dengan demikian terbukti bahwa matriks merupakan
Definisi 3.2 Matriks simetrik taksingular dikatakan dapat difaktorisasi (factorizable) jika terdapat matriks diagonal dan matriks segitiga bawah dengan elemen-elemen 1 pada diagonal utamanya (unit lower triangular . matrix) yang memenuhi Pasangan matriks , disebut faktorisasi dari matriks . [Vanderbei 1995]
matriks
kuasidefinit.
■
3.3 Faktorisasi Matriks Kuasidefinit Setelah dibahas mengenai definisi dan beberapa sifat matriks kuasidefinit, berikutnya akan dibahas mengenai sifat matriks kuasidefinit yang berhubungan dengan faktorisasi. Terlebih dahulu akan diberikan definisi faktorisasi. Contoh 3.2: Misalkan matriks kuasidefinit 2 1 2 4 2
1 2 2 5 7
2 2 4 2 2
4 5 2 10 2
2 7 2 . 2 5
Dapat difaktorisasi ke dalam hasil kali 2 1 2 4 2 1 2 2 5 7 2 2 4 2 2 4 5 2 10 2 2 7 2 2 5 2 1 0 0 0 0 0 1 0 0 0 0 1 2 1 0 0 0 2 2 0 1 0 1 1 4 0
sebagai berikut:
0 0 0
, maka sesuai dengan Definisi 3.2 matriks
dikatakan dapat difaktorisasi (factorizable).
0
Definisi 3.3 Matriks simetrik taksingular dikatakan strongly factorizable jika terdapat faktorisasi untuk setiap matriks permutasi dengan adalah matriks diagonal dan adalah matriks segitiga bawah dengan elemen-elemen 1 pada diagonal utamanya (unit lower triangular matrix). [Vanderbei 1995] Contoh 3.3: Misalkan matriks simetrik
4 4 4 2 8 1
8 1 , 2
0 0 12 0 0
0 0 0 24 0
0 0 0 0
1 0 0
1 0
1 2 1
2 2 0
0
0
0
1
0
0
0
0
1 4
1
karena det 108 0, maka matriks taksingular. Untuk menunjukkan bahwa matriks strongly factorizable, maka faktorisasi harus berlaku untuk semua matriks permutasi . Karena matriks berukuran 3 3, maka terdapat 3! 6 matriks permutasi berukuran 3 3. Akan ditunjukkan untuk setiap matriks permutasi terdapat faktorisasi , dengan adalah matriks diagonal dan adalah matriks segitiga bawah dengan elemen-elemen 1 pada diagonal utamanya, sebagai berikut:
11 1 0 0 0 1 0 0 0 1 1 0 0 4 4 8 0 1 0 4 2 1 0 0 1 8 1 2 Dapat difaktorisasi ke dalam hasil kali 1 0 0 4 4 4 8 1 1 0 0 4 2 1 2 1 0 8 1 2
0 0 4 4 1 0 4 2 0 1 8 1 sebagai berikut: 0 0 1 1 2 6 0 0 1 0 0 0 1
1 0 0 0 0 1 0 1 0 1 0 0 4 4 8 0 0 1 4 2 1 0 1 0 8 1 2 Dapat difaktorisasi ke dalam hasil kali 4 1 0 0 4 8 4 0 2 1 0 8 2 1 1 0 1 4 1 2
1 0 0 4 8 4 0 0 1 8 2 1 . 0 1 0 4 1 2 sebagai berikut: 0 0 1 2 1 18 0 0 1 0 0 0 1
1. Matriks permutasi
1 0 0
8 1 . 2
.
2. Matriks permutasi
.
0 1 0 1 0 0 0 0 1 0 1 0 4 4 8 0 1 0 2 4 1 1 0 0 4 2 1 1 0 0 4 4 8 . 0 0 1 8 1 2 0 0 1 1 8 2 Dapat difaktorisasi ke dalam hasil kali sebagai berikut:
3. Matriks permutasi
2 4 1
4 1 4 8 8 2
1 2
0 0 1 0 1
2 0 0
0 12 0
0 0
1 2 0 1 0 0
. 1
0 1 0 0 0 1 1 0 0 0 1 0 4 4 8 0 1 0 2 1 0 0 1 4 2 1 0 0 1 1 2 1 0 0 8 1 2 1 0 0 4 8 sebagai berikut: Dapat difaktorisasi ke dalam hasil kali 2 0 0 1 0 0 2 1 4 2 1 0 0 1 0 1 2 8 0 1 4 4 8 4 2 4 1 0 0 36 0 0 1
4. Matriks permutasi
4 8 . 4
.
0 0 1 1 0 0 0 1 0 0 0 1 4 4 8 0 0 1 2 8 1 1 0 0 4 2 1 1 0 0 8 4 4 . 0 1 0 8 1 2 0 1 0 1 4 2 sebagai berikut: Dapat difaktorisasi ke dalam hasil kali
5. Matriks permutasi
12 2 8 1
8 1 4 4 4 2
1 4
0 1 0
0 0 1
2 0 0
0 0 36 0 0
1 4 0 1 0 0 0 1
0 0 1 0 1 0 1 0 0 0 0 1 4 4 8 0 0 1 2 1 0 1 0 4 2 1 0 1 0 1 2 1 0 0 8 1 2 1 0 0 8 4 sebagai berikut: Dapat difaktorisasi ke dalam hasil kali 2 0 0 1 0 0 2 1 8 4 1 1 0 0 0 1 2 4 0 1 0 8 4 4 4 0 1 0 0 36 0 0 1
.
6. Matriks permutasi
Karena untuk semua matriks permutasi , terbukti matriks , maka sesuai dengan Definisi 3.3, maka matriks strongly factorizable. Dari Contoh 3.3 di atas, untuk membuktikan suatu matriks simetrik taksingular strongly factorizable, dengan menggunakan Definisi 3.3 terlalu banyak faktorisasi yang harus diperiksa yaitu sebanyak !, sehingga diperlukan cara yang lebih praktis. Berikut ini akan dijelaskan sifat matriks kuasidefinit yang berhubungan dengan faktorisasi dan pembuktiannya menggunakan Teorema 2.5 dan Teorema 2.6. Teorema 3.3 Matriks kuasidefinit strongly factorizable.
merupakan matriks [Vanderbei 1995]
Bukti: Misalkan adalah submatriks utama yang pertama dari dan adalah matriks permutasi berukuran dengan 1 . Untuk membuktikan teorema di atas, akan merupakan ditunjukkan bahwa semua matriks taksingular. Submatriks utama yang pertama dari mempunyai persamaan ,
8 4 . 4
.
dengan adalah submatriks utama dari matriks kuasidefinit dan himpunan bagian dari 1, 2, … , . Submatriks utama mempunyai bentuk
, dengan
dan adalah submatriks utama dari matriks dan (Ilustrasi diberikan pada Lampiran 10). Karena dan adalah submatriks utama dari matriks dan , sesuai dengan Teorema 2.14, maka dan adalah matriks definit positif. Jadi
adalah
matriks kuasidefinit (Definisi 3.1). Oleh karena itu, sesuai dengan Teorema 3.1 terbukti bahwa adalah matriks taksingular. Karena dan semua matriks permutasi merupakan matriks taksingular maka taksingular. Sesuai dengan Teorema 2.5 dan Teorema 2.6 maka matriks . dapat difaktorisasi ke dalam hasil kali Jadi sesuai dengan Definisi 3.3 dapat dinyatakan bahwa matriks kuasidefinit merupakan matriks strongly factorizable. ■ Selanjutnya, dari Contoh 3.2 dan Contoh 3.3 dapat dibuat suatu teorema tentang hubungan antara matriks yang dapat difaktorisasi (factorizable) dengan matriks strongly factorizable.
sebagai
difaktorisasi ke dalam hasil kali
Teorema 3.4 Jika suatu matriks strongly factorizable, maka matriks tersebut dapat difaktorisasi (factorizable).
berikut: 2 1
1
1 0
0 1
2 0
0
1 0
1
. Bukti: Misalkan matriks (berukuran ) strongly factorizable. Sesuai dengan Definisi 3.3, terdapat faktorisasi untuk setiap matriks permutasi . Jika dipilih , maka terdapat matriks permutasi faktorisasi
Dari Definisi 3.2, terbukti matriks factorizable. Namun jika dipilih matriks permutasi 0 1 , maka diperoleh matriks 1 0 0 1 2 1 0 1 0 1 . 1 2 1 0 1 0 1 0 Matriks tidak dapat difaktorisasi ke , karena bila dilihat dalam hasil kali pada matriks bentuk umum perkalian berukuran 2 2 sebagai berikut:
. Sesuai dengan Definisi 3.2, maka matriks dapat difaktorisasi (factorizable). ■
0
1 1
Dari Contoh 3.3 bagian 1, terlihat apabila suatu matriks strongly factorizable, maka matriks factorizable (pada saat matriks permutasi ). Berikut ini diberikan contoh suatu matriks simetrik taksingular factorizable tapi tidak strongly factorizable.
2 1
det
Karena pada matriks elemen pada baris dan kolom pertama bernilai nol (0), 0, oleh maka akan mengakibatkan nilai 0 0 karena itu untuk semua 0 matriks segitiga bawah dengan elemen 1 pada diagonal utamanya. Jadi matriks tidak dapat difaktorisasi ke dalam hasil kali . Oleh karena itu, matriks bukan matriks strongly factorizable.
1
0,
maka
1 , karena 0 matriks
taksingular. Oleh karena itu, matriks
1 .
Contoh 3.4: Misalkan matriks
1
0
dapat
IV SIMPULAN DAN SARAN 4.1 Simpulan Berdasarkan pembahasan yang telah diuraikan di atas, diperoleh beberapa simpulan sebagai berikut: i) Matriks kuasidefinit merupakan matriks taksingular. ii) Invers dari matriks kuasidefinit merupakan matriks kuasidefinit. iii) Matriks kuasidefinit merupakan matriks strongly factorizable.
4.2 Saran Bagi yang beminat mengembangkan tulisan ini, dapat menggunakan hasil pada tulisan ini untuk diaplikasikan pada metode titik interior (interior-point method) untuk pemrograman linear dan kuadratik.
DAFTAR PUSTAKA Anton H. 2000. Dasar-dasar Aljabar Linear. Ed. Ke-7. Hari Suminto, alih bahasa. Batam: Interaksara. Terjemahan dari: Elementary Linear Algebra.
Leon SJ. 2001. Aljabar Linear dan Aplikasinya. Ed. ke-5. Bondan A, alih bahasa. Jakarta: Erlangga. Terjemahan dari: Linear Algebra with Applications.
Golub GH, van Loan CF. 1985. Matrix Computations. Maryland: The Johns Hopkins University Press.
Vanderbei RJ. 1995. Symmetric quasi-definite matrices. SIAM J. Optimization 5(1): 100113.
Harville DA. 2008. Matrix Algebra from a Statistician's Perspective, 2nd printing. http://www.springer.com/978-0-3877835 6-7. 28-03-2009.
Zhang F. 1999. Matrix Theory: Basic Results and Techniques. New York: Springer-Verlag.
Horn RA, Johnson CR. 1985. Matrix Analysis. New York: Cambridge University Press.
LAMPIRAN
16
Lampiran 1 Pembuktian Teorema 2.3 Sebelum membuktikan Teorema 2.3, terlebih dahulu diberikan beberapa definisi yang berhubungan dengan pembuktian Teorema 2.3. Definisi 1 (Matriks Eselon Baris) Suatu matriks dikatakan memiliki bentuk eselon baris jika: i) Entri bukan nol pertama setiap baris adalah 1. ii) Jika baris k tidak seluruhnya mengandung nol, maka banyaknya entri nol di bagian depan pada baris k + 1 lebih besar dari banyaknya entri nol di bagian depan pada baris k. iii) Jika terdapat baris-baris yang entrinya semua adalah nol, maka baris-baris ini berada di bawah baris-baris yang memiliki entri-entri bukan nol. [Leon 2001] Contoh 1: 1. Matriks-matriks berikut memiliki bentuk eselon baris, 1 4 2 1 2 3 1 3 1 0 0 1 3 , 0 0 1 , 0 0 1 3 . 0 0 0 0 0 0 1 0 0 0 2. Matriks-matriks berikut tidak memiliki bentuk eselon baris, 2 4 6 0 1 0 0 0 . , 0 3 5 , 1 0 0 1 0 0 0 4 Matriks pertama tidak memenuhi syarat (i), matriks kedua gagal memenuhi syarat (iii) dan matriks ketiga gagal memenuhi syarat (ii). Definisi 2 (Matriks Elementer) Suatu matriks yang diperoleh dari matriks satuan I dengan melakukan satu operasi baris elementer disebut matriks elementer. Terdapat tiga jenis matriks elementer yang berkorespondensi dengan ketiga jenis operasi baris elementer. Jenis I. Matriks elementer jenis I adalah matriks yang diperoleh dengan mempertukarkan dua baris dari I. Contoh 2:
0 1 0 1 0 0 adalah matriks elementer jenis I, karena diperoleh dengan 0 0 1 mempertukarkan kedua baris yang pertama dari I. Misalkan matriks 3 3, 0 1 0 1 0 0 0 0 1 0 1 0 . 1 0 0 0 0 1 akan mempertukarkan baris pertama dan kedua dari . Mengalikan di sebelah kiri dengan Mengalikan di sebelah kanan dengan adalah ekuivalen dengan operasi kolom elementer yang mempertukarkan kolom pertama dan kedua dari . Misalkan
17 Jenis II. Matriks elementer jenis II adalah matriks yang diperoleh dengan mengalikan satu baris dari I dengan konstanta taknol. Contoh 3: Misalkan
1 0 0
0 1 0
0 0 adalah matriks elementer jenis II, dan misalkan 3 1 0 0 0 1 0 3 3 3 0 0 3 3 1 0 0 3 . 0 1 0 3 0 0 3
matriks 3
3 maka
akan melakukan operasi baris elementer dengan mengalikan baris Perkalian di sebelah kiri oleh ketiga dari oleh 3. Sedangkan perkalian di sebelah kanan oleh akan melakukan operasi kolom elementer dengan mengalikan kolom ketiga dari oleh 3. Jenis III. Matriks elementer jenis III adalah matriks yang diperoleh dari I dengan menjumlahkan kelipatan dari satu baris pada baris yang lain. Contoh 4: Misalkan
1 0 0
0 1 0
3 0 adalah satu matriks elementer jenis III. Jika 1 3 3 1 0 3 0 1 0 0 0 1 3 1 0 3 3 0 1 0 3 0 0 1
matriks 3
3 maka
3
.
akan menjumlahkan 3 kali baris ketiga pada baris pertama dari , Perkalian di sebelah kiri oleh sedangkan perkalian di sebelah kanan oleh akan menjumlahkan 3 kali kolom pertama pada kolom ketiga dari . [Leon 2001] Teorema 1 Jika dan adalah matriks-matriks berukuran
, maka det
det
det
.
[bukti lihat Leon 2001] Bukti Teorema 2.3 Matriks dapat direduksi menjadi bentuk eselon baris dengan operasi-operasi baris yang berhingga banyaknya. Jadi . . . dengan berbentuk eselon baris dan semua adalah ,,matriks elementer. det det . . . det det . . . . det det Karena determinan-determinan dari semuanya taknol, maka det 0 jika dan hanya jika det 0. Jika matriks singular, maka matriks memiliki baris dengan seluruh elemen bernilai nol dan dengan demikian det 0. Jika matriks taksingular, maka matriks segitiga yang elemenelemen diagonalnya bernilai 1 sehingga det 1 0. [Leon 2001]
18
Lampiran 2 Pembuktian Teorema 2.5 Sebelum membuktikan Teorema 2.5, diberikan teorema yang berhubungan dengan pembuktian teorema tersebut. Teorema 2 Jika adalah matriks berukuran dengan submatriks utama yang pertama semuanya taksingular, maka matriks dapat difaktorisasi ke dalam hasil kali dengan adalah matriks segitiga bawah dengan elemen-elemen 1 pada diagonalnya dan adalah matriks segitiga atas. Bukti: Misalkan adalah matriks berukuran dengan submatriks utama yang pertama semuanya taksingular, maka dapat direduksi menjadi matriks segitiga atas dengan hanya menggunakan operasi baris III (Definisi 2 di Lampiran 1); dengan elemen-elemen diagonal tidak akan pernah menjadi nol pada proses eliminasi, sehingga reduksi dapat berlangsung sempurna tanpa mempertukarkan baris. Proses reduksi berlangsung sebagai berikut: . . . . Jika matriks dapat direduksi menjadi matriks segitiga atas tanpa melakukan pertukaran baris, maka dapat difaktorisasi ke dalam hasil kali sebagai berikut: . . . . . . dengan
. . .
dan
adalah matriks segitiga atas. [Leon 2001]
Untuk memperjelas pembuktian teorema di atas, diberikan contoh berikut. Contoh 5: Misalkan matriks matriks adalah: • det
4 2 2
2 10 2
2 2 . Karena determinan submatriks utama yang pertama dari 5
|4| 4 0; 4 2 36 0; dan • det 2 10 4 2 2 • det 108 0. 2 10 2 2 2 5 Maka semua submatriks utama yang pertama dari matriks merupakan matriks taksingular, jadi matriks dapat direduksi menjadi matriks segitiga atas dengan cara matriks dikalikan (dari kiri) dengan serangkaian matriks elementer jenis III sebagai berikut: 1 0 0 1 0 , sehingga diperoleh: • 0 0 1 1 0 0 4 2 2 4 2 2 1 0 2 10 2 0 9 3 ; 2 2 5 2 2 5 0 0 1
19 1 0
•
0 0 1 0 , sehingga diperoleh: 0 1 1 0
1 0 0
•
0 0 1 0 0 1
4 2 0 9 2 2
dinyatakan sebagai: 1 0 0 0 1 0 0 1 1
4 0 0
2 9 3
2 3 ; 4
0 0 1 0 , sehingga diperoleh: 1 1 0 0
Matriks
2 3 5
0 0 1 0 1
1 0
4 0 0
2 9 3
0 0 1 0 0 1
1 0
2 3 4
4 0 0
2 9 0
2 3 . 3
0 0 1 0 0 1
1 0 0 1 0 . 1
Bila diujikan kembali, diperoleh: 1 0 0 1 1 0 2 1 1 1 2 3 Jadi terbukti bahwa matriks
0 0 1 0 1
4 0 0
2 9 0
2 3 3
4 2 2 10 2 2
dapat difaktorisasi ke dalam hasil kali
2 2 . 5
.
Bukti Teorema 2.5: Teorema 2 telah menunjukkan bahwa matriks dengan submatriks utama yang pertama semuanya taksingular, maka matriks dapat difaktorisasi ke dalam hasil kali dengan adalah matriks segitiga bawah dengan elemen-elemen 1 pada diagonalnya dan adalah matriks segitiga 0 0 0 0 atas. Definisikan matriks diagonal dengan untuk 1 . 0 0 yang merupakan Diketahui bahwa matriks taksingular, maka terdapat matriks matriks segitiga atas dengan elemen-elemen 1 pada diagonalnya. Karena . Jadi terbukti bahwa matriks dapat difaktorisasi ke dalam bentuk perkalian . [Golub & van Loan 1985]
20
Lampiran 3 Pembuktian Teorema 2.6 Bukti Teorema 2.6: Misalkan matriks simetrik, taksingular dan memenuhi faktorisasi dengan dan adalah matriks segitiga bawah dengan elemen-elemen 1 pada diagonalnya dan adalah matriks diagonal. Jika adalah matriks segitiga bawah dengan elemen-elemen 1 pada diagonalnya, maka juga merupakan matriks segitiga bawah dengan elemen-elemen 1 pada diagonalnya (seperti pada Contoh 5 di Lampiran 2). Oleh karena itu, bila matriks simetrik dikalikan dari kiri dan kanan oleh matriks akan dan akan diperoleh matriks yang merupakan matriks diagonal. Karena , maka merupakan matriks diagonal juga. Karena adalah matriks diagonal. Namun karena adalah matriks diagonal dan taksingular, maka matriks adalah matriks segitiga bawah dengan elemen-elemen 1 pada diagonalnya, maka . Hal ini membuktikan bahwa matriks . haruslah [Golub & van Loan 1985]
Lampiran 4 Pembuktian Teorema 2.7 Terlebih dahulu diberikan definisi dan teorema yang berhubungan dengan pembuktian Teorema 2.7. Definisi 3 (Perkalian Blok) Misalkan matriks berukuran dan matriks berukuran dan dapat dibedakan menjadi 4 kasus, yaitu:
. Perkalian blok matriks
Kasus 1 , dengan
matriks
dan
matriks
, maka
Kasus 2 , dengan
matriks
dan
,
dan
matriks
, maka
Kasus 3 dengan
Kasus 4 Misalkan
matriks , maka
dan
matriks
keduanya dipartisi sebagai berikut: dan
maka,
dan
,
matriks
dan
matriks
21
[Leon 2001] Contoh 6: Misalkan 1 1 2 2 3 3 maka 1 1 2 2 3 3 1.1 2.1 3.1
1.1 2.1 3.1
8 10 18
6 9 15
1 1 1 1 2 2 1.3 1.3 2.3
4 6 10
1.3 1.3 2.3
1 1 3 3
1 1 1 1 2 2 1 2 1 2
1.1 2.1 3.1
1 1 1 1
1.2 2.2 3.2
1 1 3 3
dan
1 1 1 2
1.1 1.1 2.1
1.2 1.2 2.2
1.1 2.1 3.1
1.1 2.1 3.1
1.1 1.1 2.1
1 2 1 2
1.1 1.1 2.1
1 1 1 1
1.1 2.1 3.1
1 1 1 2
1.1 2.1 3.1
1.1 1.1 2.1
1.2 1.2 2.2
5 7 12
Definisi 4 (Operasi Dasar pada Matriks Dipartisi) Operasi baris dasar atau operasi kolom dasar pada matriks yang dipartisi dibedakan menjadi tiga operasi, yaitu: I. Penukaran dua (blok) baris (kolom) II. Mengalikan (blok) baris (kolom) dari kiri (kanan) dengan suatu matriks taksingular yang berukuran tepat III. Mengalikan (blok) baris (kolom) dengan suatu matriks dari kiri (kanan), lalu menambahkan pada baris (kolom) yang lain. [Zhang 1999] Contoh 7: Misalkan
1 1 2 2 3 3
1 1 1 1 2 2
I. Jika dilakukan penukaran antara baris pertama dan kedua, maka matriks 2 2 3 3 1 1
1 1 2 2 1 1 2 1
II. Jika baris pertama dikalikan dengan matriks
1 dari kanan, maka matriks A 3
menjadi: 1 2 3
menjadi:
2 1 2 1 3 2
2 1 2
22 1
III. Jika baris kedua dikalikan dengan matriks pertama, maka matriks menjadi:
1 dari kiri, lalu ditambahkan pada baris
0 2 3
0 0 0 2 1 1 3 2 2
Teorema 3 Jika adalah matriks segitiga atas atau bawah yang berukuran sama dengan hasil kali elemen-elemen diagonal matriks .
, maka determinan dari
[bukti lihat Leon 2001] Definisi 5 (Pengaruh Operasi Baris pada Nilai Determinan ) Pengaruh-pengaruh dari operasi-operasi baris atau kolom pada nilai determinan suatu matriks adalah sebagai berikut: I. Pertukaran dua baris (atau kolom) dari suatu matriks akan mengubah tanda dari determinan. II. Mengalikan satu baris (atau kolom) dari suatu matriks dengan suatu skalar sama akibatnya dengan mengalikan nilai dari determinan dengan skala r tersebut. III. Menjumlahkan perkalian dari satu baris (atau kolom) pada baris lain (atau kolom lain) tidak akan mengubah nilai dari determinan. [Leon 2001] Bukti Teorema 2.7 Jika
sebagai invers dari
matriks taksingular maka terdapat matriks
melakukan operasi baris dasar jenis III (Definisi 4) pada matriks
. Dengan
, yaitu baris pertama
(dari kiri) lalu menambahkannya pada baris kedua sehingga
dikalikan dengan matriks diperoleh
.
0 Sesuai dengan Definisi 5, maka det det
det
, lalu dari Teorema 3 diketahui
det
dengan Teorema 1 (di Lampiran 1), terbukti bahwa det
det
det
.
23
Lampiran 5 Pembuktian Teorema 2.8 adalah
Akan dibuktikan invers dari matriks
dengan
, , , . Bukti Teorema 2.8: Dari setiap matriks yang mempunyai invers dapat dituliskan sebagai perkalian dari matriks elementer, sehingga dapat ditulis: | ~ | , | akan diperoleh melalui matriks yang berarti dengan menerapkan operasi baris pada | . Diberikan matriks perluasan berikut: 0 | 0 lalu dilakukan operasi baris dasar (Definisi 4 di Lampiran 4), 1. Baris pertama dikalikan dengan matriks
(dari kiri), sehingga diperoleh: 0 0
2. Baris pertama dikalikan dengan matriks diperoleh:
(dari kiri), lalu ditambahkan pada baris kedua 0
0 3. Baris kedua dapat dikalikan dengan
(dari kiri) untuk memperoleh: 0
0 4. Dengan mengalikan (dari kiri) baris kedua dengan matriks baris pertama diperoleh: 0 0 Jadi terbukti bahwa invers matriks yang dipartisi
, lalu menambahkannya pada
adalah
dengan
, , , . [Zhang 1999]
24
Lampiran 6 Pembuktian Teorema 2.9 Akan
dibuktikan dan berukuran dan
bahwa adalah matriks taksingular, serta .
dan
dengan berturut-turut adalah matriks
Bukti Teorema 2.9: Menurut Definisi 2.6, akan ditunjukkan bahwa . •
. •
. Jadi terbukti bahwa
.
25
Lampiran 7 Tambahan Contoh 2.14 2
Dengan cara yang sama pada Contoh 2.14 dapat ditunjukkan bahwa matriks definit positif sebagai berikut: •
2 maka
•
3
10
3
dan 3
4 2
1,3
5
2 , 5
0
0 dengan
0.
0 dengan
5 1,3
1,3
dan
2,3
dan
0. juga matriks definit positif
,
maka 1,3
1,3
4 2
1,3 2
dengan
•
2,3
0 dan 10 2
4
2 5
4
4
5
0
0. 0
2 , 5
dan
2,3
,
maka 2,3 dengan
2,3
2,3
0 dan
2 0.
juga
,
Begitu pula dapat ditunjukkan bahwa sebagai berikut: •
3
, 10
2
0 0
5 , 3
2
dan 0
2
2
3 maka
0
10 ,
dan
10 2
2 5 6
10 4
4 0
5
26
Lampiran 8 Tambahan Bukti Teorema 3.1 Akan dibuktikan
merupakan matriks definit positif.
Bukti: a. Karena matriks definit positif berukuran (Teorema 2.12)
, maka
matriks definit positif berukuran
b. Karena matriks definit positif berukuran dan , maka matriks semidefinit positif berukuran c. Misalkan adalah vektor taknol sembarang di . . Maka matriks semidefinit positif berukuran Karena karena matriks definit positif berukuran , maka 0 untuk sembarang vektor taknol di
sembarang matriks berukuran (Teorema 2.13)
, maka 0 dan 0, sehingga bentuk kuadrat .
d. Untuk membuktikan
matriks simetrik, akan ditunjukkan: . . Dari Teorema 2.1, didapat Karena matriks definit positif, maka matriks simetrik, jadi . Sedangkan sesuai . Karena matriks Teorema 2.1, matriks definit positif, maka matriks simetrik, jadi . Jadi . Terbukti bahwa matriks merupakan matriks simetrik.
Jadi terbukti bahwa matriks
merupakan matriks definit positif.
27
Lampiran 9 Tambahan Bukti Teorema 3.2 Akan dibuktikan invers matriks • • • •
dengan
adalah matriks , , ,
.
Bukti: Sesuai dengan Teorema 2.8, invers matriks yang dipartisi
,
adalah
dengan , , , . Jadi untuk matriks
akan diperoleh invers matriks
dengan
yaitu
• . Sesuai Teorema 2.9,
Dengan demikian diperoleh matriks
.
•
•
• . ,
Jika , , , Maka terbukti
.
28
Lampiran 10 Tambahan Bukti Teorema 3.3 Akan diperlihatkan untuk beberapa matriks permutasi bahwa submatriks utama yang pertama yaitu dengan adalah matriks permutasi berukuran dengan dari 1 dan adalah submatriks utama dari matriks kuasidefinit dengan himpunan bagian dari 1, 2, … , . Submatriks utama mempunyai bentuk , dengan
dan
adalah submatriks utama dari matriks
dan .
Dengan menggunakan matriks kuasidefinit pada Contoh 3.3, yaitu 2 1 2 4 2 1 2 2 5 7 2 2 4 2 2 4 5 2 10 2 2 7 2 2 5 dengan 4 2 2 2 1 dan 2 10 2 . 1 2 2 2 5 Misalkan diberikan beberapa matriks permutasi sebagai berikut:
1)
1 0 0 0 0
0 0 1 0 0
0 0 0 0 1
0 1 0 0 0
0 0 0 , maka 1 0
2 4 1 2 2
4 10 5 2 2
1 5 2 7 2
2 2 7 5 2
2 2 2 . 2 4
Submatriks utama yang pertama dari adalah: 2 4 1 0 , merupakan 1,4 , 1 dan 2 , dengan ; • 4 10 0 1 2 4 1 1 • 4 10 5 , merupakan 1,2,4 , 1,2 dan 2 , dengan 0 1 5 2 0 2 4 1 2 4 10 5 2 • , merupakan 1,2,4,5 , 1,2 dan 2,3 , 1 5 2 7 2 2 7 5 1 0 0 0 0 0 1 0 ; dan 0 1 0 0 0 0 0 1 2 4 1 2 2 4 10 5 2 2 1,2,3,4,5 , 1,2 dan • 1 5 2 7 2 , merupakan 2 2 7 5 2 2 2 2 2 4 dengan .
0 0 0 1 ; 1 0 dengan
1,2,3 ,
29 0 0 1 0 0 4 2 2 2 2 1 0 0 0 0 2 2 2 4 1 2) 0 0 0 0 1 , maka 2 2 5 2 7 . 0 0 0 1 0 2 4 2 10 5 0 1 0 0 0 2 1 7 5 2 Submatriks utama yang pertama dari adalah: 0 1 4 2 ; , merupakan 1,3 , 1 dan 1 , dengan • 1 0 2 2 4 2 2 0 • 2 2 2 , merupakan 1,3,5 , 1 dan 1.3 , dengan 1 2 2 5 0 4 2 2 2 2 2 2 4 • , merupakan 1,3,4,5 , 1 dan 1,2,3 , 2 2 5 2 2 4 2 10 0 1 0 0 1 0 0 0 ; dan 0 0 0 1 0 0 1 0 4 2 2 2 2 2 2 2 4 1 1,2,3,4,5 , 1,2 dan • 2 2 5 2 7 , merupakan 2 4 2 10 5 2 1 7 5 2 . dengan 0 0 0 0 1 0 1 0 0 0 3) 0 0 0 1 0 , maka 1 0 0 0 0 0 0 1 0 0 Submatriks utama yang pertama dari
5 7 2 2 2 adalah:
7 2 5 1 2
2 5 10 4 2
2 1 4 2 2
1 0 0
0 0 ; 1
dengan
1,2,3 ,
2 2 2 . 2 4
0 1 7 ; , merupakan 2,5 , 2 dan 2 , dengan 1 0 2 0 1 0 5 7 2 • 0 0 1 ; 7 2 5 , merupakan 2,4,5 , 2 dan 2.3 , dengan 1 0 0 2 5 10 5 7 2 2 7 2 5 1 , merupakan 1,2,4,5 , 1,2 dan 2,3 , dengan • 2 5 10 4 2 1 4 2 0 0 0 1 0 1 0 0 ; dan 0 0 1 0 1 0 0 0 5 7 2 2 2 7 2 5 1 2 1,2,3,4,5 , 1,2 dan 1,2,3 , • 2 5 10 4 2 , merupakan 2 1 4 2 2 2 2 2 2 4 . dengan •
5 7
