BAB III TEORI PERRON-FROBENIUS

BAB III : TEORI PERRON-FROBENIUS

BAB III TEORI PERRON-FROBENIUS Pada Bab III ini akan dibahas mengenai Teori Perron-Frobenius, yaitu teori hasil kontribusi dari seorang matematikawan asal German, Oskar Perron dan Ferdinand Georg Frobenius. Perron menerbitkan tulisannya tentang sifat-sifat yang dimiliki oleh matriks positif pada tahun 1907. Kemudian pada tahun 1912, Frobenius memberikan kontribusi yang cukup besar dalam memperluas hasil yang telah diperoleh Perron dalam menyelidiki sifat-sifat dari matriks nonnegatif. Jadi, teori ini pada dasarnya membahas mengenai sifat-sifat dari matriks postif dan matriks nonnegatif berdasarkan sifat spektralnya.

Sebelum kita memasuki pada pembahasan mengenai Teori Peron-Frobenius, berikut ini akan dikenalkan notasi yang akan digunakan dalam pembahasan selanjutnya. Misalkan matriks A ∈

mxn

dengan elemen-elemennya berupa bilangan real, yaitu

A = ⎡⎣ aij ⎤⎦ untuk setiap i = 1, 2,...., m ; j = 1, 2,..., n . Matriks A disebut matriks

nonnegatif (notasi : A ≥ 0 ) jika untuk setiap elemen dari matriks A bernilai nonnegatif ( a ij ≥ 0 ). Secara umum, A ≥ B berarti untuk setiap aij ≥ bij . Matriks A disebut matriks positif (notasi : A > 0 ) jika untuk setiap elemen dari matriks A bernilai postif ( a ij > 0 ). Secara umum, A > B berarti untuk setiap aij > bij . Selain itu,

Teori Perron-Frobenius untuk Matriks Stokastik Madona Yunita (10103035)

34


notasi ∗ , kita mengenalnya untuk menyatakan nilai determinan dari suatu matriks. Namun, dalam bab ini, notasi ∗ pada suatu matriks, misalkan matriks A , yaitu A menyatakan matriks dengan elemennya adalah aij .

Berikut ini adalah teorema yang mendukung beberapa teorema lainnya dalam bab ini seperti pada Teorema 3.2 dan Teorema 3.6. Teorema 3.1 Misalkan matriks A ∈

n×n

dan vektor u, v ∈

n×1

, maka pernyataan

berikut ini benar. (a).

A > 0 dan u ≥ 0 , u ≠ 0 ⇒ Au > 0 .

(b).

A ≥ 0 , A ≠ 0 , dan u > v > 0 ⇒ Au > Av .

Bukti (a). Misal A = ⎡⎣ aij ⎤⎦ > 0 , untuk setiap i, j = 1, 2,..., n dan misalkan pula u > 0 ,

u ≠ 0 , maka terdapat k ∈ {1, 2,..., n} sehingga uk = 0 . Tanpa mengurangi keumuman misalkan u1 = 0 maka Au = [ Au ]i , untuk setiap i = 1, 2,..., n n

= ∑ aij u j , karena u1 = 0 maka j =1 n

= ∑ aij u j > 0 j =2

Bukti (b). Vektor u > v menyatakan bahwa setiap elemen pada vektor u lebih besar daripada elemen yang bersesuaian pada vektor v . Jika setiap elemen pada matriks A nonnegatif ( A ≥ 0 ) maka u > v akan mengakibatkan Au > Av , karena selisih elemen

∑ a (u n

ke- i adalah

j =1

ij

j

− vj ) > 0 .


35


3.1 Matriks Positif

Pada awal bab ini akan diuraikan sifat-sifat yang dimiliki oleh matriks positif, khususnya untuk matriks persegi, yaitu A nxn > 0 dengan elemen-elemen matriks yang bernilai positif. Tujuannya adalah untuk menyelidiki ke arah mana perluasan dari sifat matriks positif ini yang diturunkan berdasarkan nilai karakteristik dan vektor karakteristik dari matriks A .

Perhatikan bahwa, A > 0 ⇒ ρ ( A) > 0 .

(3.1)

Karena jika σ ( A ) = {0} maka bentuk Jordan untuk A adalah A sendiri yang bersifat nilpoten dan tidak mungkin untuk setiap aij ≥ 0 . Hal ini berarti dalam pembahasan selanjutnya akan dikhususkan untuk matriks positif yang mempunyai spectral radius 1, karena A akan selalu bisa dinormalkan oleh spectral

radius.

Sebagai

contoh,

A>0⇔

A >0 ρ (A)

dan

ρ ( A) = r ⇔ ρ ( A / r ) = 1 .

Berikut ini adalah beberapa teorema yang merupakan sifat-sifat yang dimiliki oleh matriks positif berdasarkan vektor karakteristik dan nilai karakteristiknya. Teorema 3.2 Jika A nxn > 0 maka pernyataan di bawah ini benar. ρ ( A) ∈ σ ( A) . (a).

(b).

jika Ax = ρ ( A)x maka A x = ρ ( A) x dan x > 0 .

Dengan kata lain, A mempunyai pasangan karakteristik dengan bentuk ( ρ ( A ), v) dimana v > 0 .

Bukti. Tanpa mengurangi keumuman, misalkan ρ ( A ) = 1 . Jika (λ , x) adalah

pasangan karakteristik untuk A dimana λ = 1 maka


36


x = λ x = λ x = Ax ≤ A x = A x

⇒

x ≤ A x

(3.2)

Misalkan z = A x dan y = z − x , maka persamaan (3.2) akan mengakibatkan y ≥ 0 . Andaikan y ≠ 0 , artinya terdapat yi > 0 dan berdasarkan persamaan

Teorema 3.1(a) maka Ay > 0 dan z > 0 , serta terdapat ε > 0 sehingga Ay > ε z atau

A z>z. 1+ ε

A . Dengan mengalikan kedua ruas dengan B dan 1+ ε

Tulis Bz > z , dimana B =

berdasarkan persamaan Teorema 3.1(b) maka

B2 z > Bz > z, B3 z > B2 z > z,..... ⇒ Bk z > z untuk setiap k = 1, 2,.... lim k →∞ B k = 0

Tetapi, Teorema

2.25,

karena

maka

0 = y = A x − x , dimana

diperoleh

x

⎛ A ⎝ 1+ ε

ρ (B ) = ρ ⎜

0>z

1 ⎞ <1 ⎟= ⎠ (1 + ε )

berdasarkan

(kontradiksi).

Akibatnya,

adalah vektor karakteristik untuk A yang

bersesuaian dengan nilai karakteristik 1 = ρ ( A ) . Karena x ≥ 0, x ≠ 0 , dan

A > 0 , maka x = A x > 0 berdasarkan Teorema 3.1(a). Pada teorema sebelumnya telah ditunjukkan bahwa ρ ( A ) > 0 adalah nilai karakteristik untuk A > 0 . Langkah selanjutnya adalah menyelidiki indeks dari nilai karakteristik tersebut yang akan diuraikan pada teorema berikut ini. Teorema 3.3 Jika A nxn > 0 maka pernyataan di bawah ini benar. (a).

ρ ( A ) adalah satu-satunya nilai karakteristik A pada lingkaran spektral .

(b).

Indeks ( ρ ( A )) = 1 . Dengan kata lain, ρ ( A ) adalah nilai karakteristik

semisimple.


37


Bukti.. Tanpa mengurangi keumuman, misalkan ρ ( A ) = 1 . Jika (λ , x) adalah pasangan karakteristik untuk A dimana λ = 1 maka 0 < x = A x berdasarkan Teoerma 3.2(b). Jadi, n

0 < x k = ( A x )k = ∑ akj x j

xk = λ xk = ( λ x )k = ( Ax )k =

atau

j =1

n

∑a j =1

kj

xj ,

sehingga n

∑a j =1

kj

n

n

j =1

j =1

x j = ∑ akj x j = ∑ akj x j .

Berdasarkan Teorema 2.12, maka untuk suatu α j > 0 , berlaku akj x j = α j (ak1 x1 ) atau x j = π j x1 , dengan π j =

α j ak1 akj

> 0 . Dengan kata lain, jika λ = 1 , maka

x = x1 p , dimana p = (1 π 2 .... π n ) > 0 , maka T

λ x = Ax ⇒ λ p = Ap = Ap = λ p = λ p ⇒ λ = 1 dan λ = 1 ini merupakan satu-satunya nilai karakteristik pada lingkaran spektralnya. Misalkan, indeks(λ = 1) = m > 1 , maka A k

∞

→ ∞ jika k → ∞

karena terdapat blok Jordan m × m , yaitu J * dengan bentuk Jordan J = P −1AP yang

serupa,

Jk

= P −1 A k P

∞

J*

maka ∞

≤ P −1

∞

Ak

A

∞

∞

k ∞

→∞ P

≥

∞

sehingga

Jk

∞

→∞,

akibatnya

, maka

Jk P −1

∞

→∞.

∞

P

∞

Misalkan A k = ⎡⎣ aij ( k ) ⎤⎦ dan misalkan pula ik menyatakan baris ke- ik dimana Ak

∞

= ∑ j aij ( k ) . Kita mengetahui bahwa terdapat vektor p > 0 sehingga

p = Ap , maka untuk suatu vektor karakteristik, p

∞

(

)

⎛ ⎞ ≥ pik = ∑ aij ( k ) p j ≥ ⎜ ∑ aij ( k ) ⎟ min pi = A k j ⎝ j ⎠ i


∞

( min p ) → ∞ . i

i

38


Namun, hal ini tidak mungkin karena p adalah vektor konstan, maka pemisalan indeks(1) > 1 salah. Jadi haruslah indeks(1) = 1 .

Teorema 3.4 Jika A n×n > 0 maka ma ( ρ ( A) ) = 1 . Dengan kata lain, spectral radius

dari

A

disebut

nilai

karakteristik

simple

dari

A.

Jadi,

dim ( N ( A − ρ ( A)I ) ) = mg ( ρ ( A) ) = ma ( ρ ( A) ) . Bukti. Tanpa mengurangi keumuman, misalkan ρ ( A ) = 1 dan misalkan pula

ma ( λ = 1) = m > 1 . Kita mengetahui bahwa λ = 1 adalah nilai karakteristik semisimple, yaitu ma (1) = mg (1) , maka terdapat m buah vektor karakteristik

yang bebas linier yang berkorespondensi dengan λ = 1 . Jika x dan y adalah pasangan vektor karakteristik yang saling bebas linier yang berkorespondensi dengan λ = 1 , maka x ≠ α y untuk setiap α ∈ . Pilih elemen tak nol dari vektor y , misal yi ≠ 0 dan tulis z = x − ( xi / yi )y . Karena Az = z maka

A z = z > 0 . Tetapi, hal ini kontradiksi karena zi = xi − ( xi / yi ) yi = 0 . Jadi, haruslah m = 1 . Karena N ( A − ρ ( A)I ) adalah ruang vektor berdimensi satu yang bisa dispan dengan

suatu

v > 0,

maka

terdapat

p ∈ N ( A − ρ ( A)I ) , sehingga p > 0 dan

∑

vektor j

karakteristik

tunggal

p j = 1 (diperoleh dari normalisasi

p = v / v 1 ). Vektor karakteristik p ini disebut dengan vektor Perron dari matriks A dengan nilai karakterstik yang berkorespondensi r = ρ ( A ) disebut akar Perron untuk A .

Teorema 3.5

Jika A > 0 maka terdapat vektor p > 0 tunggal sehingga

Ap = ρ ( A ) p dan p 1 = 1 .


39


Bukti. Misalkan

Ap = ρ ( A ) p ,

p1 = α p2

p1 dan p2 merupakan vektor-vektor yang memenuhi

p > 0 , dan

untuk

p1 1 = α p2

1

p 1 = 1 . Karena dim ( A − ρ ( A ) I ) = 1 , maka

α >0.

suatu

p1 1 = p2 1 = 1 ,

maka

⇒ α = 1 . Jadi, p1 = p2 .

Karena A > 0 ⇔ AT > 0 dan ρ ( A) = ρ ( AT ) , jelas bahwa jika A > 0 maka untuk pasangan karakteristik Perron

( r, p )

untuk A terdapat pasangan

karakteristik Perron yang berkorespondensi

( r, q )

untuk

A T . Karena

qT A = rqT . Vektor qT > 0 disebut vektor Perron kiri untuk A . Teorema 3.6 Tidak ada vektor karakteristik nonnegatif lainnya dari An×n > 0 selain vektor Perron p dan kelipatan positifnya.

Bukti. Jika (λ , y) adalah pasangan karakteristrik dari A , dimana y ≥ 0 , dan

x > 0 adalah vektor Perron dari matriks A T , maka xT y > 0 (Teorema 3.1(a)), sehingga ρ ( A)xT = xT A ⇒ ρ ( A)xT y = xT Ay = λ xT y ⇒ ρ ( A) = λ .

Berikut ini adalah teorema yang menyatakan cara lain dalam mencari akar Perron. Formula ini ditemukan oleh matematikawan kebangsaan German yang bernama Lothar Collatz. Formula ini selanjutnya digunakan oleh Helmut Wielandt untuk membangun Teori Perron-Frobenius. Oleh karena itu, Teorema 3.7 ini dikenal pula dengan Teorema Collatz-Wielandt. Teorema 3.7 Akar Perron dari A n×n > 0 diberikan oleh r = max f (x) , dimana f (x) = min x∈N

1≤i ≤ n xi ≠0


[ Ax ]i xi

dan N = {x/x ≥ 0,x ≠ 0} .

40


Bukti. Misal ξ = f (x) , maka 0 ≤ ξ x ≤ Ax untuk setiap x ∈ N . Misalkan pula

p dan qT berturut-turut adalah vektor Perron kanan dan vektor Perron kiri dari A yang berkorespondensi dengan r (akar Perron). Berdasarkan Teorema 3.1(a), kita peroleh q T x > 0 , maka

ξ x ≤ Ax ⇒ ξ q T x ≤ q T Ax = rq T x ⇒ ξ ≤ r ⇒

f (x) ≤ r ,

untuk setiap x ∈ N . Karena f ( p ) = r dan p ∈ N , akibatnya r = max f (x) . x∈N

Berdasarkan beberapa teorema yang telah diuraikan sebelumnya mengenai sifat-sifat dari matriks positif, berikut ini merupakan rangkuman sifat-sifat tersebut yang dikenal dengan Teorema Perron, yaitu misalkan A nxn > 0 dengan

r = ρ ( A ) , maka pernyataan berikut benar. (a).

r > 0.

(b).

r ∈ σ ( A ) ( r disebut akar Perron dari A ).

(c).

ma(r ) = 1 .

(d).

Terdapat vektor karakteristik x > 0 sehingga Ax = rx .

(e).

Vektor Perron adalah vektor tunggal yang didefinisikan oleh Ap = rp , dimana p > 0 dan p 1 = 1 . Kecuali untuk vektor kelipatan dari p , tidak ada vektor karakteristik nonegatif lainnya dari A .

(f).

Akar Perron merupakan satu-satunya nilai karakteristik dalam lingkaran spektralnya.

(g).

Akar Peron dari A diberikan oleh r = max f (x) , dimana x∈N

f (x) = min 1≤i ≤ n xi ≠0

[ Ax ]i xi


dan N = {x/x ≥ 0,x ≠ 0} .

41


3.2 Matriks Nonnegatif Pada subbab sebelumnya telah diuraikan mengenai sifat-sifat yang dimiliki oleh matriks positif berdasarkan nilai karakteristik dan vektor karakteristiknya. Dalam subbab ini, kita akan melihat bagaimana jika dalam matriks tersebut terdapat elemen bernilai nol. Dengan kata lain, matriks yang kita hadapi adalah matriks nonnegatif. Teorema 3.8 Misalkan Jika A nxn ≥ 0 dengan r = ρ ( A ) , maka pernyataan berikut benar. (a).

r ∈ σ ( A ) , berlaku pula untuk r = 0 .

(b).

Az = rz untuk suatu z ∈ N = {x/x ≥ 0, x ≠ 0} .

(c).

r = max f (x) dengan f (x) = min 1≤i ≤ n

x∈N

xi ≠0

[ Ax ]i xi

dan N = {x/x ≥ 0,x ≠ 0} .

( k ) E > 0 dimana

Bukti (a)&(b). Perhatikan barisan matriks positif A k = A + 1

E adalah matriks dengan elemennya adalah satu. Misal rk dan pk berturutturut adalah akar Perron dan vektor Perron dari matriks Ak . Kita mengetahui bahwa

{ pk }k =1 ∞

adalah himpunan terbatas karena himpunan tersebut termuat

dalam unit 1-sphere (Definsi 2.13) di ℜn . Berdasarkan Teorema Bolzano Weirstrass, kita peroleh bahwa { pk }k =1 mempunyai subbarisan yang konvergen. ∞

Misalkan lim pki = p* dimana p* ≥ 0, p* ≠ 0 (karena pki > 0 dan i →∞

p ki

1

= 1 ).

Dari Teorema 2.20, kita peroleh bahwa jika A1 > A 2 > A3 > .... > A maka

r1 > r2 > r3 > .... > r . Jadi, {rk }k =1 adalah barisan monotonik positif dengan batas ∞

bawahnya adalah r , artinya

lim rk = r * ada dan r * ≥ r . Secara khusus, k →∞

lim rki = r * ≥ r . k →∞


42


Bukti (c). Misal qTk adalah vektor Perron kiri dari Ak . Untuk setiap x ∈ N dan

k > 0 , maka qTk > 0 dan 0 ≤ f (x)x ≤ Ax ≤ A k x

⇒

f (x)qkT x ≤ qkT A k x = rk qkT x

⇒

f (x) ≤ rk

⇒

f (x) ≤ r ( karena rk → r * = r )

karena f ( z ) = r dan z ∈ N , akibatnya r = max f (x) . x∈N

Hanya sampai sejauh ini Teorema Perron bisa digeneralisasikan pada matriks ⎡0 1 ⎤ nonnegatif tanpa perlu adanya tambahan hipotesis. Sebagai contoh, A = ⎢ ⎥ ⎣0 0⎦ menunjukkan bahwa Teorema Perron (a), (c), dan (d) tidak berlaku secara ⎡0 1 ⎤ umum untuk matriks nonnegatif dan A = ⎢ ⎥ menunjukkan bahwa pada ⎣1 0 ⎦ Teorema Perron (f) juga tidak berlaku.

Berdasarkan hal tersebut, Frobenius melihat bahwa masalah ini bukan hanya terletak pada ada atau tidaknya nilai nol sebagai elemen dalam matriks nonnegatif tetapi posisi dari elemen nol ini. Sebagai contoh, Teorema Perron (c) dan (d) tidak berlaku untuk ⎡1 0 ⎤ ⎡1 1 ⎤ , tetapi teorema tersebut berlaku untuk A 2 = ⎢ A1 = ⎢ ⎥ ⎥. ⎣1 1 ⎦ ⎣1 0 ⎦

(3.3)

Kejeniusan Frobenius adalah melihat perbedaan antara matriks A1 dan A2 dalam istilah dan menghubungkan hal ini dengan sifat spketral pada matriks nonnegatif. Berikut ini merupakan definisi dari tereduksi dan graf yang akan dikaitkan dengan sifat pada matriks nonnegatif tersebut.


43


Definisi 3.9

Matriks A nxn disebut matriks tereduksi jika terdapat matriks

⎡X Y⎤ permutasi P sehingga B = PT AP = ⎢ ⎥ , dimana X dan Z adalah matriks ⎣ 0 Z⎦ persegi. Jika matriks A tidak tereduksi maka A disebut matriks tak tereduksi. Matriks B disebut matriks permutasi simetri dari A . Efeknya adalah menukar baris dan kolom yang bersesuaian. Akibat 3.10 G ( B ) = G ( A ) untuk setiap P matriks permutasi.

Bukti. Jika baris (dan kolom) pada matriks P adalah vektor unit yang muncul ⎛1 2 berdasarkan permutasi π = ⎜ ⎝ π1 π 2

⎡⎛ eπT ⎞ ⎢⎜ 1 ⎟ T aij = ⎣⎡ PBP ⎦⎤ = ⎢⎜ ⎟ B eπ1 ij ⎢⎜ eT ⎟ ⎣⎢⎝ π n ⎠

(

n⎞ , maka π n ⎟⎠

eπ n

)

⎤ ⎥ T ⎥ = eπ i Beπ j = bπ i π j . ⎥ ⎦⎥ ij

Akibatnya, aij ≠ 0 jika dan hanya jika bπ i π j ≠ 0 maka graf G ( B ) sama dengan graf G ( A ) kecuali titik Nk pada G ( A ) adalah titik Nπ k pada G ( B ) untuk setiap k = 1, 2,..., n .

Definisi 3.11 Graf G ( A ) dari A adalah graf berarah untuk n buah titik

{ N1 , N 2 , N3 ,..., N n }

dimana terdapat lintasan yang menghubungkan dari titik

Ni ke N j jika dan hanya jika aij ≠ 0 . G ( A ) terhubung kuat jika untuk setiap pasangan titik ( N i , N k ) terdapat lintasan yang menghubungkan dari titik Ni ke

Nk .


44


Teorema 3.12 Matriks A tak tereduksi jika dan hanya jika G ( A ) terhubung kuat.

Bukti. Akan dibuktikan dengan kontrapositif, yaitu A tereduksi jika dan hanya jika G ( A ) tidak terhubung kuat.

( ⇒ ) Jika

A

tereduksi maka terdapat matriks permutasi

P sehingga

⎡X Y⎤ PT AP = ⎢ ⎥ . Misalkan matriks X berukuran m x m , maka untuk i > m ⎣ 0 Z⎦ graf G ( PT AP ) tidak mempunyai lintasan dari titik Ni ke N j untuk j ≤ m . Akibatnya graf G ( PT AP ) = G ( A ) tidak terhubung kuat.

( ⇐)

Jika G ( A ) tidak terhubung kuat maka terdapat dua titik di G ( A )

sehingga tidak terdapat lintasan dari titik yang satu ke titik yang lain. Tanpa mengurangi keumuman, misalkan kedua titik tersebut adalah

N1 dan Nn

dimana N1 tidak tidak dapat diakses dari Nn . Misalkan pula terdapat tambahan titik yang tidak dapat diakses dari Nn (kecuali Nn sendiri). Sebut titik tersebut

N1 , N2 ,…, N r , sehingga himpunan titik-titik yang tidak dapat diakses dari

Nn (kecuali Nn sendiri) adalah P = { N 2 , N3 ,...., N r } . Sebut sisa dari titik tersebut adalah titik yang dapat diakses dari

Nn

dalam himpunan

Q = { N r +1 , N r +1 , N n −1} . Akibatnya tidak ada titik pada P yang dapat diakses dari titik pada Q . Jika tidak maka titik pada P dapat diakses dari titik Nn melalui titik pada Q . Dengan kata lain, jika N r + k ∈ Q dan N r + k → Ni ∈ P maka ⎛1 2 N n → N r + k → Ni (tidak mungkin). Artinya, jika π = ⎜ ⎝ π1 π 2

permutasi

yang

dibangun

dari

maka

aπ iπ j = 0

n⎞ adalah π n ⎟⎠

untuk

setiap

i = r + 1, r + 2,...., n − 1 dan j = 1, 2,...., r . Akibatnya, jika B = PT AP dimana P


45


adalah matriks permutasi yang berkorespondensi dengan permutasi π maka

⎡X Y⎤ B = PT AP = ⎢ ⎥ dimana X berukuran r × r dan Z berukuran n − r × n − r ⎣ 0 Z⎦ sehingga A tereduksi.

Sebagai contoh, matriks A1 pada (3.3) tereduksi karena

⎡1 1⎤ ⎡0 1 ⎤ PT A1 P = ⎢ untuk P = ⎢ ⎥ ⎥. ⎣0 1⎦ ⎣1 0 ⎦ Seperti yang terlihat pada Gambar 1 berikut, G ( A1 ) tidak terhubung kuat karena tidak terdapat lintasan yang menghubungkan dari titik 1 ke titk 2. Namun, matriks A2 tak tereduksi dan G ( A 2 ) terhubung kuat seperti yang terlihat pada Gambar 1.

1

2

G(A1)

2

1

G(A2)

Gambar 1. Contoh Graf dari Matriks Tereduksi dan Matriks Tak Tereduksi

Sampai dengan tahap ini, kita bisa perhatikan bahwa beberapa sifat pada Teorema Perron dapat diperluas untuk matriks nonnegatif. Hal ini berlaku dengan catatan bahwa elemen nol pada matriks berada pada posisi yang tepat untuk memastikan sifat tak tereduksi dari suatu matriks. Untuk membuktikan bahwa hal tersebut berlaku, maka teorema berikut ini akan diperlukan.

Teorema 3.13 Misal matriks A nxn ≥ 0 serta Ni dan N j adalah titik dalam graf

G ( A ) . Terdapat lintasan dengan panjang k dalam G ( A ) dari Ni dan N j Teori Perron-Frobenius untuk Matriks Stokastik Madona Yunita (10103035)

46


jika dan hanya jika ⎣⎡ A k ⎦⎤ ≠ 0 . ij Bukti. Dengan menggunakan induksi, untuk m = 1 , trivial. Selanjutnya, untuk

m=2,

n

n

k =1

k =1

⎡⎣ A 2 ⎤⎦ = ∑ [ A ]ik [ A ]kj = ∑ aik akj , untuk setiap ij

i, j ∈ {1, 2,..., n} ,

sehingga ⎡⎣ A 2 ⎤⎦ ≠ 0 jika dan hanya jika paling sedikit satu indeks k , yaitu nilai ij

aik dan akj tak nol. Hal ini sama saja artinya dengan jika dan hanya jika terdapat lintasan dengan panjang dua dalam G ( A ) dari Ni ke N j . Secara umum, misalkan m = q benar, akan ditunjukkan untuk m = q + 1 benar, n

n

k =1

k =1

⎡⎣ A q +1 ⎤⎦ = ∑ ⎡⎣ A q ⎤⎦ [ A ]kj = ∑ ⎡⎣ A q ⎤⎦ akj ≠ 0 jika dan hanya jika paling sedikit ij ik ik satu indeks k , yaitu nilai ⎡⎣ A q ⎤⎦ dan akj tak nol. Hal ini ekivalen dengan ik menyatakan bahwa terdapat lintasan dengan panjang k dari Ni ke Nk dan terdapat lintasan dengan panjang satu dari

Nk ke N j . Dengan kata lain,

terdapat lintasan dengan panjang q + 1 dari Ni dan N j .

Teorema selanjutnya merupakan teorema yang menunjukkan bagaimana mengubah matriks nonnegatif tak tereduksi menjadi matriks positif.

Teorema 3.14. Jika A nxn ≥ 0 matriks tak tereduksi maka ( A + I )

n −1

> 0.

Bukti. Karena A tak tereduksi maka G ( A ) terhubung kuat, sehingga untuk setiap pasangan titik

(N , N ) i

j

terdapat lintasan dengan panjang k (dengan

k < n ) dari Ni ke N j . Berdasarkan Teorema 3.13, kita mempunyai aij( k ) > 0 dan hal ini menjamin bahwa Teori Perron-Frobenius untuk Matriks Stokastik Madona Yunita (10103035)

47

BAB III : TEORI PERRON-FROBENIUS n −1 n − 1 ⎡ n −1 n − 1⎞ k ⎤ ⎛ ⎞ (k ) ⎡( I + A )n −1 ⎤ = ⎢ ∑ ⎜⎛ A ⎥ = ∑⎜ a ij > 0 . ⎟ ⎟ ⎣ ⎦ ij ⎣ k =0 ⎝ k ⎠ ⎦ ij k =0 ⎝ k ⎠

Pada Teorema 3.15 dan Teorema 3.16 berikut ini merupakan teorema pendukung untuk mencari sifat nilai karakteristik dan vektor karakteristik matriks nonnegatif tak tereduksi pada Teorema 3.17.

Teorema 3.15

A nxn

Misal

dan

λ1 > λ2 > .... > λn adalah nilai-nilai

karaketristik untuk A , maka λ1 + 1, λ2 + 1,...., λn + 1 adalah nilai karakteristik untuk I + A dan ρ ( I + A ) ≤ 1 + ρ ( A ) . Jika A ≥ 0 maka ρ ( I + A ) = 1 + ρ ( A ) . Bukti. Jika λ ∈ σ ( A ) dengan multipilsitas aljabarnya adalah k , maka λ adalah akar dari persamaan karaketeristik pA ( t ) = det ( tI − A ) = 0 dengan multiplisitasnya

k.

λ +1

Tetapi

pA +I ( s ) = det ( sI − ( A + I ) ) = 0

dengan

adalah

akar

dari

multiplisitasnya

persamaan

k

karena

det ( tI − A ) = det ( ( t + 1) I − ( A + I ) ) , maka λ1 + 1, λ2 + 1,...., λn + 1 adalah nilai karakteristik

I + A.

untuk

Akibatnya

ρ ( I + A ) = max λi + 1 ≤ max λi + 1 = ρ ( A ) + 1 . Selanjutnya, 1 + ρ ( A ) adalah 1≤ i ≤ n

1≤ i ≤ n

nilai karakteristik bagi I + A karena A ≥ 0 sehingga

Ax = ρ ( A ) x ⇒

( A + I ) x = ( ρ ( A ) +1) x .

Jadi, ρ ( I + A ) = 1 + ρ ( A ) .

Teorema 3.16 Jika A nxn ≥ 0 dan A k > 0 untuk suatu k ≥ 1 , maka ρ ( A ) adalah nilai karakteristik simple untuk A .


48


Bukti. Jika λ1 > λ2 > .... > λn adalah nilai-nilai karaketristik untuk A , maka

λ1k > λ2k > .... > λnk adalah nilai karakteristik untuk A k . Selanjutnya, ρ ( A ) adalah nilai karakteristik untuk A dari Teorema 3.8(a), sehingga jika ρ ( A ) adalah nilai karakteristik multiple untuk A , maka ρ ( A ) = ρ ( A k ) adalah nilai k

karakteristik multiple untuk A k . Tetapi, hal ini tidak mungkin karena ρ ( A k ) adalah nilai karakteristik simple untuk A k berdasarkan Teorema Perron (c). Jadi, haruslah ρ ( A ) nilai karakteristik simple untuk A .

Teorema 3.17 Misalkan A nxn ≥ 0 tak tereduksi, maka (a).

r = ρ ( A ) adalah nilai karakteristik simple untuk A .

(b).

Terdapat vektor karakteristik x > 0 sehingga Ax = rx .

(c).

terdapat vektor p > 0 tunggal sehingga Ap = ρ ( A ) p dan p 1 = 1 .

Bukti (a). Jika

ρ ( A ) adalah nilai karakteristik multiple untuk A ,

maka 1 + ρ ( A ) = ρ ( I + A )

(berdasarkan

Teorema

3.15)

karakteristik multiple untuk I + A . Tetapi, I + A ≥ 0 dan

adalah

(I + A)

n −1

nilai

> 0 dari

Teorema 3.14, sehingga 1 + ρ ( A ) adalah nilai karakteristik simple untuk I + A berdasarkan Teorema 3.16. Jadi, ρ ( A ) juga merupakan nilai karakteristik

simple untuk A . Bukti (b). Dari Teorema 3.8, kita peroleh bahwa terdapat x ≥ 0 sehingga

Ax = rx . Selanjutnya,

(I + A)

n −1

>0

(I + A )

n −1

x = (1 + ρ ( A ) )

berdasarkan

x = (1 + ρ ( A ) )

1− n

(I + A )

n −1

n −1

Teorema

x

dan karena matriks 3.14,

maka

x > 0.


49


Selanjutnya, untuk pembuktian Teorema 3.17 (c) ini dapat dilihat pada pembukitan Teorema 3.5.

Berdasarkan beberapa teorema yang telah diuraikan sebelumnya mengenai sifat-sifat dari matriks nonnegatif, dapat kita peroleh Teorema Perron Frobenius. Pada dasarnya, sifat-sifat dari Teorema Perron-Frobenius ini masih sama dengan beberapa sifat pada Teorema Perron, yaitu jika A nxn ≥ 0 tak tereduksi maka berlaku sifat (a), (b), (c), (d), (e), dan (g) pada Teorema Perron pada halaman 41.

Satu-satunya sifat pada Teorema Perron yang tidak dapat dipertahankan adalah sifat (f) di halaman 41 yang menyatakan bahwa r adalah satu-satunya nilai

⎡0 1 ⎤ karakteristik pada lingkaran spektral. Sebagai contoh, A = ⎢ ⎥ nonnegatif ⎣1 0 ⎦ tak tereduksi, tetapi A memiliki dua buah nilai karakteristik pada lingkaran spektral yaitu ±1 . Berdasarkan keberadaan nilai karakteristik pada lingkaran spektral yang terdiri dari satu buah nilai karakterstik atau lebih, kita bisa membagi matriks nonnegatif tak tereduksi menjadi dua bagian.

Definisi 3.18 Matriks nonnegatif tak tereduksi A yang mempunyai satu nilai karakteristik r = ρ ( A ) pada lingkaran spektralnya disebut matriks primitf. Matriks nonnegatif tak tereduksi A yang mempunyai h > 1 buah nilai karakteristik pada lingkaran spektralnya disebut matriks imprimitf.

Jika kita memiliki matriks primitif maka matriks tersebut akan konvergen ke dalam bentuk tertentu yang diberikan pada Teorema 3.19. Sebaliknya, jika kita memiliki matriks imprimitif maka matriks tersebut tidak akan konvergen. Namun, matriks imprimitif memiliki limit Cesaro yang diberikan pada Teorema


50


3.23. Karena matriks primitif konvergen maka matriks primitif juga akan memiliki limit Cesaro.

Teorema 3.19 Matriks nonnegatif tak tereduksi A dengan r = ρ ( A ) primitif jika dan hanya jika lim ( A / r ) k →∞

k

k

pqT ⎛A⎞ ada, dengan lim ⎜ ⎟ = G = T > 0 , dimana k →∞ q p ⎝r ⎠

p dan q adalah vektor Perron untuk A dan A T . G adalah proyektor pada N ( A − rI ) sepanjang R ( A − rI ) .

( r)

Bukti. Berdasarkan Teorema Perron-Frobenius kita tahu bahwa 1 = ρ A

adalah nilai karakteristik simple untuk A . Jelas bahwa A primitif jika dan r hanya jika A

( r)

1= ρ A

primitif. Dengan kata lain, A primitif jika dan hanya jika

r

adalah satu-satunya nilai karakteristik pada lingkaran spektral.

( r ) = 1 jika dan hanya jika

Berdasarkan Teorema 2.26, ρ A

lim ( A / r ) ada. k

k →∞

Selanjutnya, kita akan menunjukkan bahwa G adalah proyektor pada

N ( A − rI )

p ( qT p ) qT

G =

( q p )( q p )

setiap

z

2

R ( A − rI ) .

sepanjang

T

T

=

qT p > 0

Karena

dan

pqT > 0 , maka G adalah proyektor. Hasil peta untuk qT p Gz = α p

adalah

dengan

α=

qT z , qT p

maka

R ( G ) ⊆ span { p} = N ( A − rI ) dan dim ( R ( G ) ) = 1 = dim ( N ( A − rI ) ) , maka R ( G ) = N ( A − rI ) . Misal, N ( G ) = R ( I − G ) dan qT ( A − rI ) = 0 ⇒ qT ( I − G ) = 0 . Jadi, R ( A − rI ) ⊆ R ( I − G ) = N ( G ) ⇒ N ( G ) ⊆ R ( A − rI ) . ⊥

⊥


⊥

51


Selanjutnya perhatikan dimensi dari N ( G ) , yaitu

dim ( N ( G ) ) = n − dim ( R ( G ) ) = n − 1 = n − dim ( N ( A − rI ) ) = dim ( R ( A − rI ) ) , maka N ( G ) = R ( A − rI ) .

Teorema 3.20 berikut ini merupakan teorema pendukung dalam pembuktian Teorema 3.21. Teorema 3.20 Misal A nxn ≥ 0 dengan r = ρ ( A ) . Jika rz ≤ Az untuk z ≥ 0 maka rz = Az dan z > 0 . Bukti. Andaikan rz < Az , maka dengan menggunakan vektor Perron q > 0 untuk A T , maka kita peroleh ( A − rI ) z > 0 ⇒ qT ( A − rI ) z > 0 . Kontradiksi, karena qT ( A − rI ) = 0 . Jadi, haruslah rz = Az dan karena z harus merupakan kelipatan dari vektor Perron untuk A , maka kita peroleh z > 0 .

Berikut ini merupakan dua teorema penting yang ditemukan oleh Helmut Wielandt pada tahun 1950 yang membuktikan bahwa nilai karakteristik pada lingkaran spektral dari matriks imprimitif adalah akar ke- h dari spectral radius-nya. Teorema 3.21 Jika B ≤ A nxn , dimana A adalah matriks tak tereduksi maka

ρ ( B ) ≤ ρ ( A ) . Selanjutnya, ρ ( B ) = ρ ( A ) (yaitu, μ = ρ ( A ) eiφ ∈ ρ ( B ) untuk suatu φ ) jika dan hanya jika B = eiφ DAD−1 , untuk suatu ⎡eiθ1 ⎢ D=⎢ ⎢ ⎢ ⎣

e


iθ 2

⎤ ⎥ ⎥. ⎥ iθ n ⎥ e ⎦

52


Bukti. Berdasarkan Teorema 2.20 sebelumnya, telah ditunjukkan bahwa

ρ (B) ≤ ρ ( A) .

(⇒ )

Jika ρ ( B ) = r = ρ ( A ) , dan jika

B

untuk

(A − B ) ≥ 0

A x =r x

lingkaran ⎡eiθ1 ⎢ D=⎢ ⎢ ⎢ ⎣

dan

μ =r, ⇒

B x =r x .

dan x > 0 . Akibatnya

x > 0 , maka

satuan

e

adalah pasangan karakteristik

dimana

r x = μ x = μ x = Bx ≤ B x ≤ A x Teorema 3.20,

( μ, x )

untuk

Berdasarkan

(A − B ) x = 0,

B = A nxn . Karena xk / xk

xk / xk = eiθk

dan

maka

suatu

tetapi

berada pada

θk .

Tulis

⎤ ⎥ ⎥ dan x = D x . Karena μ = r maka terdapat φ ∈ ℜ ⎥ ⎥ eiθn ⎦

iθ 2

sehingga μ = reiφ . Akibatnya, BD x = Bx = μ x = reiφ x = reiφ D x ⇒ e − iφ D−1BD x = rx = A x . Misalkan,

C = e − iφ D−1BD

maka

C = B =A

sehingga

0 = ( C − C) x .

Perhatikan bagian real dari persamaan tersebut, yaitu 0 = ( C − Re ( C ) ) x . Tetapi, C ≥ Re ( C ) dan x > 0 , maka Re ( C ) = C dan

( )

( )

Re cij = cij = Re cij

2

( )

+ Im cij

2

( )

⇒ Im cij = 0 ⇒ Im ( C ) = 0 .

Akibatnya, C = Re ( C ) = C = A sehingga B = eiφ DAD−1 .

(⇐) Misal B = e φ DA i

−1

D maka ,

BD x = e iφ DA x

⇒

B x = e iφ D r x

⇒

μ x = re iφ x ⇒

μ = re iφ

akibatnya, μ = ρ ( A ) eiφ ∈ ρ ( B ) .


53


Teorema 3.22 Misal A nxn ≥ 0 tak tereduksi dan A memiliki h buah nilai karakteristik pada lingkaran spektral, maka pernyataan berikut benar. (a).

ma ( λk ) = 1 , untuk k = 0,1,..., h − 1 .

(b).

{λ1 , λ2 ,..., λh }

adalah akar ke- h dari r = ρ ( A ) diberikan oleh

{r , rω , rω ..., rω } , dimana ω = e h −1

2

2π i / h

.

Bukti. Misal S = {r , reiθ1 ,..., reiθh−1 } menyatakan himpunan nilai karakteristik pada lingkaran spektral A . Dengan menggunakan Teorema 3.21, dimana

B=A

dan

μ = reiθ , maka terdapat matriks diagonal Dk k

sehingga

A = B = eiθk Dk ADk−1 . Hal ini menunjukkan bahwa eiθk A serupa dengan A . Karena r adalah nilai karakteristik simple untuk A (Teorema Perron Frobenius), maka reiθk adalah nilai karakteristik simple untuk eiθk A . Karena matriks serupa memiliki nilai karakteristik yang sama maka reiθk juga merupakan nilai karakteristik bagi A . Misalkan, A = eiθs Ds AD−s 1 untuk suatu Ds , maka

(

)

A = eiϕk Dk eiθs Ds AD−s 1 D−k 1 = e (

i θ k +θ s )

Dk D s A ( D k D s ) . −1

Akibatnya, rei (θ k +θ s ) juga merupakan nilai karakteristik pada lingkaran spektral

A . Dengan kata lain, S = {r , reiθ1 ,..., reiθh−1 } tertutup terhadap operasi perkalian, artinya R = {1, eiθ1 ,..., eiθh−1 } tertutup terhadap operasi perkalian, sehingga R adalah group komutatif berhingga dengan orde h . Dalam aljabar, pangkat ke- h setiap elemen dalam group berhingga dengan orde h adalah identitas yang merupakan elemen dalam group. Akibatnya,

0 ≤ k ≤ h − 1 . Jadi

S

( 0 ≤ k ≤ h −1) , sehingga

adalah

himpunan

akar

(e ) iθ k

h

=1

semesta

untuk setiap ke- h ,

e 2π ki / h

S adalah akar ke- h dari r .


54


Kita telah mengetahui pada Definisi 3.18 bahwa jika A matriks primitif dan jika G adalah proyektor yang berkorespondensi dengan r = ρ ( A ) , maka

G > 0 . Hal ini berlaku juga untuk matriks imprimitif. Dengan kata lain, jika G adalah proyektor yang berkorespondensi dengan r = ρ ( A ) untuk sebarang matriks nonnegatif tak tereduksi, maka G > 0 .

Teorema 3.23 Misalkan A adalah matriks imprimitif, maka I + ( A r ) +… + ( A r ) lim k →∞ k

k −1

=G,

dimana G adalah proyektor spektral pada N ( A − rI ) sepanjang R ( A − rI ) .

Bukti. Dengan menggunakan Teorema 2.33 mengenai Cesaro Summable untuk

A

r

maka I + ( A r ) +… + ( A r ) k →∞ k

lim

k −1

=G

dimana G adalah proyektor spektral pada N ( ( A r ) − I ) = N ( A − rI ) sepanjang

R ( ( A r ) − I ) = R ( A − rI ) . Karena r adalah nilai karakteistik simple, maka dengan cara yang sama seperti pada Teorema 3.17, kita peroleh bahwa

G=

pqT >0 qT p

dengan p dan q adalah vektor Perron untuk A dan AT .


55

BAB III TEORI PERRON-FROBENIUS

Recommend Documents