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
