Jurnal Matematika & Sains, April 2014, Vol. 19 Nomor 1
Ruang Vektor Eigen Suatu Matriks Atas Aljabar Max-Plus Interval Siswanto1), Ari Suparwanto2), dan M. Andy Rudhito3) 1) Jurusan Matematika FMIPA UNS Surakarta, 2) Jurusan Matematika FMIPA Universitas Gadjah Mada Yogyakarta 3) FKIP, Universitas Sanata Dharma Yogyakarta e-mail :
[email protected],
[email protected],
[email protected] Diterima 22 November 2013, disetujui untuk dipublikasikan 7 Maret 2014 Abstrak Misalkan himpunan bilangan real. Aljabar Max-Plus adalah himpunan max = {-} dilengkapi dengan operasi maksimum dan plus . Dapat dibentuk himpunan matriks berukuran n n yang elemen-elemennya n merupakan anggota himpunan max, ditulis nmax . Dibentuk himpunan I()max yaitu himpunan yang anggotanya merupakan interval-interval tertutup dalam max. Himpunan I()max dilengkapi dengan operasi dan disebut aljabar Max-Plus interval. Selanjutnya, dapat pula dibentuk himpunan matriks berukuran n n yang elemenn n n elemennya merupakan anggota himpunan I()max, ditulis I () nmax . Misalkan A I () nmax dan [ A, A] I ( nmax )b , dengan A [ A, A] , matriks interval A dikatakan tak tereduksi jika untuk setiap matriks A [ A, A] tak tereduksi. Jika tidak demikian matriks interval A dikatakan tereduksi. Dalam penelitian ini akan dibahas tentang ruang vektor eigen suatu matriks atas aljabar Max-Plus interval. Kata kunci : Ruang vektor eigen, Aljabar Max-Plus interval.
Eigenvector Space of a Matrix of Interval Max-Plus Algebra Abstract Let be the set of real numbers. Max-Plus Algebra is the set max = {-} equipped with the maximum n operation and plus . The set nmax is a set of n n matrix with entries belonging to max. Set I()max i.e the set whose members are closed intervals in max.The set I()max equipped with the maximum operation and plus called interval Max-Plus algebra. Furthermore, we can also form the set of size n n matrices whose elements are n n n members of the set I()max written I () nmax . Suppose A I () nmax and [ A, A] I (nmax )b where A [ A, A] , the interval matrices A is irreducible if for any matrix A [ A, A] irreducible. Otherwise the interval matrix A is said reducible. In this research we will discuss eigenvector space of interval Max-Plus algebra matrix. Keywords : Eigenvector space, Interval Max-Plus algebra. matriks berukuran m n. Khusus untuk n = 1 diperoleh himpunan vektor atas aljabar Max-Plus ditulis m max (Farlow, 2009). Schutter (1996) dan Subiono (2000) telah membahas tentang masalah n nilai eigen dan vektor eigen suatu matriks A nmax , sedangkan Butkovic dan Tam (2009) serta Tam (2010) telah membahas tentang ruang vektor eigen matriks atas aljabar Max-Plus. Untuk menyelesaikan masalah jaringan dengan waktu aktivitas bilangan kabur seperti penjadwalan kabur dan sistem antrian kabur, aljabar Max-Plus telah digeneralisasi menjadi aljabar MaxPlus interval dan aljabar Max-Plus bilangan kabur. Aljabar Max-Plus interval yaitu himpunan I()max dilengkapi dengan operasi maksimum dan , sedangkan aljabar Max-Plus bilangan kabur yaitu dan himpunan F()max dilengkapi dengan operasi
1. Pendahuluan Aljabar Max-Plus adalah himpunan max { }, dilengkapi dengan operasi maksimum dan plus . Aljabar Max-Plus telah digunakan untuk memodelkan dan menganalisis secara aljabar masalah perencanaan, komunikasi, produksi, sistem antrian dengan kapasitas berhingga, komputasi parallel, dan lalu lintas (Bacelli dkk., 2001). Dari himpunan max dapat dibentuk himpunan matriks berukuran n n yang elemen-elemennya n , merupakan elemen max dinotasikan dengan nmax disebut himpunan matriks atas aljabar Max-Plus. Himpunan ini dilengkapi dengan operasi maksimum dan plus merupakan semiring idempoten (Akian, dkk., 1994; Konigsberg, 2009). Secara umum, juga n yaitu himpunan didefinisikan himpunan m max
8
9
Siswanto, dkk., Ruang Vektor Eigen Suatu Matriks Atas Aljabar Max-Plus Interval (Rudhito, 2011). Telah dibahas juga oleh Rudhito (2011) tentang matriks atas aljabar Max-Plus interval, graf dalam aljabar Max-Plus interval serta nilai eigen dan vektor eigen matriks atas aljabar Max-Plus interval khusus untuk matriks tak tereduksi. Selain itu, Siswanto (2012) telah membahas tentang nilai eigen dan vektor eigen matriks tereduksi regular atas aljabar Max-Plus interval. Dari uraian tersebut, menarik untuk diteliti tentang ruang vektor eigen matriks atas aljabar MaxPlus interval. Sebelum dibahas hasil penelitian ini, terlebih dahulu akan ditinjau beberapa konsep dasar dan hasil-hasil yang mendukung pembahasan.
Kajian Pustaka Berikut adalah definisi tentang aljabar MaxPlus, matriks atas aljabar Max-Plus beserta operasinya dan graf (Bacelli dkk., 2001; Farlow, 2009; Konigsberg, 2009). Definisi 1. Misalkan himpunan bilangan real, definisikan himpunan max = {} dengan = -. Himpunan max yang dilengkapi dengan operasi maksimum dan plus sehingga merupakan semifield idempoten, disebut aljabar Max-Plus dan dinotasikan dengan max (max ; , ) . Definisi 2. Himpunan matriks berukuran m n dengan elemen-elemen dalam max dinotasikan n n yaitu m dengan m max max {[ Aij ] | Aij max } . n Himpunan nmax dilengkapi dengan operasi dan n n (nmax ; , ) sehingga merupakan ditulis nmax semiring idempoten dengan elemen netral dan elemen identitas masing-masing adalah nn dan En n .
Definisi 3. Diberikan himpunan V dan E V V dimana V merupakan himpunan titik (node) dengan anggota berhingga dan E terdiri atas himpunan pasangan terurut titik yaitu busur (edge atau arc). Selanjutnya D = (V, E) disebut sebagai graf berarah (directed graph). Definisi 4. Grafik berarah D = (V, E) yang dilengkapi fungsi bobot w : E max, disebut graf berarah berbobot (weighted directed graph). Selanjutnya disajikan konsep dari lintasan (path), sikel (cycle) dan sikel elementer (elementary cycle) dalam suatu graf berarah. Definisi 5. Misalkan D = (V, E) adalah graf berarah. Barisan (v1…, vp+1) disebut lintasan jika vi V , i 1,..., p 1 dan (v1, v p 1 ) E , i 1,..., p . Lintasan (v1 , v p 1 ) dikatakan mempunyai panjang
p, v1 sebagai titik awal dan vp+1 sebagai titik akhir dari . Definisi 6. Misalkan D = (V, E, w) adalah graf berarah berbobot dan (v1…, vp+1) lintasan dari v1 ke vp+1, bobot lintasan didefinisikan sebagai w(v1, v2) + w(v2, v3) + … + w(vp, vp+1). Definisi 7. Misalkan bahwa D = (V, E) adalah graf berarah maka (v1…, vp+1) disebut sikel jika adalah lintasan dan v1 = vp+1. Definisi 8. Misalkan D = (V, E) adalah graf berarah maka (v1…, vp+1) disebut sikel elementer jika adalah sikel dan vi vj untuk semua i, j = 1, …, p dan i j. Definisi 9. Misalkan bahwa D = (V, E) adalah graf berarah dan u,v V. Maka v dikatakan dapat dicapai dari u jika ada lintasan dari u ke v. Definisi 10. Graf berarah D = (V, E) dikatakan terhubung kuat (strongly connected) jika u dapat dicapai dari v untuk semua u,v V. n , graf berarah Definisi 11. Misalkan A [ Aij ] nmax
berbobot yang bersesuaian dengan A adalah DA = (N,E = {(i,j)|Aij > }, w) dimana w(i,j) = Aji untuk setiap (i,j) E. n dan DA merupakan Definisi 12. Misalkan A nmax graf berarah berbobot yang bersesuaian dengan A. Matriks A disebut tak tereduksi jika DA terhubung kuat. Jika tidak demikian A disebut tereduksi.
Definisi 13. Misalkan
n A nmax , didefinisikan
matriks ( A) A A2 . n Definisi 14. Misalkan A nmax dan DA merupakan graf berarah berbobot yang bersesuaian dengan A. Misalkan adalah sikel dalam DA. Definisikan w( , A) ( , A) , dimana w() merupakan bobot l ( )
dari sikel dan l() merupakan panjang dari sikel. Bilangan (,A) disebut rata-rata bobot dari sikel dan (A) = max(,A) yaitu rata-rata bobot maksimum dari A. n dan (A) > , Teorema 1. Jika A nmax maka ( A) = (A). n , Definisi 15. Misalkan A nmax dikatakan definit jika (A) = 0.
matriks
A
10 Jurnal Matematika & Sains, April 2014, Vol. 19 Nomor 1 Teorema
2.
n A nmax
Jika
definit
maka
( A) A A2 A n . Berdasarkan Teorema 1, untuk setiap matriks tak tereduksi A dapat dibentuk A = (A)-1 A, dengan A definit. Dengan demikian, ( A ) A A2 A n . Selanjutnya, disajikan tentang konsep-konsep yang berhubungan dengan nilai eigen dalam aljabar Max-Plus. n A nmax
dan max Definisi 16. Diberikan didefinisikan : a. V ( A, ) {x nmax | A x x} , b. c. d. e.
( A) { max | V ( A, ) { n1}} , V ( A) ( A) V ( A, ) ,
V ( A, ) V ( A, ) , n
1.
Diberikan
n A, B nmax ,
, , max , max dan x, maka a. b. c. d.
y nmax
V ( A) V ( A) ,
( A) ( A) , V ( A, ) V ( B, ) V ( A B, ) , V ( A, ) V ( B, ) V ( A B, ) .
Definisi 17. Misalkan
4.
Jika
n A nmax , A nn
dan
V ( A) maka (A) > dan A x = (A) x,
x V+(A). n , A nn , maka berlaku : Teorema 5. Jika A nmax
a. V ( A) ( A)
dan
di
dalam
b. Jika V ( A) maka V ( A) {jE ( A) j g j ;
V ( A) V ( A) .
Proposisi
Teorema
DA , j N , i E ( A) sehingga j i.
n
n , ( A) nilai eigen Teorema 3. Misalkan A nmax dari matriks A. Jika (A) > maka paling banyak terdapat n vektor eigen yang bersesuaian dengan (A) yang dapat ditemukan di antara gk kolom-kolom dari (A). Kolom-kolom dari (A) yang elemen diagonalnya 0 merupakan vektor eigen dari A yang bersesuaian dengan nilai eigen (A). Basis dari V(A,(A)) diperoleh dengan mengambil tepat satu gk untuk setiap kelas ekuivalensi di dalam (E(A), ~).
n A nmax , N {1, 2, , n} .
Definisikan E ( A) {i N | (i i1 , i2 , , ik , i1 ) dalam DA ( , A) ( A)} . Anggota E(A) disebut sebagai titik-titik eigen atau titik-titik kritis dari graf berarah berbobot yang bersesuaian dengan A. Sikel disebut sebagai sikel kritis jika (,A) = (A). Gabungan himpunanhimpunan busur dari sikel kritis membentuk graf berarah C(A) dan C(A) disebut sebagai graf berarah kritis dari A. n . Jika C(A) merupakan Lema 1. Diberikan A nmax graf berarah kritis dari A maka semua sikel di C(A) adalah sikel kritis. Dua titik i dan j dalam C(A) ekuivalen jika i dan j keduanya termuat dalam sikel kritis yang sama dari A. Relasi ini dinotasikan dengan i j dan merupakan relasi ekuivalensi dalam E(A). n . Jika (A) = , maka Lema 2. Diberikan A nmax (A) = {} merupakan nilai eigen dari A yang bersesuaian dengan vektor ( x1 , x2 , , xn )T nmax sehingga xj = jika kolom ke-j dari A tidak sama dengan vektor , j N.
j } dimana g1, g2, …, gn adalah kolomkolom dari (A). n 6. Jika A nmax , ( A) , ( A ) ( gij ) dan g1, g2, …, gn adalah kolom-kolom
Teorema
dari (A) maka a. i E ( A) gii 0 , b. Jika i, j (A) maka gi = gj untuk suatu jika dan hanya jika i ~ j. n Akibat 1. Misalkan A nmax . Jika ( A) , g1, g2, …, gn adalah kolom-kolom dari (A) dan V ( A) , maka V ( A) {jE* ( A) j g j ; j }
dengan E*(A) adalah suatu himpunan maksimal titiktitik kritis dari A yang tidak ekuivalen. Teorema 7. Setiap matriks tak tereduksi n A nmax , (n 1) mempunyai nilai eigen tunggal
yaitu (A) dan V ( A) { } V ( A) {jE* ( A) j g j ; j } dimana g1, g2, …, gn adalah kolom-kolom
dari (A). Matriks A11 = [] merupakan matriks tak tereduksi dan V(A) = V+ (A) = . Untuk matriks tak tereduksi Ann dengan n > 1, bobot terbesar dari semua lintasan (i,j) tidak sama dengan . Oleh karena berhingga dan itu, elemen-elemen (A) V ( A) V ( A) { } {( A ) z | z nmax ,
z j , j E ( A)} Selanjutnya, dibicarakan konsep aljabar MaxPlus interval, matriks, graf di dalam aljabar Max-Plus interval.
11
Siswanto, dkk., Ruang Vektor Eigen Suatu Matriks Atas Aljabar Max-Plus Interval Interval tertutup x dalam max adalah suatu himpunan bagian dari max yang berbentuk x [ x, x ] {x max | x m x m x } . Interval x dalam max disebut interval Max-Plus. Suatu bilangan x max dapat dinyatakan sebagai interval [ x, x ] .
isomorfisma di atas maka berlaku A [ A, A] , A B [ A B, A B ] dan A B [ A B, A B ] .
Definisi 22. Definisikan I () nmax {x [ x1 , x2 , , xn ]T | x j I () max ; i 1, 2,, n}.
Himpunan Definisi 18. Definisikan I () max {x [ x, x ] | x, x , m x m x } { }
dengan = [, ]. Pada himpunan didefinisikan operasi x y [ x y, x y ] dan
himpunan
I () max
dan dengan x y [ x y, x y ]
untuk setiap x, y I () max . Himpunan I () max dilengkapi dengan operasi dan merupakan semiring idempoten komutatif dengan elemen netral = [, ] dan elemen satuan 0 [0, 0] . Selanjutnya disebut aljabar Max-Plus interval dan dinotasikan dengan I () max ( I () max ; , ) . Definisi 19. Himpunan matriks berukuran m n dengan elemen-elemen dalam I () max dinotasikan n n dengan I () mmax yaitu I ()mmax { A [ Aij ] | Aij I () max ,
i 1, 2, , m
mn
j 1, 2, , n} . Matriks anggota I () max
disebut matriks interval Max-Plus. Selanjutnya matriks interval Max-Plus cukup disebut dengan matriks interval. Definisi
matriks
n A I () m max
Untuk
20.
A [ Aij ]
mn
dan
didefinisikan
A [ Aij ] mn
masing-masing disebut matriks batas bawah dan matriks batas atas dari matriks interval A. n Definisi 21. Diberikan matriks interval A I () m max ,
dengan A dan A masing-masing adalah matriks batas bawah dan matriks batas atas dari matriks A. Didefinisikan interval matriks dari A yaitu n n [ A, A] { A m dan I (m max )b max | A m A m A} n {[ A, A] | A I () m max } . n n Semiring I () nmax ( I () nmax ; , ) isomorf
dengan dengan
n I ( nmax )b
semiring pemetaan
f
n ( I (nmax )b ; , ) nn n : I () max I (nmax )b ,
n sedangkan semimodul f ( A) [ A, A], A I () nmax
n I () nmax atas I () max isomorf dengan semimodul n I (nmax )b
atas
n [ A, A] I ( m max )b
I () max .
matriks
disebut interval matriks yang
bersesuaian dengan interval dilambangkan
Interval
dengan
n A I () m max
A [ A, A] .
dan Akibat
I () nmax n1 I () max
dapat
dipandang
sebagai
. Unsur-unsur dalam I () nmax
disebut vektor interval dalam I () nmax . Vektor interval x bersesuaian dengan interval vektor [ x, x ] yaitu x [ x, x ] . Selanjutnya disajikan konsep graf berarah berbobot interval. Misalkan D = (N,E) adalah graf berarah dengan N = {1,2,,n} dan E N N. Graf berarah dikatakan berbobot interval jika setiap busur (j,i) E dikawankan dengan suatu interval tertutup bilangan real Aij ( I () max {[ , ]}) . Interval bilangan real Aij disebut bobot interval busur (j,i), dinotasikan dengan w(i,j). Graf preseden (graf n didefinisikan komunikasi) dari matriks A I () nmax sebagai graf berarah berbobot interval DA = (N, E) dengan N = {1,2,,n} dan E {( j , i ) | w(i, j ) Aij [ , ]} . Sebaliknya untuk setiap graf berarah berbobot interval DA = (N, E) selalu dapat n yang didefinisikan suatu matriks A I () nmax disebut matriks bobot interval graf D dengan w( j , i ), jika (i, j ) E . [ , ], jika (i, j ) E 2. Hasil dan Pembahasan
Pada bagian ini disajikan hasil utama dari penelitian yaitu tentang ruang vektor eigen dan basis suatu matriks atas aljabar Max-Plus interval. Definisi
23.
Diberikan
n A I () nmax
dengan
n [ A, A] I (nmax )b
A dan [ , ] I () max , didefinisikan : dan a. V ( A, ) {x I () nmax | A x x}
V ([ A, A],[ , ]) { I (nmax )b | A x x ; A x x}
b. ( A) { I () max | V ( A, ) { n1}, n1 ( , , , )T } dan ( A, A) {[[ ],[ ]] I (max )b | V ([ A, A] , [ , ]) {[ , ]}}
c. V ( A) ( A) V ( A, ) dan V ([ A, A] [ , ] ([ A, A ]) V ([ A, A],[ , ]) , d. V ( A, ) V ( A, ) I () n dan V ([ A, A],[ , ]) V ([ A, A],[ , ]) I ( n )b
12 Jurnal Matematika & Sains, April 2014, Vol. 19 Nomor 1 e. V ( A) V ( A) I () n
V ([ A, A]
dan
V ([ A, A]) I ( )b n
V ([ A, B, A B ],[ , ]) . n I () nmax
Berdasarkan isomorfisma diperoleh : i. V ( A, ) V ([ A, A],[ , ]) ,
dan
( A) ([ A, A]) ,
iii.
V ( A) V ([ A, A]) ,
iv.
V ( A, ) V ([ A, A],[ , ]) ,
v.
V ( A) V ([ A, A]) .
V ([ A B, A B ],[ , ]) .
Oleh karena itu, V ( A, ) V ( B, ) V ( A B, ) . ■ n A, B I () nmax ,
[ , ] I (),[ , ], [ , ] I () max maka
a. V ( A) V ( A) . b. ( A) ( A) d. V ( A, ) V ( B, ) V ( A B, ) .
Definisi
V ([ A, A]) dan V ( A) V ([ A, A]) . Menurut Proposisi 1, V ( A) V ( A) dan V ( A) V ( A) ,
berarti
V ([ A, A])
V ([ A, A]) . Oleh karena itu, V ( A) V ( A) .
b. Menurut Definisi 23 ( A) ([ A, A]) dan ( A) [ , ] ([ A, A]) ([ (A), (A)] . Menurut Proposisi 1, ( A) ( A) dan ( A) ( A) .
Oleh
karena
itu,
( A) ( A) . c. Menurut Definisi 23, V ( A, ) V ([ A, A],[ , ]) dan V ( B, ) V ([ B, B ],[ , ]) sedangkan V ( A B, ) V ([ A, A] [ B, B ],[ , ] [ , ])
= V ([ A B, A B ],[ , ]) . Menurut
Proposisi
1,
V ( A, ) V ( B, )
V ( A B, ) dan V ( A, ) V ( B , ) V ( A B , ) maka
V ([ A, A],[ , ]) V ([ B, B ],[ , ]) V ([ A B, A B ],[ , ]) Oleh karena itu, V ( A, ) V ( B, ) V ( A B, ) . d. Menurut Definisi 23, bahwa V ( A, ) V ([ A, A],[ , ]) dan V ( B, ) V ([ B, B ],[ , ]) sedangkan
dan
( , A) ( A)} , dan E ( A) E ([ A, A]) . V ( A)
23,
n nn Definisi 24. Misalkan A I ()nmax , A [ A, A] I ( Rmax )b dan N = {1,2,, n} definisikan i. E ( A) {i N | (i i1 , i2 , , ik , i1 ) dalam DA ( , A) ( A)} ,
ii. E ([ A, A) {i N | (i i1 , i2 , , ik , i1 ) dalam DA dan DA ( , A) ( A)
c. V ( A, ) V ( B, ) V ( A B, )
Bukti : a. Berdasarkan
Menurut Proposisi 1, V ( A, ) V ( B, ) V ( A B, ) dan V ([ A, A],[ , ]) V ([ B, B ],[ , ]
Diberikan
2.
n I (nmax )b
V ( A, ) V ( B , ) V ( A B , ) maka
ii.
Proposisi
V ( A B, ) V ([ A, A] [ B, B ],[ , ] [ , ])
Anggota E(A) disebut sebagai titik-titik eigen atau titik-titik kritis dari graf berarah berbobot interval yang bersesuaian dengan A. Sikel disebut sebagai sikel kritis jika (,A) = (A). Dari titik-titik kritis dan busur-busur semua sikel kritis, dapat dibuat graf berarah C(A) disebut graf berarah kritis dari A. n Lema 3. Misalkan A I () nmax . Jika C(A) adalah graf berarah kritis dari A maka semua sikel dalam C(A) merupakan sikel kritis.
Bukti : Karena C(A) adalah graf berarah kritis dari A, sehingga C(A) merupakan gabungan himpunan busur yang merupakan sikel kritis. Dengan demikian, sirkuit dalam C(A) merupakan sikel kritis. ■
Dua titik i dan j dalam C(A) dikatakan ekuivalen jika i dan j keduanya termuat dalam sikel kritisyang sama dari A dinotasikan i ~ j. Dapat dibuktikan bahwa ~ merupakan relasi ekuivalensi di dalam E(A). n Lema 4. Diberikan A I () nmax , n A [ A, A] I (nmax )b . Jika (A) = [,] maka (A)
={[,]} dan vektor-vektor eigen dari matriks A adalah vektor [ x1 , x2 , , xn ]T I () nmax sehingga xj = [,] bila kolom ke-j dari matriks A tidak sama dengan vektor ,j N. Bukti : Diketahui (A) = [,]. Untuk matriks batas bawah A, (A) = . Menurut Lema 2, (A) = {} dan vektorvektor eigen dari matriks A adalah vektor
13
Siswanto, dkk., Ruang Vektor Eigen Suatu Matriks Atas Aljabar Max-Plus Interval [ x1 , x2 , , xn ]T nmax sehingga xj = . bila kolom ke-j dari matriks A tidak sama dengan vektor ,j N. Demikian juga untuk matriks batas atas A . Oleh karena itu, diperoleh ( A) ([ A, A] {[ ], [ ]} dan vektor-vektor eigen dari matriks A adalah vektor [ x1 , x2 , , xn ]T [[ x1 , x 2 , x n ]T ,[ x1 , x2 , , xn ]T ]
sehingga x j [[ ], [ ]] bila kolom ke-j dari matriks A tidak sama dengan vektor [ , ], j N . ■
Bukti : Diketahui
n A [ A, A] I ( nmax )b dan (A) merupakan nilai eigen matriks A yang memenuhi [ , ] m [ ( A), ( A)] ( A) . Karena ( A) dan
( A) masing-masing nilai eigen matriks A dan A dengan ( A) dan ( A) maka dapat ditentukan matriks-matriks dan ( A ) ( g ) ij
( A ) ( gij ) .
Definisi 25. Misalkan g
k
dan g k , k 1, 2, , n
masing-masing adalah kolom-kolom matriks ( A ) dan ( A ) . Dibentuk matriks ( A ) dengan beberapa cara, salah satunya bahwa kolom-kolom matriks ( A ) ditentukan sebagai berikut : dan g k memenuhi i. Jika pasangan g k
g m g k , k 1, 2, , n k
maka diperoleh satu
kolom yaitu vektor interval g k [ g , g k ] . k
ii. Jika pasangan g
k
dan g k
g m g k , k 1, 2, , n k * gk
gk
tidak memenuhi
dapat
dibentuk
dengan maksi (( g k )i ( g )i ), k
i 1, 2, , n sehingga diperoleh satu kolom yaitu
vektor interval g k [ g , g k* ] . k
Oleh karena itu, matriks ( A ) [ g1 , g 2 g n ] . Teorema 8. Misalkan n n A I () nmax , A [ A, A] I (nmax )b dan (A) merupakan nilai eigen matriks A. Jika [ , ] m ( A) maka kolom-kolom matriks ( A ) dengan batas bawah elemen diagonalnya 0 merupakan vektor-vektor eigen yang bersesuaian dengan (A). Selanjutnya, basis dari V(A,) diperoleh dengan mengambil satu gk untuk setiap kelas ekuivalensi di dalam (E(A),~).
dan
( A) [ ( A), ( A)] nilai eigen matriks A, dengan
(A) dan ( A) masing-masing nilai eigen matriks A dan A . Karena [ , ] m [ ( A), ( A)] ( A) maka
(A) > dan ( A) sehingga dapat ditentukan matriks ( A ) ( g ) dan ( A ) ( gij ) . Misalkan ij
g
Lema 4 menjamin penyelesaian untuk (A) = Selanjutnya, akan dibahas untuk [,]. n . Misalkan A I ( ) nmax , [ , ] m [ ( A), ( A)] ( A)
n n A I () nmax , A [ A, A] I (nmax )b
dan g k , k 1, 2, , n , masing-masing adalah
k
kolom-kolom matriks matriks ( A ) dan ( A ) . Menurut Definisi 25 dan Teorema 3 dapat diperoleh sejumlah n vektor eigen yang bersesuaian dengan (A) dari kolom-kolom matriks ( A ) dengan batas bawah elemen diagonal 0. Basis dari V(A,) diperoleh dengan mengambil satu vektor interval gk untuk setiap kelas ekuivalensi di dalam (E(A),~). ■ Teorema 9. Misalkan n n A I () nmax , A [ A, A] I (nmax )b dan A bukan matriks yang setiap elemennya [,] dan V+(A) maka m ( A) dan A x ( A) x, x V ( A) . Bukti : Perhatikan matriks batas bawah dan matriks batas atas A dan A . Karena A bukan matriks yang setiap elemennya [,] dan V+(A) , berarti A dan A bukan matriks yang setiap elemennya dan V ( A) , V ( A) . Menurut Teorema 4,
( A) ,
( A)
A x ( A) x ;
dan
A x ( A) x ,
x V ( A), x V ( A) .
Oleh
karena itu, diperoleh [ , ] m [ ( A), ( A)] ( A) dan
A x ( A) x, x V ( A)
x [ x, x ], x V ( A) .
dengan
■
Selanjutnya akan disajikan salah satu hasil khusus di dalam aljabar Max-Plus interval. Teorema 10. Misalkan n n A I () nmax , A [ A, A] I (nmax )b dan A bukan matriks yang setiap elemennya [,], maka berlaku : dan di dalam a. V ( A) m ( A) DA , j N , i E ( A) sedemikian sehingga j i. b. Jika V ( A) maka V ( A) {jE ( A) j g j ; j I ()} dimana g1, g2,, gn adalah kolom-
kolom dari (A). Bukti : n Misalkan A I () nmax ,
14 Jurnal Matematika & Sains, April 2014, Vol. 19 Nomor 1 n A [ A, A] I (nmax )b dan A bukan matriks yang setiap elemennya [,]. Oleh karena itu, matriks batas bawah dan batas atas atas A dan A bukan matriks yang setiap elemennya . Menurut Teorema 5 dipenuhi : (a) V ( A) ( A) dan di dalam
b. Jika i, j E ( A) maka g g i
juga, jika i, j E ( A) maka gi g j atau g i* g *j untuk suatu I () jika dan
hanya jika i ~ j. Oleh karena itu, jika i, j E ( A) maka
i. Demikian juga, V ( A) ( A) dan hingga j i. (b) Jika V ( A) maka V ( A) {jE ( A) j g ; j
j I ()}
dimana
adalah
g1 , g 2 ,, g n
kolom-kolom dari (A). Demikian juga, jika V ( A) maka V ( A) {jE ( A) j g j ;
j } dimana g1 , g 2 , , g n adalah kolomkolom dari ( A ) .
■
Dari (a) diperoleh, V ( A) m ( A) dan di dalam DA , j N , i E ( A) sedemikian sehingga j i. Dari (b) dan berdasarkan Definisi 25 dapat dibentuk matriks (A), sehingga jika V+(A)
maka V ( A)
{ jE ( A) j
g j ; j I ()} dimana
g1, g2,, gn adalah kolom-kolom dari (A). Teorema 10 memberikan syarat perlu dan cukup adanya vektor eigen berhingga dan bagaimana membentuk himpunan vektor eigen berhingga. Teorema
Misalkan
11.
n A I () nmax ,
n A [ A, A] I ( nmax )b , m ( A) dan g1, g2,, gn
adalah kolom-kolom dari (A), = (gij) maka i E ( A) g 0 . i. ii
ii.
Jika i, j E ( A) maka gi g j untuk suatu
I() jika dan hanya jika i ~ j. Bukti : Perhatikan matriks batas bawah dan matriks batas atas A dan A , berarti (A) > , ( A) , adalah kolom( A ) ( g ) dan g , g , , g 1
ij
2
n
kolom dari ( A ) . Demikian juga ( A ) ( gij ) dan g1 , g 2 , , g n adalah kolom-kolom dari ( A ) . Menurut Teorema 6 dipenuhi : a. i E ( A) g 0 dan i E ( A) gii 0 . ii
Berdasarkan Definisi 25, i E ( A) gi [ g , gii ] [0, 0] ii
gi [ g , g ii* ] [0, ] . ii
i E ( A) g 0 . ii
Oleh
diperoleh atau karena
itu,
untuk suatu
I () jika dan hanya jika i ~ j. Demikian
DA , j N , i E ( A) sedemikian sehingga j
di dalam DA , j N , i E ( A) sedemikian se-
j
gi g j untuk suatu I () jika
dan hanya jika i ~ j.
■
n Akibat 2. Misalkan A nmax . Jika m ( A) , g1, g2,, gn adalah kolom-kolom dari (A) dan V+(A) maka V ( A) {jE* ( A) j g j ; j I ()} , dengan
E * ( A) adalah suatu himpunan maksimal titik-titik kritis dari A yang tidak ekuivalen.
Bukti : n Misalkan A nmax . Diketahui m ( A) , g1, g2,, gn adalah kolom-kolom dari (A) dan V+(A) . Perhatikan matriks batas bawah dan matriks batas atas yaitu A dan A . Oleh karena itu, (A) > , g , g , , g adalah kolom-kolom dari (A) dan 1
2
n
V (A) , Demikian juga, ( A) ; g1 , g 2 , , g n +
adalah kolom-kolom dari ( A ) dan V ( A) . Menurut
Akibat
1,
j } dan V ( A)
V ( A) {jE* ( A) j g ; j
{jE* ( A ) j
g j ; j } .
Dengan demikian diperoleh, j I ()} , dengan V ( A) {jE* ( A) j g j ; a j g j [ j g , j g j ] . ■ j
Dari Teorema 10 dan Teorema 11, diperoleh cara untuk membentuk himpunan vektor eigen berhingga. Dengan menggunakan hasil yang diperoleh dari Teorema 10 dan Teorema 11, dapat ditarik kesimpulan tentang penyelesaian masalah eigen untuk matrik tak tereduksi, yang disajikan pada teorema berikut. Teorema 12. Setiap matriks tak tereduksi n A I () nmax , (n 1) mempunyai nilai eigen tunggal (A) dan yang sama dengan V ( A) { } V ( A) { jE* ( A) j g j ; j I ()}
dimana g1, g2,, gn adalah kolom-kolom dari (A). Bukti : Perhatikan matriks batas bawah dan matriks batas atas A dan A merupakan matriks tak tereduksi. Menurut Teorema 7, A dan A mempunyai nilai eigen tunggal ( A), ( A) , dan V ( A) { } V ( A)
Siswanto, dkk., Ruang Vektor Eigen Suatu Matriks Atas Aljabar Max-Plus Interval
15
{jE* ( A) j g ; j I ()} dimana g1 , g 2 , , g n
Daftar Pustaka
adalah kolom-kolom dari ( A ) dan E * ( A) adalah
Akian, M., G. Cohen, S. Gaubert, J.P. Quadrat, and M. Viot, 1994, Max-Plus Algebra and Applications to System Theory and Optimal Control. Proceedings of the International Congress of Mathematicians. Zurich, Switzerland. Bacelli, F., G. Cohen, G. J. Olsder, and J. P. Quadrat, 2001, Synchronization and Linearity, New York : John Wiley & Sons. Butkovic, P. and K. P. Tam, 2009, On Some Properties of The Image of a Max Linear Mapping. Contemporary Mathematics. Volume 495. Farlow, K. G., 2009, Max-Plus Algebra. Master's Thesis submitted to the Faculty of the Virginia Polytechnic Institute and State University in partial fulfillment of the requirements for the degree of Masters in Mathematics. Konigsberg Z. R., 2009, A Generalized Eigenmode Algorithm for Reducible Regular Matrices over the Max-Plus Algebra. International Mathematical Forum, 4. 24. 1157 – 1171. Rudhito, A., 2011, Aljabar Max-Plus Bilangan Kabur dan Penerapannya pada Masalah Penjadwalan dan Jaringan Antrian. Disertasi : Program Studi S3 Matematika FMIPA UGM. Yogyakarta. Schutter, B. D, 1996, Max Algebraic System Theory for Discrete Event Systems.Ph.D Thesis, Katholike Universiteit Leuven, Departement Elektrotechniek. Siswanto, 2012, Nilai Eigen dan Vektor Eigen Matriks Tereduksi Reguler dalam Aljabar Max-Plus Interval. Prosiding Seminar Nasional Matematika dan Pendidikan Matematika Jurusan Pend. Matematika FMIPA UNY. MA – 99. Subiono, 2000, On Classes of Min-Max-Plus Systems and Their Applications, Published by Delf University Press. Tam, K. P., 2010, Optimizing and Approximating Eigenvectors In Max-Algebra. A thesis Submitted to the University of Birmingham for The Degree of Doctor of Philosophy (Ph.D).
j
sebarang himpunan maksimal titik kritis dari A yang tidak ekuivalen. Demikian juga V ( A) { } V ( A) { jE* ( A) j g j ; j } dimana
g1 , g 2 , , g n
adalah kolom-kolom dari ( A ) dan E * ( A) adalah sebarang himpunan maksimal titik kritis dari A yang tidak ekuivalen. Oleh karena itu, V ( A) { } V ( A) { jE* ( A) j g j ; j I ()} ,
dengan j g j [ j g , j g j ] atau j
j g j [ j g j , j g *j y] .
■
Matriks A = [[,]] merupakan matriks tak tereduksi dan V(A) = V+(A) = I(). Untuk matriks tak tereduksi Ann untuk n > 1, menurut definisi dari matriks tak tereduksi bahwa i, j N, i j, sehingga bobot maksimum semua lintasan (i,j) tidak sama dengan [,]. Oleh karena itu, misalkan (A)ij elemen matriks (A), (A)ij [,],i, j dan V(A) = V+(A) {}. {( A ) z; z , z j [ , ], j E ( A)} . Kesimpulan
Dari hasil pembahasan dapat disimpulkan: n untuk setiap A I nmax jika m ( A) , g1, g2,, gn adalah kolom-kolom dari (A) dan V+(A) , maka V ( A) { jE* ( A) j g j ; j I ()} dimana E*(A) adalah suatu himpunan maksimal titik-titik n kritis dari A yang tidak ekuivalen. Jika A I () nmax matriks tak tereduksi, g1, g2,, gn adalah kolomkolom dari (A) maka V ( A) {jE * ( A) j g j ; j I ()} dan
V ( A) V ( A) { } {( A ) z; z , z j [ , ], j E ( A)}
.
