## Sifat-sifat Nilai Eigen dan Vektor Eigen Matriks atas Aljabar Maxplus

## (The Properties of Eigen Value and Eigen Vector of Matrices
Over Maxplus Algebra)
Musthofa * dan Nikenasih Binatari ♣
* Jurusan Pendidikan Matematika FMIPA UNY / email: musthofa@uny.ac.id
♣ Jurusan Pendidikan Matematika FMIPA UNY / email: nikenasih@yahoo.com

## Abstrak
Penelitian ini bertujuan untuk mengkaji sifat-sifat  nilai eigen dan vektor eigen matriks atas aljabar maxplus.  Langkah-langkah  yang  dilakukan  adalah  dengan  mengkaji  eksistensi  nilai  eigen  dan  vector eigen matriks atas aljabar maxplus. Selanjutnya diselidiki sifat-sifat nilai eigen dan vector eigen, meliputi ketunggalan  dari  nilai  eigen,  dan  mengkaji  tentang  sifat  nilai  eigen  dan  vector  eigen  dari  matriks transpose.  Hasil  penelitian  menunjukkan  bahwa  setiap  matriks  persegi  atas  aljabar  maxplus  selalu mempunyai nilai eigen. Suatu mariks persegi A atas aljabar mxplus akan mempunyai nilai eigen tunggal jika A irredusibel. Jika   merupakan nilai eigen A , maka   jug merupakan nilai eigen dari A T . Tetapi sifat ini tidak berlaku untuk vektor eigennya.
Kata kunci: aljabar maxplus, nilai eigen, vektor eigen, matriks transpose

## Abstract
This  research  aimed  to  study the  properties  of  eigenvalues  and  eigenvectors  of the matrix  over maxplus algebra. The initial step is to study the existence of eigenvalues and eigenvector of matrix over maxplus algebra. Moreover, the properties of eigenvalues and eigenvectors are investigated. Finally, we study the properties of eigenvalues and eigenvectors of the matrix transpose. The result shows that every square matrix over maxplus algebra always has eigenvalue. A square matrix A in the maxplus algebra will have a unique eigenvalue if A is  irreducible. If   is an eigenvalue of A , then   is also an eigenvalue of A T , but this property does not apply for the eigenvector.
Key words: maxplus algebra, eigenvalue, eigenvector, matrix transpose

## Pendahuluan
Seiring  dengan  perkembangan  ilmu pengetahuan  dan  teknologi,  para  peneliti dituntut  untuk  terus  melakukan  inovasi  dan usaha  yang  terus  berkesinambungan  dalam menghadapi persaingan dan untuk mewujudkan  kesejahteraan  umat  manusia. Kemajuan  pesat  dalam  teknologi  informasi tidak  lepas  dari  perkembangan  riset  dalam bidang ilmu dasar. Oleh karena itu peneltian di bidang ilmu dasar tidak bisa ditinggalkan.
Aljabar  maxplus  merupakan  salah satu  bagian  dari  ilmu  dasar  dalam  bidang matematika khususnya aljabar yang memiliki peranan
sangat
banyak dalam
menyelesaikan persoalan di beberapa bidang  seperti  teori  graf,  kombinatorika (seperti  dibahas  dalam  [2]),  teori  sistem (dibahas  dalam  [5]  dan  [7]),  teori  antrian (dibahas dalam [4]) dan proses stokastik(dibahas dalam [3]). Hal ini disebabkan aljabar max-plus mampu menguraikan  suatu  tipe  tertentu  dari  sistem nonlinear  dalam  sudut  pandang  aljabar linear  menjadi  sistem    linear  dalam  sudut pandang  aljabar  max-plus.  Kelinieran  ini akan  memudahkan  dalam  penganalisaan sistem yang dikaji.
Berkaitan  dengan  masalah  tersebut matriks  dan  nilai  eigen  merupakan  salah satu  alat  matematis  untuk  menyelesaikan berbagai  masalah  dalam  bidang  tersebut. Pembahasan  tentang  nilai  eigen  dan  vektor eigen  dalam  dari  suatu  matriks  relative terhadap  suatu  struktur  aljabar  merupakan bagian  yang  tidak  bisa  ditinggalkan.  Oleh sebab  itu,  melalui  penelitian  diinginkan kajian  yang  mendalam  tentang  nilai  eigen dan vektor eigen pada aljabar max-plus yang memiliki aplikasi di berbagai bidang keilmuan.
Dalam aljabar linear dan aplikasinya, nilai  eigen  dan  vektor  eigen  memiliki peranan  penting  salah  satunya  dalam menganalisis  suatu  sistem.  Tidak  adanya invers  terhadap  operasi  pertama  dalam aljabar  max-plus,  mengakibatkan  kesulitan ketika  akan  menerapkan  metode –metode yang  sudah  dikenal  dalam  aljabar  linear seperti  misalnya  untuk  menentukan  solusi persamaan Ax = b .  Beberapa  peneliti  di bidang  aljabar  max-plus,  seperti  dalam  [1] dan  [2]  telah  ditunjukkan  eksistensi  dan metode  untuk  menentukan  nilai  eigen  dan vektor  eigen  dari  suatu  matriks  atas  aljabar max-plus.
Berberapa  hal  yang  cukup  menarik untuk diteliti antara lain metode menentukan nilai  eigen  dan  vektor  eigen    pada  matriks atas  aljabar  max-plus  serta  sifat-sifat  nilai eigen  dan  vektor  eigen  seperti  halnya  pada aljabar  linear  yang  sudah  dikenal.  Sejauh yang  kami  ketahui,  belum  diteliti  masalah sifat – sifat nilai eigen dan vektor eigen pada aljabar max-plus, misalnya jika   merupakan nilai eigen A , apakah   juga merupakan nilai eigen  dari A T ?  Berdasarkan  hasil-hasil tersebut,  dalam  penelitian  ini  akan  diselidiki tentang sifat –sifat lebih lanjut dari nilai eigen dan  vektor  eigen  dari  matriks    atas  aljabar max-plus.

## Metode Penelitian
Penelitian ini dilakukan model research and development . Peneliti mengkaji berbagai sumber tentang masalah nilai eigen dan  vector  eigen  ada  aljabar  maxplus, membandingkan dengan kondisi yang terjadi pada ruang vektor dan kemudian melakukan
pengembangan  untuk  diterapkan pada aljabar  maxplus. Alat bantu  yang digunakan dalam  penelitian  ini  adalah  perangkat  lunak Scilab 5.3.

## Hasil dan Diskusi

## 1. Aljabar Maxplus
Aljabar  maxplus  adalah  himpunan R {- },  dengan R menyatakan  himpunan semua bilangan real yang dilengkapi dengan operasi    maksimum,  dinotasikan  dengan dan  operasi  penjumlahan,  yang  dinotasikan dengan .  Selanjutnya  ( R {- }, , ) dinotasikan dengan R max dan {- }
dinotasikan dengan  . Elemen merupakan elemen  netral  terhadap  operasi dan  0 merupakan    elemen  identitas  terhadap operasi  .  Struktur  aljabar  dari R max adalah semifield, yaitu :
1.  ( R {- },   ) merupakan semigrup komutatif dengan elemen netral {- }
2.  ( R {- }, )  merupakan  grup komutatif dengan elemen identitas 0
3.  Operasi   dan   bersifat distributif 4.  Elemen  netral  bersifat  menyerap terhadap operasi   , yaitu a R max , a = a =

## 2. Matriks atas R max
Dalam  aljabar  linear,  jika F field, maka dapat dibentuk suatu matriks berukuran m × n dengan entri –entrinya adalah  elemen –elemen F .  Hal  yang  serupa dapat  dikerjakan  pada R max ,  yaitu  dapat dibentuk matriks A berukuran m × n dengan entri-entrinya elemen R max .
Operasi dan    pada  matriks  atas aljabar maxplus didefinisikan sebagai berikut: (1) ( ) ij ij ij A B A B (2) ( ) ( ) ij ik kj k A B A B Contoh:
Jika 1    2 -2  3 A dan -2    7 1     -3 B , maka
1    2 -2    7 1 -2   2 7 1    7 -2  3 1    -3 -2 1   3 3 1    3
A B
dan {1+(-2)} {2 1}     {1+7} {2 ( 3)} 3    8 {-2+(-2)} {3 1}    {-2+7} {3 ( 3)} 4    5 A B
Jika ( R max ) n × n menyatakan himpunan semua matriks  dengan entri-entrinya elemen R max, , maka matriks E dengan 0,  jika ( ) ,  jika ij i j
E i j dan  matriks    dengan
( ) ij =  , i , j berturut –  turut  merupakan matriks identitas  dan matriks nol. Jadi ,
(1)  ( E A ) = ( A E ) = A untuk setiap A ( R max ) n × n ; (2)  ( A ) = ( A ) = A , untuk setiap A ( R max ) n × n .
Perlu  diperhatikan  bahwa  ( R max ) n × n bukan merupakan  semifield,  tetapi  merupakan semiring,  sebab  terhadap  operasi ( R max ) n × n tidak  komutatif  dan  tidak  setiap A ( R max ) n × n mempunyai invers .
1.  Nilai  Eigen  dan  Vektor  Eigen  Matriks atas Aljabar Max-plus
Konsep  nilai  nilai  eigen  dan  vector eigen  dalam  aljabar  maxplus  tidak  berbeda dengan  konsep  yang  telah  dikenal  dalam aljabar  linear.  Namun  untuk  mencari  nilai eigen  dan  vector  eigen  terdapat  sedikit perbedaan.  Metode untuk menentukan nilai eigen dan vector eigen suatu matriks persegi atas  aljabar  maxplus  antara  lain  terdapat dalam  Andy  Rudhito  (  2003)  dan  Subiono (2010).
Definisi  1(  Rudhito,  2003) . Misalkan  A matriks  pesegi  atas  R max .  Skalar disebut nilai eigen dari  matriks A  jika terdapat suatu vektor v sehingga A v = v.
Selanjutnya vektor v tersebut
disebut
vektor eigen A yang bersesuaian dengan  .
Contoh  2    (  Subiono,  2010) .Diberikan matriks
0 2 6 6 8 0 2 5 4 8 3 maka , 5 4 8 3 A . 2.
Terlihat bahwa nilai-karakteristik dari matriks A adalah 6 dan vektor karakteristiknya adalah
0 2 .
Selanjutnya  untuk  menentukan  nilai  eigen tersebut,  terlebih  dahulu  dibahas  tentang graf, khususnya graf berarah.
Definisi  3.  (  Rudhito,  2003) Suatu  graf berarah  didefinisikan  sebagai  pasangan  (V, A)  dengan  V  adalah  suatu  himpunan berhingga  tak  kosong    yang  anggotanya disebut  titik  (vertices)  dan  A  adalah  suatu himpunan    pasangan  teurut  titik-titik  yang disebut dengan busur(arc).
Berikut  beberapa  definisi  penting  yang berkaitan dengan graf :
Definisi 4(Subiono, 2010) Diberikan G = ( V, A ).
(i) Suatu lintasan dalam G adalah suatu barisan berhingga busur ( i 1 , i 2 ),  ( i 2 , i 3 ),  …,  ( i l-1 , i l )    dengan  ( i k , i k+1 ) A .
(ii) Untuk  suatu  lintasan  , panjang lintasan didefinisikan  sebagai banyak  busur  yang  menyusun  , dinotasikan dengan (iii) Suatu sirkuit adalah suatu lintasan  dengan    titik  awal  dan titik akhirnya sama.
(iv) Sirkuit  elementer adalah  suatu sirkuit yang mana setiap titik yang muncul  tidak  lebih  dari  sekali kecuali  titik  awal  yang  muncul tepat dua kali.
Selanjutnya berkaitan dengan matriks, selalu dapat  dikaitkan  dengan  suatu  graf  berarah berbobot sebagai berikut :
Definisi  5(Subono,  2010)) Jika  A  matriks persegi  atas  aljabar  maxplus,  maka  Graf
Preseden  dari A adalah graf berarah berbobot G ( A ) = ( V, A ) dengan V = { 1, 2, ... , n } dan A  = {( j, i ) | w ( i, j ) = A ij }.
Contoh 6.
Diberikan 2 4 1 5 6 1 A
Graf preseden dari A adalah graf berarah berbobot G ( A ) = ( V, A )  dengan V = { 1, 2, 3 } dan A = {( 1, 1 ), ( 2, 1 ), ( 3, 1 ), ( 2, 2 ), ( 3, 2 ),  ( 2,  3 )}  yang  disajikan  dalam  gambar berikut:
Gambar 1. Graf berarah berbobot G ( A )
Dalam  Rudhito(2003)  telah  dibahas bahwa  untuk  mencari  bobot  maksimum dari  semua  sirkuit  dengan  panjang k dengan  titik i sebagai  titik  awal  dan  titik akhir  dalam G ( A )    adalah  dengan menghitung ( ) . k ii A Sedangkan  untuk
mengitung bobot bobot rata-rata
maksimum  sirkuit  elementer  dalam G ( A ) (dinotasikan dengan max ( )) A adalah dengan menghitung :
k k A
k A trace 1 ) ( 1 m ax dengan ii k k k A A ) ( trace .
Berkaitan  dengan  nilai  eigen,  berikut beberapa  teorema  yang  dapat  dijumpai dalam Bacelli(2001).
Teorema 7. ( Bacelli, 2001)
Diberikan A n n R m ax . Jika semua sirkuit dalam G(A) mempunyai bobot non positif, maka
n p A A A E A n p , ... 1 2 Berdasarkan teorema diatas,
didefinisikan  matriks  A * dan  A + seperti  di bawah ini :

## Definisi 8 ( Bacelli, 2001)
Diberikan A n n R m ax dengan  semua  sirkuit dalam G ( A ) mempunyai bobot nonpositif .
Didefinisikan dua matriks A * dan A + sebagai berikut :
* 1 : ... ... n n A E A A A dan
* : . A A A
Selanjutnya,  untuk  mencari  nilai  eigen  dari matriks A digunakan  teorema  berikut  yang dapat dijumpai dalam Rudhito(2003) :
Teorema  9.  (Rudhito,  2003) Diberikan  A matriks  persegi  atas  aljabar  maxplus. Jika skalar , merupakan  nilai  eigen A,  maka merupakan  bobot  rata-rata  suatu  sirkuit dalam G ( A ) .
Contoh 10.
Diberikan matriks 5 5 6 3 6 6 3 A . Diperoleh 2
11 11 10
9 12 9 11 12 11
A dan 3 16 17 16 15 18 15 17 18 16
A Selanjutnya  diperoleh
trace A =  max(5,6,3)=5;  trace A 2 = max(11,12,11)
=12; trace A 3
= max(16,18,16)  =  18.  Jadi, max (A)  =
)) 18 ( 3 1 ), 12 ( 2 1 ), 6 (
1 1
max( =max(6,6,6) = 6.
Selanjutnya dapat dilihat bahwa 6
merupakan nilai eigen dari A , sebab: 2 2 1 6 2 2 1 3 6 6 3 6 5 5

## 1. Eksistensi Nilai Eigen
Dalam  aljabar  linear,  telah  dibahas bahwa tidak setiap matriks persegi mempunyai  nilai  eigen.  Namun,  dalam aljabar  maxplus,  setiap    matriks  persegi dijamin  mempunyai  nilai  eigen.  Hal  ini dibahas  dalam  teorema  berikut  yang  mana pembuktiannya ada dalam Rudhito(2003)

## Teorema 11. (Rudhito, 2003)
Diberikan A matriks persegi berukuran n n atas  aljabar  maxplus. Skalar max ( A ), yaitu bobot  rata-rata  maksimum  sirkuit  elementer d alam  G ( A ), merupakan  suatu  nilai  eigen matriks A.
Contoh 12.
1.  Matriks
5 0 0 mempunyai  2  nilai eigen, yaitu 0 dan 5, sebab
5 0 0 0 =    0 0 dan 5 0 0 5 0 = 5 5 0 2.  Matriks 4 3 2 1 nilai  eigennya  4, yaitu 4 3 2 1 2 0 =  4 2 0 .    Namun,
vector  eigen  dari  matrik  tersebut tidaklah tunggal, sebab
4 3 2 1 3 1 = 4 3 1

## 2. Ketunggalan
Berdasarkan  contoh-contoh  di  atas,  pada bagian ini akan dibahas tentang syarat suatu
matriks  atas  aljabar  maxplus  mempunyai nilai  eigen  yang  tunggal.  Suatu  matrik  atas aljabar maxplus dinamakan matriks irredusibel  jika G ( A )  terhubung  kuat.  Berikut sifat  matriks  irredusibel  yang  telah  dibahas dalam Bacelli ( 2001) dan Rudhito(2003).
Teorema  13.  (Rudhito,  2003) Jika  matriks irredusibel  A berukuran  n  x  n  atas  aljabar maxplus mempunyai  nilai  eigen    dengan x vektor eigen aljabar max-plus yang bersesuaian  dengan ,  maka       x i ≠ ɛ untuk setiap i {1, 2, ..., n } .
Bukti:
Misalkan terdapat dengan tunggal s {1, 2, ..., n } sehingga x s ≠  Akibatnya ( A x ) s = x s = atau A s,i x i = untuk setiap i {1, 2, ..., n }. Karena x i ≠  untuk setiap i  s , maka A s,i = . Hal ini berarti tidak ada busur dari setiap titik i s ke titik s . Akibatnya G ( A ) tidak terhubung kuat atau A tidak irredusibel. Jika terdapat lebih dari satu komponen yang sama  dengan ,  bukti  seperti  di  atas sehingga akan diperoleh kesimpulan A tidak irredusibel . Matriks irredusibel mempunyai  nilai eigen  aljabar  max-plus  tunggal    seperti diberikan  dalam  teorema  berikut  yang  telah dibahas dalam Bacelli(2001)
dan Rudhito(2003).

## Teorema 14.(Rudhito, 2003)
Jika  A  merupakan  matriks atas  aljabar maxplus  yang irredusibel,  maka  A mempunyai nilai eigen tunggal.
Bukti: .
Misalkan adalah  sebarang    nilai  eigen aljabar  max-plus  matriks A dengan x adalah  vektor  eigen  aljabar  max-plus yang  bersesuaian  dengan  .  Karena A irredusibel  maka x i untuk  setiap  i {1,  2,  ..., n }.  Diambil  sebarang  sirkuit  , misalkan sirkuit adalah  ( i 1 , i 2 ), ( i 2 , i 3 ) , ... , ( i p , i 1 ) dalam G ( A ).
Karena adalah  nilai eigen aljabar max- plus matriks A , maka
2 1 1 2 1 1 1 1 , , , , , . p p p p p p i i i i i i i i i i i i A x x A x x A x x Didapat  bahwa lebih  besar  atau
sama  dengan  rata-rata  bobot ,  untuk setiap  sirkuit
dalam G ( A ).  Jadi
max ( A ),  yang  berarti  nilai  eigen aljabar max-plus matriks A tunggal.

## 1. Nilai  Eigen  dan  Vektor  Eigen Matriks Transpos
Pada  bagian  ini  akan  dikaji  nilai  eigen  dari matriks transpose.
Teorema  15. Jika    merupakan  nilai  eigen matriks atas aljabar maxplus A, maka   juga merupakan nilai eigen dari matriks B = A T
Bukti :
Misal A merupakan nilai eigen matriks A dan B merupakan nilai eigen dari B = A T .
Karena
ii k ii k B A , maka  trace A k = trace B k . Akibatnya
A = k k A k A trace 1 ) ( 1 m ax = B k k B B k ) ( trace 1 m ax 1 .

## Contoh 16.
Dalam contoh sebelumnya nilai eigen dari
4 3 2 1 adalah  4 dan nilai eigen dari transposenya, yaitu 4 2 3 1
juga 4, sebab:
4 2 3 1 2 1 = 4 2 1 . Dari contoh ini
dapat dilihat bahwa A dan A T mempunyai nilai eigen yang sama.  Dari contoh ini pula,
dapat dilihat bahwa 2 1 bukan merupakan
vektor eigen dari 4 3 2 1
. Artinya walaupun
A dan A T mempunyai nilai eigen yang sama, tetapi vektor eigennya berlainan.
Kesimpulan mengungkapkan hal yang  lebih  tinggi  atau  luas  dari  diskusi. Hendaknya  dalam  bagian  ini  terkandung penarikan kesimpulan dan perampatan yang meluas,  serta  pencetusan  teori,  konsep, prinsip baru secara mapan daripada kesimpulan dangkal dan saran yang menyatakan penelitian perlu dilanjutkan.

## Kesimpulan
1.    Untuk  menentukan  nilai  eigen  suatu matriks  atas  aljabar  maxplus A dapat dilakukan dengan menghitung
k n k A k trace 1 1
2.  Setiap  matriks  persegi  atas  aljabar maxplus selalu mempunyai nilai eigen.
3. Jika matriks A irredusibel ( graf preseden dari A strongly  connected ),  maka A mempunyai nilai eigen tunggal, tetapi vektor eigennya belum tentu tunggal
4. Nilai eigen dari matriks transpose A sama dengan  nilai  eigen  matriks A ,  tetapi  vector eigennya belum tentu sama.

## Ucapan Terima Kasih
Tim  Peneliti  mengucapkan  terimakasih kepada  Universitas  Negeri  Yogyakarta, khususnya  Fakultas  MIPA  yang  telah mendanai kegiatan penelitian ini.

## Pustaka
[1]  Bacelli,  F. et.al .  2001. Synchronization and  Linearity. New York: John Wiley & Sons
[2] Butkovic,  p.  2002. Max-algebra:  the linear  algebra  of  combinatoric.  Science Direct,  Journal  of  algebra  and  its application.
[3] Flemming,W.H, 2004. Max-Plus Stochastic Processes. Applied Mathemamatic Optimization. New York :
Springer-Verlag
[4]    Heidergot,  B.  2000.  A  Characterization of  (max,+)-linear  queueing  system. Queueing System .2359(2000) 237-262.
[5]  Menguy,  E.  2000.  A  fist  Step  Towards Adaptive  Control  for  Linear  System  in
Max  Algebra. Discrete  Event  Dynamic System: Theory and Application. Boston: KluwerAcademic Publisher.
[6]  Rudhito,  M.  A.  2003.  Sistem  Persamaan Linear  Maxplus  Waktu  Invarian.  Tesis: UGM.
[7] Subiono.  2010. Aljabar  max-plus  dan terapannya. Artikel  tidak  diterbitkan.