PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW
ANALISIS EIGENPROBLEM MATRIKS SIRKULAN DALAM ALJABAR MAX-PLUS Maria Ulfa1, Subiono2, dan Mahmud Yunus3 Institut Teknologi Sepuluh Nopember Surabaya1,2,3 e-mail:
[email protected],
[email protected],
[email protected]
ABSTRAK Eigenproblem pada matriks aljabar max-plus telah banyak diteliti. Dalam penelitian ini akan dikaji tentang vektor eigen matriks sirkulan pada aljabar max-plus. Matriks berukuran dimana . Dalam merupakan matriks sirkulan jika dan hanya jika penelitian ini diberikan rumusan langkah-langkah untuk menentukan vektor eigen matriks sirkulan pada aljabar max-plus dan juga membahas mengenai hubungan antara ukuran matriks sirkulan, posisi nilai maksimal dan dimensi dari ruang eigen matriks sirkulan. Kata kunci: Aljabar Max-Plus, Eigenproblem, Matriks Sirkulan, Vektor Eigen.
1. PENDAHULUAN Aljabar max-plus telah banyak digunakan untuk memodelkan suatu permasalahan. Penerapan aljabar max-plus untuk memodelkan suatu permasalahan diantaranya pada penjadwalan, transportasi, manufakturing dan sistem antrian. Eigenproblem pada matriks aljabar max-plus dapat digunakan untuk memperoleh gambaran tentang kedinamikan sistem seperti pada penjadwalan sistem jaringan kereta, penjadwalan sistem produksi, penjadwalan jalur bus dalam kota dan penjadwalan kegiatan pembelajaran sekolah pada kelas moving. Pada penelitian-penelitian tersebut nilai eigen dan vektor eigen dari matriks yang dibentuk dari model yang telah dikontruksi digunakan untuk mengetahui kedinamikan sistem. Matriks sirkulan adalah salah satu matriks khusus yang baris (atau kolomnya) merupakan pergeseran sirkular dari baris (atau kolom) sebelumnya. Seperti halnya matriks biasa, matriks sirkulan juga mempunyai nilai eigen dan vektor eigen. Beberapa penelitian berkaitan dengan matriks sirkulan diantaranya telah dilakukan oleh Gavalec (2010) yang membahas tentang karakteristik struktur ruang eigen matriks sirkulan pada aljabar max-min. Kalman (2001) telah melakukan penelitian tentang persamaan polynomial dan matriks sirkulan. Dalam penelitiannya dibahas tentang konsep dasar matriks sirkulan dan penggunaan matriks sirkulan untuk menyelesaikan persamaan polinomial kuadratik, kubik dan kuartik. Selain itu juga dibahas tentang penggunaan matriks sirkulan untuk menganalisis akar-akar polinomial. Pada penelitian ini akan dibahas mengenai vektor eigen matriks sirkulan dalam aljabar maxplus. 2. ALJABAR MAX-PLUS Aljabar max-plus ( selanjutnya cukup ditulis
,
, ,
) dengan elemen netral dan elemen satuan dimana R adalah himpunan semua bilangan real.
M17-1
PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW Definisi 1. Struktur aljabar [2] menyatakan himpunan dengan operasi biner yaitu maksimum yang Simbol dinotasikan dan penjumlahan yang dinotasikan . didefinisikan dan , Operasi biner dan pada . untuk setiap a,b adalah sebagai berikut: Sifat-sifat dalam aljabar max-plus a. Assosiatif : dan b. Komutatif : dan c. Distributif terhadap : d. Eksistensi elemen nol, yaitu : e. Eksistensi elemen satuan, yaitu : f. Elemen nol adalah absorbing untuk operasi : g. Idempoten dari operasi : Operasi pangkat dalam aljabar max-plus untuk setiap adalah , untuk semua dan untuk didefinisikan . Karena sehingga
, untuk setiap
dalam
. aljabar biasa dapat ditulis dimana . Notasi Himpunan matriks dalam aljabar max-plus dinyatakan atau menyatakan elemen dari matriks pada baris ke-i dan kolom ke-j, n dan m, dengan n . Sebagaimana biasa, matriks dapat ditulis untuk dengan
a11 a A = 21 a n1
a12 a 22 an2
a1m a2m a nm
Operasi penjumlahan matriks A, B , dinotasikan dengan untuk n dan dengan rumus dengan skalar didefinisikan oleh perkalian dengan n dan m. Sedangkan operasi perkalian matriks dinotasikan dengan untuk
didefinisikan m. Operasi , dan
didefinisikan dengan rumus n dan
m.
mempunyai sifat assosiatif, komutatif dan Penjumlahan matriks dalam . Matriks adalah matriks berukuran dengan mempunyai elemen nol yaitu semua elemennya sama dengan . Sedangkan matriks berukuran yang semua elemennya sama dengan , kecuali elemen yang terletak pada baris dan kolom yang sama nilainya sama dan didefinisikan dengan dengan dinotasikan dengan
Perkalian matriks dalam mempunyai sifat assoasiatif, distributif terhadap , mempunyai , serta elemen penyerap untuk operasi . elemen satuan dinotasikan dengan dan didefinisikan oleh Transpose matriks , untuk n dan m. Pangkat ke-k dari matriks A dinotasikan dengan dan didefinisikan , untuk dan . Matriks untuk juga dapat dinyatakan dengan
. M17-2
PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW Suatu graph dapat diubah menjadi bentuk matriks dan begitu pula sebaliknya. Dari dapat dibuat suatu digraph dengan verteks , yang suatu matriks A berukuran didefinisikan sebagai berikut: Definisi 2. Precedence Graph [2] Precedence graph dari matriks bujur sangkar A dengan elemennya adalah sebuah digraph , dimana bobot pada arc berbobot dengan n verteks dan sebuah arc (j, i) ada jika . Precedence graph dinotasikan . adalah nilai dari Suatu path adalah barisan verteks sedemikian hingga ada arc dari ke untuk . verteks adalah verteks awal dan adalah verteks akhir dari path. Path elementer adalah path yang tidak ada verteks muncul (dilalui) lebih dari sekali. Graph disebut strongly connected jika ada suatu path dari setiap verteks ke verteks yang lain. Jika strongly connected maka dikatakan bahwa matriks A irreducible. Path dengan verteks awal dan akhirnya adalah verteks yang sama disebut circuit ( ). Circuit elementer adalah circuit dengan path elementer. Suatu loop adalah circuit ( ) yaitu circuit yang hanya terdiri dari satu verteks, jadi pada loop hanya ada satu arc , dari ke . Panjang dari path adalah jumlah arc pada path tersebut yang dinotasikan dengan dengan demikian maka panjang dari loop adalah 1. Bobot path adalah jumlah dari bobot arc yang membentuk path tersebut yang dinotasikan dengan . Bobot rata-rata path adalah . dan Hal ini juga berlaku jika path merupakan suatu circuit. Circuit dengan bobot circuit panjang circuit maka bobot rata-rata circuit (circuit mean) adalah . Untuk suatu , circuit mean maksimum didefinisikan matriks A dengan circuit yang berbeda . dengan Adapun definisi nilai eigen dan vektor eigen dalam Aljabar Max-Plus diberikan sebagai berikut: Definisi 3. [6] Misalkan matriks A . Jika adalah sebuah skalar dan adalah sebuah , vektor yang memuat minimal satu elemen yang berhingga sehingga memenuhi maka λ disebut nilai eigen dan adalah vektor eigen. Dari suatu vektor eigen yang bersesuaian dengan nilai eigen dapat diperoleh vektor eigen yang lain dari mariks tersebut yang juga bersesuaian dengan nilai eigen . Lemma 4. [1] Misalkan adalah matriks berukuran juga merupakan eigenpair dari .
dengan eigenpair
dan
. Maka
3. MATRIKS SIRKULAN Matriks sirkulan adalah matriks dengan elemen baris pertama dan baris berikutnya merupakan pergeseran kekanan sekali (satu elemen) dari elemen-lemen baris sebelumnya. Jadi elemen matriks sirkulan tergantung pada input baris pertamanya. Berikut adalah bentuk umum matriks sirkulan berukuran
a0 a n −1 a n−2 a 1
a1 a0 a n −1 a2
a 2 a n −1 a1 a n − 2 a 0 a n −3 a3 a 0
M17-3
PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW Definisi 5. [4] Misalkan dimana
matriks berukuran
.
adalah matriks sirkulan jika dan hanya jika
.
Definisi 6. [4] i. Diberikan
maka matriks sirkulan dimana dinotasikan oleh . ii. Vektor (baris pertama dari matriks sirkulan) disebut vektor sirkulan. Pada penjumlahan matriks sirkulan juga menghasilkan matriks sirkulan yang diberikan oleh teorema berikut: Teorema 7. [7] Jika , adalah matriks sirkulan maka Contoh 1 Diberikan matriks
Terlihat bahwa
,
adalah matriks sirkulan.
dan
,
maka
merupakan matriks sirkulan.
4. EIGENPROBLEM MATRIKS SIRKULAN Nilai eigen pada matriks sirkulan, yang merupakan bentuk matriks khusus, dapat diperoleh dengan mudah seperti yang diberikan oleh teorema berikut: Teorema 8. [7] Jika adalah matriks sirkulan maka . dapat diperoleh Sedangkan vektor eigen matriks sirkulan dengan melakukan langkah-langkah sebagai berikut: a. Hitung b. Hitung c. Hitung , dengan d. Hitung Vektor-vektor kolom pada ruang eigen merupakan vektor eigen matriks sirkulan dan vektor eigen tersebut merupakan vektor basis. Dari Lemma 4, vektor-vektor eigen yang lain dapat dicari dengan mengalikan vektor basis dengan suatu skalar. Contoh 2. Diberikan matriks sirkulan , akan ditentukan vektor eigen dari Dengan mengikuti langkah di atas, penyelesaian sebagai berikut:
.
M17-4
PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW
5 4 4 5 4 4
Matriks
4 5 4 4 5 4
4 4 5 4 4 5
5 4 4 5 4 4
4 5 4 4 5 4
4 4 5 . Berdasarkan Teorema 8. maka 4 4 5
0 −1 −1 0 −1 − 2
, selanjut diperoleh
−1 0 −1 −1 0 −1
−1 −1 0 −1 −1 0
0 −1 −1 0 −1 −1
−1 0 −1 −1 0 −1
− 1 − 1 0 − 1 − 1 0
Untuk memperoleh ruang eigen dicari terlebih dahulu , dengan . Karena juga merupakan matriks merupakan matriks sirkulan, berdasarkan Teorema 7. maka cukup menghitung elemen sirkulan. Oleh karena itu, untuk memperoleh elemen-elemen pada baris pertama saja, dari baris pertama dapat ditentukan elemen-elemen baris berikutnya.
Selanjutnya dapat diperoleh
sebagai berikut:
0 −1 −1 0 −1 −1
−1 0 −1 −1 0 −1
−1 −1 0 −1 −1 0
0 −1 −1 0 −1 −1
−1 0 −1 −1 0 −1
− 1 − 1 0 − 1 − 1 0
dengan cepat dapat menggunakan toolbox aljabar Penghitungan memperoleh ruang eigen = maxplusaplus( ). Vektor-vektor max-plus ver. 1.0.1 scilab 5.2.2 dengan mengetikkan kolom pada merupakan vektor eigen dari . Vektor kolom pertama ekivalen dengan vektor kolom ke-4, vektor kolom ke-2 ekivalen dengan vektor kolom ke-5 dan vektor kolom ke-3 ekivalen dengan vektor kolom ke-6 berarti ada 3 kelas ekivalen yang terdiri dari vektor-vektor 0 − 1 − 1 − 1 0 − 1 − 1 − 1 0 basis. Vektor basisnya adalah , dan . Jadi dimensi dari ruang eigen adalah 3. 0 − 1 − 1 − 1 0 − 1 − 1 − 1 0 Teorema 9. [9] sama dengan faktor persekutuan terbesar dari Dimensi ruang eigen dari matriks sirkulan semua posisi nilai maksimal pada baris pertama dan ukuran dari matriks . M17-5
PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW
Contoh 3. Matriks pada Contoh 2. berukuran dan nilai maksimalnya adalah 5, pada baris pertama dan . Jadi dimensi ruang eigen adalah faktor persekutuan nilai maksimal berada pada dan yaitu 3. terbesar dari Berdasarkan Teorema 9. dan contoh matriks sirkulan pada lampiran A, dapat diamati mengenai hubungan antara ukuran matriks sirkulan dan posisi nilai maksimal dengan dimensi dari ruang eigen yang diberikan dalam akibat berikut: Akibat 10. Jika adalah matriks sirkulan berukuran , maka banyak dimensi ruang eigen yang mungkin adalah sebanyak faktor dari . Bukti: Diberikan adalah himpunan faktor dari . Misal adalah dimensi dari ruang eigen dan posisi nilai maksimal berada di untuk beberapa di . Berdasarkan Teorema 9, adalah faktor persekutuan terbesar (FPB) dari dan , berarti adalah faktor dari dan . juga faktor dari maka berukuran dengan adalah elemen Dari Akibat 10. untuk matriks sirkulan bilangan prima, maka banyak dimensi yang mungkin dari ruang eigen adalah sebanyak 2 yaitu dimensi 1 dan dimensi karena faktor dari adalah 1 dan itu sendiri. 5. KESIMPULAN Nilai eigen matriks sirkulan adalah sama dengan nilai elemen matriks yang maksimal. Dimensi ruang eigen tergantung pada ukuran matriks sirkulan dan posisi nilai maksimal pada baris pertamanya, sehingga dimensi ruang eigen yang mungkin dari matriks sirkulan adalah salah satu faktor dari ukuran matriks tersebut. Dimensi ruang eigen matriks sirkulan menunjukkan banyaknya vektor basis dari matriks tersebut. DAFTAR PUSTAKA [1] Andersen, M.H. (2002), Max-plus Algebra: Properties and Applications, Tesis, Laramie, WY. [2] Baccelli, F., Cohen, G., Olsder, G.J. dan Quadrat, J.P. (2001), Synchronization and Linearity An Algebra for Discrete Event Systems, John Wiley & Sons, New York. [3] Gavalec, M., dan Tomaskova, H. (2010), “Eigenspace of a Circulant Max-Min Matrix”, Kybernetika, vol. 46, No.3, hal. 397- 404. [4] Jones, A. W. (2008), Circulants, Carlisle, Pennsylvania. [5] Kalman, D., dan White, J.E. (2001), “Polynomial Equations and Circulant Matrices”, The Mathematical Association of America, hal. 821-840. [6] Konigsberg, Z.R. (2009), “A Generalized Eigenmode Algorithm for Reducible Regular Matrices Over the Max-Plus Algebra”, International Mathematical Forum, vol. 4, No. 24, hal. 1157-1171. [7] Plavka, J., (2001), “On Eigenproblem for Circulant Matrices in Max-Algebra”, Optimization, vol. 50, No. 5, hal. 477-483. [8] Subiono, (2009), Max-Plus Algebra Toolbox ver. 1.01, Jurusan Matematika Institut Teknologi Sepuluh Nopember, Surabaya.
M17-6
PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW [9] Tomaskova, H. (2010), “Eigenproblem for Ciculant Matrices in Max-plus Algebra”, University Hradec Kralove, Czech Republik. A. Penghitungan dimensi ruang eigen menggunakan Teorema 9. Matriks sirkulan berukuran Posisi nilai maksimal , =0 =1 =1 Matriks sirkulan berukuran Posisi nilai maksimal , =0 =1,2 =1,2 Matriks sirkulan berukuran Posisi nilai maksimal , =0 2 2 =1,3 =1,3 Matriks sirkulan berukuran Posisi nilai maksimal , =0 =1,2,3,4 =1,2,3,4 Matriks sirkulan berukuran Posisi nilai maksimal , =0 =3 =3 2,4 2,4 =1,5 =1,5 Matriks sirkulan berukuran Posisi nilai maksimal , =0 =1,2,3,4,5,6 =1,2,3,4,5,6 Matriks sirkulan berukuran Posisi nilai maksimal , =0 =4 =4 2,6 2,6 =1,3,5,7 =1,3,5,7
Dimensi 2 1
Dimensi 3 1
Dimensi 4 2 1
Dimensi 5 1
Dimensi 6 3 2 1
Dimensi 7 1
Dimensi 8 4 2 1
M17-7
PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW
Matriks sirkulan berukuran Posisi nilai maksimal , =0 3,6 3,6 =1,2,4,5,7,8 =1,2,4,5,7,8 Matriks sirkulan berukuran Posisi nilai maksimal , =0 =5 =5 2,4,6,8 2,4,6,8 =1,3,7,9 =1,3,7,9 Matriks sirkulan berukuran Posisi nilai maksimal , =0 =1,…,11 =1,…,11 Matriks sirkulan berukuran Posisi nilai maksimal , =0 =6 =6 =4,8 =4,8 =3,9 =3,9 2,10 2,10 =1,5,7,11 =1,5,7,11 Matriks sirkulan berukuran Posisi nilai maksimal , =0 =1,…,13 =1,…,13 Matriks sirkulan berukuran Posisi nilai maksimal , =0 =7 =7 2,4,6,8,10,12 2,4,6,8,10,12 =1,3,5,9,11,13 =1,3,5,9,11,13
Dimensi 9 3 1
Dimensi 10 5 2 1
Dimensi 11 1
Dimensi 12 6 4 3 2 1
Dimensi 13 1
Dimensi 14 7 2 1
M17-8
