R menyatakan himpunan

Jurnal Barekeng Vol. 8 No. 2 Hal. 47 – 52 (2014)

MATRIKS PANGKAT DAN KEPERIODIKANNYA DALAM ALJABAR MAX-PLUS The Power of Matrices and its Periodic in the Max-Plus Algebra

VENN YAN ISHAK ILWARU Jurusan Matematika Fakultas MIPA Universitas Pattimura Jl. Ir. M. Putuhena, Kampus Unpatti, Poka-Ambon E-mail: [email protected]

ABSTRAK Dalam aljabar max-plus telah banyak dipelajari tentang sifat-sifat matriks.Salah satunya adalah keperiodikan suatu matriks yang tidak tereduksi. Telah diketahui pada aljabar maxk

plus bahwa barisan pangkat A dalam Aljabar Max-Plus, dengan A adalah matriks persegi yang tidak tereduksi, menjadiperiodiksetelahwaktuterbatasT(A), danperiodeakhir  samadengan siklisitas grafkritis dari A. Dalamhubunganini dipelajari masalah komputasi dari matriks persegi yang berukuran n n yaitu jika diberikan k, hitung periodik pangkat

Ar dengan r  k (mod  ) untuk r  T  A . Ide utama adalah menggunakan penskalaan similaritas diagonal yang sesuai A

X 1 AX , yang disebut penskalaan visualisasi.

Kata Kunci : Graf Kritis, Periodik Pangkat, Periodik akhir.

PENDAHULUAN

TINJAUAN PUSTAKA

Pada Aljabar max-plus banyak permasalahan yang muncul, sehingga permasalahan itu dapat diselesaikan dengan mendapatkan suatu solusi yang tepat.Dalam penyelesaiannya, dibutuhkan analisis atau dengan menggunakan komputasi.Aljabar max-plus sering digunakan untuk memodelkan suatu permasalahan seperti transportasi, manufacturing, penjadwalan, sistem antrian, lalu lintas dan sebagainya. Salah satu kegunaan dari pada aljabar max-plus yaitu dapat menyelesaikan dan mendapatkan suatu keperiodikan dari suatu permasalahan.Periodik yang dimaksud disini adalah periodik secara berkala.Untuk mempelajari periodik secara berkala, maka perlu dibahas visualisasi, dan perpangkatan matriks.Sehingga dapat membantu dalam menyelesaiakan dan mendapatkan suatu periodik secara berkala. Pada penelitian ini akan dibahas mengenai permasalahan yang diberikan oleh Sergei Sergeev (2009)

Pada penelitian-penelitian sebelumnya telah banyak dibahas mengenai matriks tidak tereduksi dan matriks boolean. Pada (Bart De Schutter dkk, 1998) telah diberikan mengenai definisi dari pada matriks tidak tereduksi dan matriks boolean. Pada (Martin Cavalec,1999) juga telah diberikan definisi mengenai keperiodikan suatu matriks. Berikut ini akan diberikan materi yang diperlukan dalam pengerjaan penelitian. Materi yang diperlukan yaitu aljabar max-plus, vektor dan matriks pada aljabar max-plus, masalah spektral pada aljabar max-plus dan teori Kleene star.

r

A dan mendapatkan perilaku periodik akhir dari A  x . yaitu menghitung periodik pangkat



l



def

def

Didefinisikan     dan e  0 . Himpunan Rmax adalah himpunan    , dimana  adalah himpunan bilangan riil. Definisi 1 Simbol Rmax menyatakan himpunan     dengan dua operasi biner yaitu maksimum yang dinotasikan dan penjumlahan yang dinotasikan  .



48

Barekeng Vol. 8 No. 2 Hal. 47 – 52 (2014)

Untuk setiap dan

a, b  Rmax , didefinikan operasi 

 adalah a  b  maks a, b  dan a  b  a  b .

a  Rmax dan  didapatkan a      a  a dan a      a   . Himpunan Rmax dengan operasi  dan  disebut

Sehingga untuk setiap

Aljabar

Max-plus

   Rmax , , ,  , e  .

dan

dinyatakan

dengan

bilangan riil yang berhingga sehingga x  p   x  q   c .

vektor p q

yang



 x  q  j  1 .

Algoritma Power (Subiono, 2000, hal. 86) 1) Ambil sebarang vektor awal x  0   x0  u   ,

x0 mempunyai minimal satu elemen

yaitu

berhingga. 2) Iterasi x  k  1  A  x  k  hingga ada bilangan

Komutatif

x, y  Rmax : x  y  y  x

bulat p, q dengan p  q  0 dan sebuah bilangan riil csehingga x  p   x  q   c , hingga suatu

dan

x y  yx Distributif  terhadap 

periodik didapatkan. 3) Hitung nilai eigen   c .

x, y, z  Rmax : x   y  z    x  y    x  z  Eksistensi elemen nol, yaitu 

pq

4) Hitung vektor eigen p q





v     p q  j   x  q  j  1 .

x  Rmax : x      x  x

e.



 p  q  j 

Dari teorema di atas, didapatkan Algoritma Power untuk menentukan nilai eigen dan vektor eigen.

x, y, z  Rmax : x   y  z    x  y   z

d.

eigen

v  

dan

c.

c dengan pq bersesuaian adalah

Maka nilai eigen dari sistem adalah  

j 1

Berikut adalah sifat-sifat Aljabar Max-plus (Heidergott dkk, 2006) sebagai berikut: a. Asosiatif x, y, z  Rmax : x   y  z    x  y   z ,

b.

sistem akan

bersifat periodik setelah iterasi yang berhingga. Misalkan p, q adalah bilangan bulat dengan p  q  0 dan c adalah

def

def

x  0   ,

dan jika diberikan nilai awal

j 1

Eksistensi elemen satuan , yaitu e

x  Rmax : x  e  e  x  x f.

Elemen nol adalah absorbing untuk operasi

g.

x  Rmax : x      x   Idempoten dari operasi  x  Rmax : x  x  x

Lemma 1 nn Misalkan A  Rmax

Untuk setiap



mempunyai nilai eigen 

A

yang

Proposisi 1 nn Diberikan A  Rmax terdefinisi dan X  diag  x  1) Jika x  2) Jika

pl



n i 1

A.*i maka X 1 AX adalah visualisasi

x   i 1 A.*i n

maka

X 1 AX

adalah

visualisasistrictly.

Teorema 1 nn Sebarang matriks tidak tereduksi A  Rmax mempunyai

satu dan hanya satu nilai eigen  . Nilai eigen  ini adalah bilangan berhingga dan nilainya sama dengan bobot rata-rata maksimum dari sirkuit pada G  A yaitu: pC  A

 A2  A, aii  1, i

star

Kondisi   A  1 menunjukan bahwa ada hubungan yang kuat antara kleene stars dan masalah spektral.

pw

  A  max

Kleene

 aij a jk  aik , aii  1, i, j, k

berhingga, maka ada sebuah sirkuit p di G  A sehingga 

adalah

A  Rnn

pw

.

pl

Teorema 2 Misalkan sistem x  k  1  A  x  k  memenuhi asumsi

Proposisi 2 nn Diberikan A  Rmax terdefinisi dan diberikan sedemikian

sehingga

sedemikian sehingga

t  n . 2

Diberikan

i  l  j  , l   ,

t 0 i, j  c

mengakibatkan

 j  s i  , dimana l  s   . 1) Jika A divisualisasikan maka aijt l   ajit  s   1 2) Pada kasus umum aijt l  ajit  s   1

dasar bahwa sistem mempunyai nilai eigen yang tunggal Ilwaru

49

Barekeng Vol. 8 No. 2 Hal. 47 – 52 (2014)

HASIL DAN PEMBAHASAN Proyektor Spektral dan Matriks Periodesitas nn Untuk matriks A  Rmax yang tidak tereduksi dan

terdefinisi, sesuai dengan matriks Q  A dengan elemenelemen: c

qij   a a , i, j  1,..., nc * * ik kj

k 1

Operator

max-plus

linear

Q  A

Ar menjadi periodik untuk

Baris dan kolom kritis dari

r  n2 . Bukti Diberikan

(1)

matriks

Proposisi 3. nn Diberikan A  Rmax yang tidak tereduksi dan terdefinisi.

i  c , maka terdapat sirkuit kritis dari panjang li . Oleh karena itu aii kl   1 untuk k  1 . Untuk semua m  k dan beberapa t  1,..., n , maka diperoleh: i

adalah

proyektor spektral max-plus linear yang berkaitan dengan n A, dalam arti bahwa Rmax pada eigencone V  A . Operator ini sangat berkaitan dengan masalah periodisitas. Q  A disebut juga matriks orbital.

ais

mli 

 aii

 k mli   mli 

 ais i  kl

ais

Selanjutnya k

ais i    ais kl

mli 

m 1

.

(2)

 kl 

Definisi 2. nn nn Diberikan matriks A  Rmax , Q  Rmax yang memenuhi

AQ  QA  Q2 disebut spektral proyektor dari A yang berhubungan dengan nilai eigen

.

nn Jika diberikan A  Rmax yang tidak tereduksi dan

terdefinisi dan diberikan C  A adalah primitive, maka

Elemen-elemen ais i merupakan bobot maksimal dari path dengan panjang k yang bersesuaian dengan matriks

Ali . Karena bobot dari semua sirkuit adalah kurang dari atau sama dengan 1 dan semua path dari panjang n tidak sederhana. Maksimum dicapai pada saat k  n . Maka t 1l   tl  diperoleh bahwa ais i  ais i untuk semua t  n . Lebih lanjut

ais

 t 1li  d 

terdapat bilangan bulat T  A  sehingga Ar  Q  A , untuk semua r  T  A .

t 1li  d 

nn Untuk matriks A  Rmax yang tidak tereduksi dan

terdefinisi, setiap kolom kritis (atau baris) dari Q  A

adalah sama dengan korenspondensi kolom (atau baris) dari

A* . Ketika

C  A

mempunyai

imprimitive, sesuai dengan proposisi

bahwa semua

adalah siklisitas dari C  A . Oleh karena itu, untuk setiap r yang cukup besar adalah kelipatan dari  , A adalah matriks dari proyektor spektral dalam eigencone r

A . Ini juga mengakibatkan bahwa untuk r yang r r  cukup besar, mempunyai A  A . Jumlah r setelah r dimulai disebut transient dari  A  dan dinotasikan dari

dengan T  A . Juga diketahui bahwa akhir dari

A  r

r 

sehingga A r 

aij



tl

d

p

tli  d 

 ais

untuk semua

t  n dan

0  d  li  1 . Sehingga ais k  periodik untuk k  nli dan semua urutannya untuk setiap i  c dan setiap s, 2 menjadi periodik untuk k  n ■

komponen

C  A  adalah primitive, dimana 

komponen dari

Selanjutnya ais

  aip i  aps 

adalah periode

yakni sedikitnya bilangan bulat



 Ar untuk semua r  T  A . Elemen

, dimana i atau j adalah kritis, menjadi periodik jauh

lebih cepat dari bagian non kritis dari A.

Proposisi 4. nn Diberikan matriks A  Rmax yang tidak tereduksi dan

t  0 sehingga t  T  A . Maka untuk setiap bilangan bulat l  0 terdefinisi dan c

akt. l    akit  Ai.t l  i 1

Ar

c

, a.kt l    aikt  A.it l  , i 1

(3)

1 k  n Bukti Untuk

B  A dan setiap t  T  B  diperoleh c

bkj    bki* bij* , 1  k , j  n r

i 1

Berikut ini adalah proposisi untuk menentukan keperiodikan baris kritis dan kolom kritis dari matriks

Sifat-sifat Periodik Perpangkatan Matriks Periodik pangkat dari matriks yang tidak tereduksi dan terdefinisi dijelaskan dengan proposisi-proposisi berikut.

(4)

Dengan demikian diperoleh

bki*  bki   aki

t 

t

dan

bij*  bij   aij t

t 

Ilwaru

50

Barekeng Vol. 8 No. 2 Hal. 47 – 52 (2014)

untuk

t  T  B  atau

semua

ekuivalen

dengan

t  T  A dan setiap i  c . Oleh karena itu c

t

t

(5)

i 1

Pada notasi matriks, persamaan di atas ekuivalen dengan c

c

Akt.   aki  Ait. , A.tk   aik  A.ti , 1  k  n t

i 1

t

(6)

i 1

Al akan

Perkalian persamaan (6) dengan matriks pangkat diperoleh persamaan (3) ■

Pada pembuktian proposisi berikut akan digunakan prinsip sederhana berikut ini:

aij  ajk  aik r

r s

s

, i, j, k , r , s

Proposisi 5. Diberikan matriks

(7)

nn max

yang tidak tereduksi dan A R dan diberikan i, j  Nc  A sedemikian

terdefinisisi

sehingga i  l  j  , untuk 0  1   .

r  n2

1) Terdapat t sedemikian sehingga untuk setiap  t  l  r  t  l  r r l r l

A.i  A. j , aij

aij

Aj.  Ai.

(8)

r  n2 A.ri  A.rjl , Arj .  Air. l

(9)

s    l . Dengan proposisi 2, terdapat t

aij

t  l 

sedemikian sehingga

aji

t  s 

 1. Jika digabungkan

t  l 

Arj .  Arj .aij

aji

t  l 

t  s 

t  s 

a ji

t  s 

 A.rjt l a ji

 A.i

 Air. t l a ji

 Aj . 

t  s 

(10)

r  2t 1

semua t  0 dan r  n2 maka semua ketidaksamaan pada persamaan (8) menjadi persamaan. Perkaliannya dengan t  l aij  diperoleh persamaan

A.ri  A.rjl , Arj .  Air. l

■

C R

atau sebaliknya

l 

nc max

R R

matriks yang diekstrak dari klom kritis dari sebaliknya  0

dari

baris

 0

kritis

t  l

A

.

menjadi t  l

A

atau

Diberikan

C : C , R : R . Dengan notasi ini dan dari proposisi 4 dan proposisi 5, maka dapat disimpulkan bahwa untuk visualisasi matriks tidak tereduksi nn A  Rmax

l

C

C

l

l

(12)

Persamaan (11) setara dengan persamaan (3). Lebih lanjut i  l  j  jika dan hanya jika terdapat indeks p  i  dan s   j  sedemikian sehingga elemen

 A   C

l

 p, s 

dari

adalah 1, dan semua baris dari R atau kolom dari

C, dengan indeks yang sama dengan kelas siklik adalah sama satu sama lain . Dengan menggabungkan persamaan (11) dan persamaan (12) maka diperoleh

  R

At l  C  A

C

l

(13)

Jika A tidak tervisualisasi tetapi terdefinisi tidak tereduksi, maka persamaan (12) dan persamaan (13) dapat 1 dituliskan. Diberikan B  X AX tervisualisasi. Dengan menerapkan penskalaan invers XBX 1 pada persamaan (13) (dimana B digantikan dengan A) maka diperoleh persamaan dari bentuk yang sama, dimana C dan R adalah matriks yang diekstrak dari kolom kritis atau

At dan AC  digantikan dengan

sebaliknya baris dari

 

 a , C aij    ij  0

jika  i, j   Ec  A ,

jika  i, j   Ec  A ,

i, j  c

Penyelesaian Masalah Keperiodikan nn Diberikan A  Rmax dan   A  1 . t-attraction cone Attr  A, t  adalah maxcone yang terdiri dari semua

semua bilangan bulat yang lebih besar atau sama dengan r. Proposisi 6 Diberikan matriks A tidak tereduksi dan terdefinisi. Sistem

Ar  x  Ar t  x

setara

r  T  A .

dengan

semua

Bukti

Diambil t  T  A . Untuk setiap l  0 , diberikan nc max

   , R    A    R

Ar  x  Ar t  x dan hal ini juga berlaku untuk

r   2t 1

Dengan proposisi 2 , A.ri  A.rjt dan Arj .  Air. t untuk

l 

(11)

vektor x, dimana terdapat bilangan bulat r sehingga

dengan persamaan (7) maka diperoleh

A.ri  A.ri aij

l

cc matriks AC   aijC   Rmax yang didefinisikan dengan

2) Jika matriks A adalah visualisasi maka untuk semua

Bukti Diberikan

l

C l   C  A

akj    aki  aij  , 1  k , j  n t

At l  C    R  C  R 

Diberikan x yang memenuhi

As  x  As t  x untuk

s  T  A , maka juga akan memenuhi sistem ini untuk

semua yang lebih besar dari s. Karena periodisitas untuk semua k dari T  A  k  s terdapat l  s sehingga

Ak  Al . Ak  x  Ak t  x

juga memenuhi T  A  k  s

■

Akibat 1. Attr  A, t   Attr At ,1



 Ilwaru

51

Barekeng Vol. 8 No. 2 Hal. 47 – 52 (2014)

Bukti Dengan proposisi 5, Attr  A, t  adalah solusi untuk

Ar  x  Ar t  x untuk setiap r  T  A

sistem

yang adalah kelipatan dari t ■ Komponen

dari

r t

A x  A r

 x dengan

Nc  A  1,..., c disebut kritis dan

indeks pada

subsistem dari komponen-komponen dengan indeks ini disebut subsistem kritis. Lemma 2. Diberikan matriks A tidak tereduksi dan terdefinisi dan diberikan r  T  A . Maka

Ar  x  Ar t  x setara

dengan subsistem kritis.

c

r  ki

i 1

c

submatriks non kritis dari

Air.  x  aki  Air. t  x r

(14)

i 1

Hal ini merupakan kombinasi maksimum dari persamaan pada subsistem kritis ■ Berikutnya diberikan batasan dalam menghitung kompleksitas dalam memutuskan apakah x  Attr  A, t  , seperti masalah-masalah yang lain yang dapat diformulasikan seperti di bawah ini: P1. Diberikan x, uji apakah x  Attr  A, t 

0  k   , hitung periodik matriks pangkat A dimana r  k  mod   .

P2. Diberikan x:

penyelesaian untuk P2. Baris non kritis dari matriks A merupakan generalisasi dari baris kritis, periodik akhir dari Ar  x ditentukan dari komponen-konponen kritis.



A

r

bulat

x,

hitung

periodik

akhir

dari

 x, r  0 , yang berarti sedikitnya bilangan



sedemikian sehingga

Ar   x  Ar  x

untuk semua r  T  A .

untuk semua

A

r

subeigen dapat dihitung dan mengidentifikasi semua titik kritis yang dilakukan dengan algoritma FloydWarshall.Selanjutnya mengidentifikasi semua kelas siklik C  A dengan kondensasi Balcer-Veinott. Dengan proposisi 4, kolom kritis dan baris kritis menjadi periodik kritis

r  n2 . Dengan mengetahui kolom kritis dan baris pada

r '  T  A , itu sudah cukup untuk

Ar untuk r  n2 , yang dapat diselesaikan 2 4 dengan perpangkatan matriks persegi A, A , A ,... . menghitung

i, j sehingga

 x    Ar t  x  untuk i

j

i  t  j  . Ini i  t  j  , artinya

berarti bahwa

untuk menentukan periode dibutuhkan hanya sub vektor

Ar  x untuk setiap sembarang r  n2 . Untuk

i  c dan

r  n2 ,

barisan

 A  x  , t  0 r

dapat

i

direpresentasikan dengan barisan dari koordinat kritis dari

Ar  x yang ditentukan oleh suatu permutasi pada kelas siklik   dari komponen strongly connected. Untuk menghitung periode, dapat diambil contoh banyaknya   secara berurutan pada barisan dan periksa semua periodeperiode yang mungkin. Periode dari A  x akan tampak seperti l.c.m. pada periode ini. Ini adalah penyelesaian P3. r

KESIMPULAN Kesimpulan yang dapat diperoleh dari penelitian ini adalah sebagai berikut: nn 1) Jika diberikan matriks A  Rmax yang tidak

2)

tereduksi dan tervisualisasi maka baris kritis dan kolom kritis akan menjadi periodik utuk r  n2 . Keperiodikan dari perpangkatan matriks persegi Ar , dapat dihitung untuk r  T  A dan jika k diketahui.

DAFTAR PUSTAKA

Untuk menyelesaikan P1-P3, maka dapat menggunakan metode sebagai berikut: Pertama-tama perhatikan bahwa   A dan vektor

untuk



Untuk visualisasi matriks, diketahui bahwa Air. t  Arj .

r

P3. Diberikan

Ar , untuk setiap r  T  A

sehingga r  k  mod   dapat dihitung. Ini adalah

dari

Bukti Berdasarkan komponen non kritis Akr.  x  Akr.t  x . Dengan menggunakan persamaan (3) maka dapat dituliskan:

a

verifikasi dari subsistem kritis dari Ar '  x  Ar 't  x . Dengan menggunakan bantuan persamaan (3), sisa





Persamaan (9) digunakan untuk permutasi siklik yang sesuai dengan kelas siklik. P1 dapat diselesaikan dengan

Bacelli, F., Cohen, G., Olsder, G. J., dan Quadrat, J. P. (2001), Synchronization and Linearity, John Wiley & Sons, New York. Papadimitriou, C. H., Steiglitz, K., Combinatorial Optimization: “Algorithms and Complexity”, Prentice Hall, New Jersey, 1982 Heidergott, B. (2006), Max Plus Algebra And Queues, Vrije Universiteit. Department of Econometrics and Operations Research De Boolean 1105, 1081 HV Amsterdam, The Netherlands. Gavalec, M., “Linear Matrix Period in Max-Plus Algebra”, Linear Algebra Appl. 307(2000) 167-182 Butkovic, P., Cuninghame-Green, R. A., “On matrix powers in max-algebra”, Linear Algebra Appl. Subiono. (2009), Aljabar Max-Plus, Institut Teknologi Sepuluh Nopember, Surabaya Ilwaru

Barekeng Vol. 8 No. 2 Hal. 47 – 52 (2014)

52

Sergeev, S., Schneider, H., Butkovic, P. (2009) “On visualization scaling, subeigenvectors and kleene stars in max algebra”, Linear Algebra Appl.

Ilwaru