BAB II LANDASAN TEORI Pada bab ini dibahas penelitian-penelitian tentang aljabar maks-plus yang telah dilakukan dan teori-teori yang menunjang penelitian masalah nilai eigen dan vektor eigen yang diperumum untuk matriks atas aljabar maks-plus.
2.1
Tinjauan Pustaka
Ide aljabar maks-plus ditemukan pertama kali pada tahun 1950-an tetapi teori aljabar maks-plus mulai berkembang pada tahun 1960-an (Tam [14]). Dalam aljabar maks-plus nilai eigen dan vektor eigen penting dalam penyelesaian suatu sistem ataupun untuk menentukan kestabilan suatu sistem. Penelitian yang dilaksanakan Binding dan Volkmer [3] maupun Cuninghame-Green dan Butkoviˇc [5] menjelaskan tentang masalah nilai eigen dan vektor eigen yang diperumum pada aljabar maks-plus. Pada hasil penelitian yang dituliskan Binding dan Volkmer [3] menjelaskan mengenai masalah nilai eigen dan vektor eigen yang diperumum untuk matriks tak tereduksi nonnegatif. Sedangkan dalam penelitian yang telah dilakukan Elsner dan van den Driessche [6] menjelaskan suatu algoritma metode pangkat untuk menentukan nilai eigen dan vektor eigen. Adapun CuninghameGreen dan Butkoviˇc [5] dalam penelitiannya telah membahas mengenai masalah nilai eigen dan vektor eigen yang diperumum untuk matriks pada aljabar maksplus. Oleh karena itu, dalam penelitian ini akan dibahas mengenai penyelesaian masalah nilai eigen dan vektor eigen yang diperumum untuk matriks atas aljabar maks-plus.
4
2.2
Teori Penunjang
Pada bagian ini dijelaskan definisi dan teori untuk mendukung tujuan dari penelitian. Berikut definisi dan teorema tentang struktur aljabar biasa, aljabar maks-plus, matriks atas aljabar maks-plus, graf dalam aljabar maks-plus, nilai eigen dan vektor eigen.
2.2.1
Struktur Aljabar Biasa
Mengacu pada Herstein [9], berikut sifat-sifat aljabar biasa pada operasi penjumlahan dan perkalian. 1. Tertutup Ambil sebarang x, y ∈ R, sifat tertutup dipenuhi jika terdapat z1 , z2 ∈ R dan berlaku x + y = z1 . x × y = z2 . 2. Assosiatif Ambil sebarang x, y, z ∈ R berlaku (x + y) + z = x + (y + z). (x × y) × z = x × (y × z). 3. Komutatif Ambil sebarang x, y ∈ R berlaku x + y = y + x. x × y = y × x. 4. Distributif Ambil sebarang x, y, z ∈ R berlaku x(y + z) = xy + xz. (x + y)z = xz + yz. 5
5. Terdapat elemen identitas yaitu 0 terhadap operasi + dan 1 terhadap operasi × dan berlaku x + 0 = 0 + x = x. x × 1 = 1 × x = x. Berikut tiga definisi dalam aljabar biasa mengacu pada Herstein [9]. Definisi 2.2.1. Himpunan G disebut semigrup terhadap operasi biner + dan × jika berlaku sifat tertutup dan assosiatif. Definisi 2.2.2. Himpunan G disebut monoid terhadap operasi biner + dan × jika berlaku sifat tertutup, assosiatif, dan mempunyai elemen identitas. Definisi 2.2.3. Himpunan G disebut grup terhadap operasi biner + dan × jika memenuhi sifat tertutup, assosiatif, terdapat unsur identitas, dan setiap unsur dalam G memiliki invers. Menurut Subiono [12], berikut definisi mengenai semiring dan semilapangan dalam aljabar biasa. Definisi 2.2.4. Suatu semiring (S, +, ×) adalah himpunan tak kosong S disertai dengan operasi biner + dan ×, yang memenuhi aksioma 1. (S, +) adalah semigrup komutatif dengan elemen identitas 0, yaitu ∀x, y, z ∈ S memenuhi x+y = y+x (x + y) + z = x + (y + z) x + 0 = 0 + x = x. 2. (S, ×) adalah semigrup dengan elemen identitas 1, yaitu ∀x, y, z ∈ S memenuhi (x × y) × z = x × (y × z) x × 1 = 1 × x = x. 6
3. Sifat penyerap elemen netral 0 terhadap operasi ×, yaitu ∀x ∈ S memenuhi x × 0 = 0 × x = 0. 4. Operasi × distributif terhadap operasi +, yaitu ∀x, y, z ∈ S berlaku (x + y) × z = (x × z) + (y × z) x × (y + z) = (x × y) + (x × z). Definisi 2.2.5. Suatu semiring komutatif (S, +, ×) dinamakan semilapangan bila setiap elemen x di S − {0} mempunyai invers terhadap operasi ×, yaitu untuk setiap x di S − {0} ada x−1 sehingga x × x−1 = x−1 × x = 1.
2.2.2
Aljabar Maks-Plus
Berikut ini adalah definisi dari aljabar maks-plus menurut Tam [14]. ¯ = R∪ Definisi 2.2.6. Aljabar maks-plus adalah aljabar linear atas semiring R {∞}, yang dilengkapi dengan operasi penjumlahan ”⊕ = max” dan perkalian ”⊗ = +”. Elemen identitas untuk penjumlahan ϵ = −∞ dan elemen identitas untuk perkalian e = 0. ¯ menurut Heidergott Berikut sifat-sifat aljabar maks-plus dengan a, b, c ∈ R [8]. 1. Asosiatif a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c a ⊗ (b ⊗ c) = (a ⊗ b) ⊗ c. 2. Komutatif a⊕b=b⊕a a ⊗ b = b ⊗ a. 3. Distributif a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c).
7
4. Terdapat elemen identitas yaitu ϵ = −∞ untuk operasi ⊕ dan e = 0 untuk operasi ⊗ a⊕ϵ=ϵ⊕a=a a ⊗ e = e ⊗ a = a. 5. Idempoten a ⊕ a = a. Definisi 2.2.7. Misalkan a, b ∈ R, b disebut invers dari a apabila a⊗b=0=b⊗a dan dinotasikan b = a−1 .
2.2.3
Matriks atas Aljabar Maks-Plus
Menurut Farlow [7] dan Tam [14], operasi penjumlahan dan perkalian pada ¯ sama dengan operasi penjumlahan dan matriks atas aljabar maks-plus atas R perkalian matriks atas R. Diambil sembarang matriks A dan B dengan elemen ¯ dalam R. 1. Operasi Penjumlahan Diambil sebarang matriks a a12 . . . 11 a21 a22 . . . A= .. .. . . ... am1 am2 . . .
A dan B yang berukuran m × n, yaitu a1n b b12 . . . b1n 11 b a2n b22 . . . b2n dan B = 21 .. .. .. . . . . . . . .. amn bm1 bm2 . . . bmn
.
Elemen-elemen pada baris ke-i kolom ke-j dari matriks A dan B dinotasikan aij dan bij untuk i = 1, 2, . . . , m dan j = 1, 2, . . . , n. Elemen aij dapat juga dituliskan sebagai [A]ij . Operasi penjumlahan atas R dinotasikan dengan ⊕ sehingga penjumlahan matriks A dan B dalam dapat ditulis dengan Am×n ⊕ Bm×n = [A ⊕ B]ij = (aij ⊕ bij ) = (maks{aij , bij }) dengan i = 1, . . . , m dan j = 1, . . . , n. 8
2. Operasi Perkalian (a) Perkalian matriks dengan matriks Diambil sembarang matriks A yang berukuran m × p dan B yang berukuran p × n, yaitu a a12 . . . a1p 11 a21 a22 . . . a2p A= .. .. . . . . . . .. am1 am2 . . . amp
b11 b12 . . . b1n
b b . . . b2n dan B = 21 22 .. .. .. . . . ... . bp1 bp2 . . . bpn
Operasi perkalian atas R dinotasikan dengan ⊗ sehingga perkalian matriks A dan B atas R dapat ditulis dengan Am×p ⊗Bp×n =
p ⊕
(aik ⊗bkj ) = (maks{ai1 +b1j , ai2 +b2j , . . . , aip +bpj }).
k=1
(b) Perkalian skalar dengan matriks Diberikan skalar α ∈ R dan sebarang matriks A yang berukuran m×n. Perkalian skalar α dengan matriks A dapat ditulis dengan α ⊗ A = (α ⊗ aij ) dengan i = 1, . . . , m dan j = 1, . . . , n. Contoh 2.2.1.
Contoh 2.2.2.
Contoh 2.2.3.
3 5 0 8 3 8 ⊕ = 0 6 1 5 1 6 5 4 1 2 ⊗ = 4 1 −2 3
7 −1 5 −3 = 2⊗ 5 4 3 2 9
Menurut Tam [14] matriks A ≤ B jika untuk setiap (aij ) ≤ (bij ). Untuk setiap matriks-matriks A, B, C, dan vektor-vektor x, y dengan ukuran yang sesuai, serta α, β ∈ R dapat ditunjukkan bahwa 1. A ⊗ (α ⊗ B) = α ⊗ (A ⊗ B), 2. α(A ⊕ B) = α ⊗ A ⊕ α ⊗ B, 3. xT ⊗ α ⊗ y = α ⊗ (xT ⊗ y) dengan T adalah transpose, 4. (α ⊕ β) ⊗ A = α ⊗ A ⊕ β ⊗ A, 5. A ≤ B =⇒ A ⊕ C ≤ B ⊕ C, 6. A ≤ B =⇒ A ⊗ C ≤ B ⊗ C, 7. x ≤ y =⇒ A ⊗ x ≤ A ⊗ y, 8. A ≤ B ⇐⇒ A ⊕ B = B. Kemudian, Tam [14] mendefinisikan matriks diagonal dan matriks identitas sebagai berikut. Definisi 2.2.8. Misalkan a, b, c, . . . , adalah bilangan real. Matriks diagonal didefinisikan dengan a ϵ diag(a, b, c, . . .) = ϵ .. . ϵ
ϵ ϵ ... b ϵ ... ϵ .. .
c ... .. . . . .
ϵ ϵ ...
ϵ
ϵ ϵ .. . ...
Dari Definisi 2.2.8, didefinisikan matriks identitas seperti yang dapat dilihat pada Definisi 2.2.9 Definisi 2.2.9. Matriks identitas adalah suatu matriks diagonal dengan semua nilai diagonalnya sama dengan nol (I = diag(0, . . . , 0)).
10
Dari Definisi 2.2.9, itu berarti I ⊗ A = A = A ⊗ I untuk setiap matriks A dan I dengan ukuran-ukuran yang sesuai. Selanjutnya, matriks A0 = I untuk setiap matriks bujur sangkar. Berdasarkan Cuninghame-Green dan Butkoviˇc [5], didefinisikan matriks permutasi dan matriks permutasi yang diperumum. Setiap matriks yang dapat diperoleh dari matriks identitas dengan permutasi pada baris-baris dan/atau kolom-kolom disebut matriks permutasi. Setiap matriks yang dapat diperoleh dari matriks diagonal dengan permutasi pada baris-baris dan/atau kolom-kolom disebut matriks permutasi yang diperumum. Berdasarkan Tam [14], berikut diberikan definisi mengenai matriks konjugat. Didefinisikan R
m×n
adalah R dengan matriks yang berukuran m × n.
Definisi 2.2.10. Misalkan A = (aij ) ∈ R
m×n
. Konjugat dari matriks A yaitu
A∗ = (a∗ij ). Ini diperoleh dari negasi dan transpose matriks A. Secara matematis, A∗ dapat dituliskan dengan A∗ = −AT . n×n
Definisi 2.2.11. Misalkan A ∈ R
n×n
, A disebut invertible apabila ada B ∈ R
sedemikian sehingga A ⊗ B = I = B ⊗ A. Definisi 2.2.12. Misalkan A ∈ R
n×n
. Ak = |A ⊗ A ⊗ {z. . . ⊗ A}. k
2.2.4
Graf dalam Aljabar Maks-Plus
Berikut ini akan dijelaskan beberapa definisi mengenai graf dalam aljabar maks-plus menurut Schutter [10]. Suatu graf G didefinisikan sebagai pasangan (V, E), dengan V adalah suatu himpunan yang anggotanya disebut vertex dan E adalah suatu himpunan pasangan vertex. Anggota dari E disebut edge. Suatu digraf (graf berarah) G didefinisikan sebagai pasangan (V, A), dengan V adalah suatu himpunan vertex dan A adalah suatu himpunan pasangan vertex. Anggota dari A disebut arc. n×n
Definisi 2.2.13. Misalkan A ∈ R
. Graf precedence dari A dinotasikan oleh
G(A) adalah digraf (graf berarah) berbobot dengan vertex 1, . . . , n dimana terdapat arc (j, i) dengan bobot aij untuk aij ̸= −∞. 11
Graf precedence G(A) dikatakan strongly connected jika untuk setiap dua vertex yang berbeda i, j terdapat sebuah path dari i ke j, dimana pengertian path adalah barisan dari vertex i1 , i2 , . . . , ik sehingga terdapat sebuah arc dari ij ke ij+1 , untuk j = 1, . . . , k − 1. n×n
Definisi 2.2.14. Suatu matriks A ∈ R
dikatakan tak tereduksi jika graf pre-
cedence G(A) adalah strongly connected. Sebaliknya, jika graf precedence G(A) tidak strongly connected, maka matriks A adalah matriks tereduksi. Sebagai contoh, diberikan matriks A dan B yang diambil dari Andersen [1] 2 3 −∞ 2 3 −∞ A = −∞ 4 B = 1 −∞ 4 −∞ 5 −∞ −∞ 5 1 −∞
Gambar 2.1. (a) Graf Precedence G(A) (Kiri), (b) Graf Precedence G(B) (Kanan). Dari gambar 2.1.(a), terlihat bahwa graf precedence G(A) strongly connected, sehingga matriks A merupakan matriks taktereduksi. Sedangkan pada gambar 2.1.(b), terlihat bahwa graf precedence G(B) tidak strongly connected karena tidak terdapat path dari v3 menuju vertex lainnya, sehingga matriks B merupakan matriks tereduksi.
2.2.5
Nilai Eigen dan Vektor Eigen
Berikut ini pengertian nilai eigen dan vektor eigen dari suatu matriks dalam aljabar maks-plus menurut Subiono [12]. 12
Pengertian nilai eigen dan vektor eigen yang bersesuaian dari suatu matriks persegi A yang berukuran n × n sebagaimana dijumpai dalam aljabar linear biasa juga dijumpai dalam aljabar maks-plus, yaitu bila diberikan suatu persamaan A⊗x=λ⊗x dalam hal ini masing-masing vektor x ∈ Rn×n dan skalar λ ∈ R berturutturut dinamakan vektor eigen dan nilai eigen dari matriks A dengan vektor x ̸= (ϵ, ϵ, . . . , ϵ)T . Subiono dan van der Woude [13] menjelaskan berikut ini merupakan suatu algoritma untuk menentukan nilai eigen dan vektor eigen dari matriks A ∈ Rn×n yang dilakukan secara berulang dari bentuk persamaan linear x(k + 1) = A ⊗ x(k), k = 0, 1, 2, . . .
(2.1)
1. mulai dari sembarang nilai awal x(0) ̸= (ε, ε, . . . , ε)T , 2. iterasi persamaan (2.1) hingga terdapat bilangan bulat p dan q dengan p > q ≥ 0 serta bilangan real c sehingga terjadi suatu perilaku periodik atau memenuhi x(p) = c ⊗ x(q), 3. hitung nilai eigen λ =
c , p−q
4. hitung vektor eigen p−q ⊕ v= (λ⊗(p−q−i) ⊗ x(q + i − 1)). i=1 n×n
Definisi 2.2.15. (Tam [14]) Diberikan A ∈ R n
(i) V (A, λ) = {x ∈ R | A ⊗ x = λ ⊗ x}, (ii) Λ(A) = {λ ∈ R | ∨(A, λ) ̸= {ϵ}}, (iii) V (A) =
∪ λ∈∧(A)
∨(A, λ),
(iv) V + (A, λ) = ∨(A, λ) ∩ Rn , (v) V + (A) = ∨(A) ∩ Rn . 13
dan λ ∈ R. Didefinisikan
2.3
Kerangka Pemikiran
Berdasarkan tinjauan pustaka, dapat dibentuk kerangka pemikiran untuk menyelesaikan masalah nilai eigen dan vektor eigen yang diperumum untuk matriks atas aljabar maks-plus. Masalah nilai eigen dan vektor eigen yang diperumum membentuk persamaan A ⊗ x = λB ⊗ x di dalam persamaan tersebut ada matriks B yang menyebabkan bentuk yang diperumum. Akan tetapi pada persamaan (2.3) untuk matriks nonnegatif. Dalam masalah nilai eigen dan vektor eigen yang diperumum akan ditentukan sebarang matriks B yang sesuai dengan banyaknya nilai eigen dan vektor eigen. Masalah nilai eigen dan vektor eigen yang diperumum ini mengacu pada Binding dan Volkmer [3]. Dalam masalah nilai eigen dan vektor eigen yang diperumum untuk matriks tak tereduksi dan matriks tereduksi yang mengacu pada CuninghameGreen dan Butkoviˇc [5] disajikan dalam bentuk A ⊗ x = λ ⊗ B ⊗ x. Adapun untuk menentukan nilai eigen dan vektor eigen mengacu pada algoritma metode pangkat yang telah dijelaskan Elsner dan van den Driessche [6].
14
