BAB II MATRIKS POSITIF. Pada bab ini akan dibahas mengenai Teorema Perron, yaitu teori hasil kontribusi

BAB II MATRIKS POSITIF

Pada bab ini akan dibahas mengenai Teorema Perron, yaitu teori hasil kontribusi dari seorang matematikawan German, Oskar Perron. Perron menerbitkan tulisannya tentang sifat-sifat yang dimiliki oleh matriks positif pada tahun 1907. Teorema Perron ini akan digunakan dalam pembahasan pada Bab III. Sifat-sifat yang akan dibahas antara lain ; Teorema Perron (1907) berdasar pada A.Horn [1], dan Teorema Jordan berdasar pada R.Fletcher [9]. Sebelum membahas mengenai Teorema Perron berikut ini akan dikenalkan notasi yang akan digunakan dalam pembahasan selanjutnya. Misalkan A ∈ Mn (C) dengan entri-entri bilangan kompleks, yaitu A = [aij ] untuk setiap i, j = 1,2,· · · , n dan Mn (C) adalah ruang matriks kompleks n × n. Matriks A disebut matriks positif dinotasikan A > 0, jika untuk setiap elemen dari matriks A bernilai positif . Pada proyek ini notasi |a| menyatakan matriks atau vektor yang entri-entri matriks atau vektornya adalah nilai mutlak entri-entri matriks atau vektor a.

II.1

Matriks Positif

Untuk membahas Teorema Perron akan diawali dengan pembahasan mengenai sifatsifat matriks positif, khususnya untuk matriks persegi. Tujuannya untuk menyelidiki ke arah mana perluasan sifat matriks positif ini diturunkan berdasarkan nilai eigen dan vektor eigen pada matriks A. Pada pembahasan AHP, matriks yang digunakan adalah matriks positif sehingga sifat-sifat yang berlaku dalam matriks positif perlu dikaji terlebih dahulu.

4

5 Definisi II.1.1 Jika A ∈ Mn (C) dan x ∈ Cn pandang persamaan Ax = λx, x 6= 0, dengan λ ∈ C. Skalar λ disebut nilai eigen matriks A dan x disebut vektor eigen yang berkorespondensi dengan λ. Definisi II.1.2 Misalkan A ∈ Mn (C). Himpunan semua nilai eigen A disebut spektrum A, dinotasikan σ(A). Spektral radius dari matriks A adalah ρ(A) = max{|λ| : λ ∈ σ(A)}, Spektral radius dinotasikan ρ(A) merupakan lingkaran terkecil dalam bidang kompleks yang memuat semua nilai eigen dari matriks A. Akibat II.1.1 Misalkan A ∈ Mn (C), x ∈ Rn , x > 0 dan A ≥ 0, pernyataan di bawah ini benar. • Jika α, β ≥ 0 sehingga αx ≤ Ax ≤ βx, maka α ≤ ρ(A) ≤ β. • Jika αx ≤ Ax, maka α < ρ(A). • Jika Ax < βx, maka ρ(A) < β. Untuk bukti Akibat II.1.1, dapat di lihat di A.Horn [1] Lema II.1.1 Misalkan A ∈ Mn (C) dengan A > 0. Jika Ax = λx, untuk x ∈ Cn , λ ∈ R, x 6= 0, dan |λ| = ρ(A), maka A|x| = ρ(A)|x| dan |x| > 0. Bukti: Perhatikan bahwa

ρ(A)|x| = |λ||x| = |λx| = |Ax| ≤ |A||x| = A|x|.

Misalkan y = A|x| − ρ(A)|x| ≥ 0. Karena |x| ≥ 0 dan |x| = 6 0 diperoleh A|x| > 0. Untuk kasus y = 0 didapat

A|x| = ρ(A)|x| |x| = ρ(A)−1 A|x| > 0

6 Untuk kasus y 6= 0, terlebih dahulu definisikan z = A|x| > 0 sehingga

0 < y = Az − ρ(A)z

berarti Az > ρ(A)z. Berdasar Akibat II.1.1 didapat ρ(A) > ρ(A). Hal ini tidak mungkin. Haruslah y = 0 sehingga kesimpulannya |x| > 0.

2

Teorema II.1.2 Misalkan A ∈ Mn (C) dan A > 0, dan ρ(A) > 0, maka terdapat vektor positif x ∈ Cn sehingga Ax = ρ(A)x Bukti: Terdapat λ dengan |λ| = ρ(A) > 0 berdasar Definisi II.1.2 dan bersesuaian dengan vektor eigen x 6= 0. Dari Lema II.1.1 vektor tersebut adalah |x|.

2

Lema II.1.3 Misalkan A ∈ Mn (C) dan A > 0. Jika Ax = λx, x 6= 0, dan |λ| = ρ(A), maka untuk suatu θ ∈ R, e−iθ x = |x| > 0, Bukti: Berdasarkan hipotesis diperoleh |Ax| = |λx| = ρ(A)|x|, berdasarkan Lema II.1.1 diperoleh A|x| = ρ(A)|x| dan |x| > 0. Perhatikan bahwa untuk setiap k = 1, · · · , n, berlaku

ρ(A)|xk | = |λ||xk | = |λxk | = |

n X

akp xp |

p=1

≤

n X p=1

|akp ||xp | =

n X

(2.1)

|akp ||xp | = ρ(A)|xp | = ρ(A)|xk |

p=1

Dengan demikian, ketaksamaan (2.1) mengakibatkan bilangan kompleks tak nol akp xp , p = 1, ..., n semuanya harus terletak dalam satu garis di bidang kompleks. Selanjutnya, tulis e−iθ akp xp > 0 untuk semua p = 1, · · · , n dan untuk suatu θ ∈ R. Karena akp > 0, kita dapatkan e−iθ xp > 0.

2

7 Teorema II.1.4 Misalkan A ∈ Mn (C), A > 0, dan λ ∈ σ(A) , maka |λ| < ρ(A), untuk setiap nilai eigen λ 6= ρ(A). Bukti: Berdasar Definisi II.1.2, |λ| ≤ ρ(A) untuk semua nilai eigen λ dari A. Selanjutnya untuk kasus |λ| = ρ(A) dan Ax = λx, x 6= 0, berdasarkan Lema II.1.3 terdapat |x| = e−iθ x > 0, untuk suatu θ ∈ R. Dengan demikian

ρ(A)|x| = A|x| = Ae−iθ x = e−iθ Ax = e−iθ λx = λe−iθ x = λ|x|

Akibatnya diperoleh λ = ρ(A).

2

Teorema II.1.5 Misalkan A ∈ Mn (C) dengan A > 0, w dan z adalah vektor-vektor tak nol di C sehingga Aw = ρ(A)w dan Az = ρ(A)z, maka terdapat suatu α ∈ C sehingga w = αz. Bukti: Berdasarkan Lema II.1.3 terdapat bilangan real θ1 dan θ2 sehingga p = e−iθ1 z > 0

q = e−1iθ2 w > 0

8 Tulis

β = min1≤i≤n

qi , pi

dengan qi adalah entri ke-i dari vektor q dan pi adalah entri ke-i dari vektor p

Definisikan pula

r = q − βp

dengan r, p, q adalah vektor ∈ C.

Diperoleh r ≥ 0 dan paling sedikit satu koordinat dari r adalah 0, ini berarti r bukan merupakan vektor positif, selanjutnya pandang

Ar = Aq − βAp = ρ(A)q − βρ(A)p = ρ(A)(q − βp) = ρ(A)r

Andaikan r 6= 0, maka Ar = ρ(A)r > 0, sehingga r = ρ(A)−1 Ar > 0. Karena kondisi ini tidak benar maka haruslah r = 0. Dengan demikian :

q = βp e−1iθ2 w = βe−iθ1 z w = βeiθ2 −iθ1 z = βei(θ2 −θ1 ) z = αz,

(dengan α = βei(θ2 −θ1 ) )

2

9 Akibat II.1.6 Misalkan A ∈ Mn (C) dan misalkan pula A > 0,maka terdapat vektor P tunggal x ∈ Cn sehingga Ax = ρ(A)x, x > 0, dan |x|1 = ni=1 xi = 1 Bukti: Misalkan x1 dan x2 adalah vektor-vektor yang memenuhi

Ax = ρ(A)x, x > 0, |x|1 =

n X

xi = 1

(2.2)

i=1

Berdasarkan Teorema II.1.5 x2 > 0 maka α > 0,

x1 = αx2 ,

untuk suatu α ∈ C. Karena x1 > 0 dan

|x1 |1 = |x2 |1 = 1.

Dengan demikian

|x1 |1 = α|x2 |1 |x1 |1 = |x2 |1 ,

untuk α = 1

sehingga x1 = x2 . Jadi, terbukti bahwa x yang memenuhi persamaan (2.2) adalah 2

tunggal.

Lema II.1.7 Misalkan A ∈ Mn (C), A > 0, λ ∈ C dan x, y ∈ C. • Jika L = xy T dan berlaku ; (1.) Ax = λx (2.) AT y = λy (3.) xT y = 1 maka (a.) Lx = x dan y T L = y T (b.) Lm = L untuk setiap m = 1, 2, ... (c.) Am L = LAm = λm L untuk setiap m = 1,2,...

10 (d.) L(A − λL) = 0 (e.) (A − λL)n = Am − λm L untuk setiap m =1,2,... dan (f.) semua nilai eigen tak nol dari A − λL, merupakan nilai eigen dari A. Jika diberikan asumsi tambahan (4.) λ 6= 0 (5.) λ adalah nilai eigen dari A dengan multiplisitas geometri 1, maka ; (g.) λ merupakan nilai eigen dari A − λL. Jika kita asumsikan bahwa (6.) |λ| = ρ(A) > 0; (7.) λ merupakan satu-satunya nilai eigen dari A dengan modulus ρ(A), dan jika |λ1 | ≤ |λ2 | ≤ · · · ≤ |λn−1 | < |λn | = |λ| = ρ(A), maka: (h.) ρ(A − λL) ≤ |λn−1 | < ρ(A); (i.) (λ−1 A)m = L + (λ−1 A − L)m → L untuk m → ∞; dan n−1 | (j.) untuk setiap r ∈ C sehingga [ |λρ(A) ]
C(r, A) sehingga |(λ−1 A)m − L|∞ < Crm untuk semua m = 1,2,... Bukti: (a.) Perhatikan bahwa xT y = 1. Dengan mengalikan kedua ruas dengan xT diperoleh

xT yxT = xT xy T x = x Lx = x

11 Selanjutnya dari asumsi (3) kalikan kedua ruas dengan y sehingga didapat

yxT y = y y T xy T = y T yT L = yT

Jadi terbukti bahwa Lx = x dan y T L = y T . (b.) Akan dibuktikan Lm = L untuk setiap m= 1,2,... dengan menggunakan induksi matematika. Untuk m = 1 jelas benar. Selanjutnya kita misalkan benar untuk m = n, akan dibuktikan benar juga untuk m = n + 1. Perhatikan bahwa :

Ln+1 = Ln L = LL = (xy T )L = xy T xy T = x(y T L) = xy T = L.

Jadi terbukti bahwa Lm = L untuk setiap m = 1,2,... (c.) Untuk membuktikan Am L = LAm = λm L untuk setiap m= 1,2,..., cukup dibuktikan : Am L = λm dan LAm = λm L.

12 • Am L = λ m L Untuk m = 1, didapat

AL = Axy T = λxy T = λL

Selanjutnya asumsikan benar untuk m = n, yaitu An L = λn L. Akan dibuktikan benar untuk m = n + 1, yaitu:

An+1 L = An AL = An λL = λAn L = λλn L = λn+1 L.

Jadi terbukti bahwa Am L = λm L untuk setiap m = 1, 2, · · · . Dengan cara yang sama dapat dibuktikan LAm = λm L untuk setiap m = 1, 2, · · · ,. Dengan demikian Am L = λm L dan LAm = λm L untuk setiap m = 1, 2, · · · . Dapat disimpulkan bahwa Am L = LAm = λm L. (d.) Akan dibuktikan bahwa L(A − λL) = 0. Dengan memperhatikan hasil (b) dan (c), maka

L(A − λL) = LA − λL2 = LA − λL = λL − λL = 0.

Jadi L(A − λL) = 0. (e.) Akan dibuktikan (A − λL)m = Am − λm L, untuk setiap m = 1, 2, · · · dengan induksi matematika. Jelas untuk m = 1 pernyataan benar. Asumsikan benar

13 untuk m = n, akan dibuktikan benar untuk m = n + 1.

(A − λL)n+1 = (A − λL)n (A − λL) = (An − λn L)(A − λL) = An+1 − λLAn − λn LA + λn+1 L2 = An+1 − λλn L − λn λL + λn+1 L = An+1 − 2λn+1 L + λn+1 L = An+1 − λn+1 L.

Dengan demikian terbukti bahwa (A − λL)n = Am − λm L, untuk setiap m = 1, 2, · · · . (f.) Akan dibuktikan bahwa untuk setiap nilai eigen tak nol dari (A − λL) juga merupakan nilai eigen dari A. Misalkan µ 6= 0, nilai eigen dari (A − λL), w 6= 0 adalah vektor eigen yang bersesuaian dengan µ, sehingga (A − λL)w = µw. Perhatikan bahwa : 1 Lw = L( )(A − λL)w µ 1 = L(A − λL)w µ 1 = .0 µ = 0.

Diperoleh (A − λL)w = Aw − λLw = Aw − λ(0) = Aw = µw. Jadi terbukti bahwa µ adalah nilai eigen dari A. (g). Ambil µ = λ. Andaikan w adalah vektor eigen dari (A − λI) yang berko-

14 respondensi dengan nilai eigen λ, maka berdasarkan (f), w juga merupakan vektor eigen yang berkorespondensi dengan nilai eigen λ dari A. Misalkan w = αx,untuk α 6= 0 diperoleh

(A − λL)w = λw = (A − λL)αx = αAx − αλLx = αλx − αλx =0

Jadi λw = 0, yang berarti λ = 0 atau w = 0. Padahal λ 6= 0 dan w 6= 0 jadi kontradiksi, maka λ bukan merupakan nilai karakteristik dari (A − λL). (h). Untuk ρ(A − λL) = 0, jelas berlaku:

0 = ρ(A − λL) ≤ |λn−1 | < ρ(A).

Selanjutnya berdasar (f) perhatikan bahwa untuk ρ(A − λL) 6= 0, terdapat nilai eigen sebut µ 6= 0 sehingga ρ(A − λL) = |µ| = |λk |, untuk suatu k < n. Dengan demikian ρ(A − λL) = |λk | ≤ |λn−1 | < |λn | = |λ| = ρ(A). Jadi

ρ(A − λL) ≤ |λn−1 | < ρ(A).

(i). Berdasar (e) didapatkan

(λ−1 A)m = L + (λ−1 A − L)m .

15 Selanjutnya dengan memperhatikan (h) pandang A − λL ) λ ρ(A − λL) = ρ(A) |λn−1 | ≤ ρ(A) ρ(A) = 1. < ρ(A)

ρ(λ−1 A − L) = ρ(

Dengan demikian (λ−1 A)m = L+(λ−1 A−L)m → L untuk m → ∞.

2

Dari Lema II.1.7 dapat disimpulkan Teorema II.1.8 berikut yang nantinya akan digunakan untuk membuktikan bahwa ρ(A) adalah akar sederhana dari A pada Teorema Perron. Teorema II.1.8 Misalkan A ∈ Mn (C) dan A > 0, asumsikan (1)-(7) dari Lema II.1.7 terpenuhi, maka limm→∞ [ρ(A)−1 A]m = L, dengan L = xy T , Ax = ρ(A)x, AT y = ρ(A)y, untuk suatu x, y ∈ Cn , x > 0, y > 0, dan xT y = 1 . Teorema II.1.9 Jika A ∈ Mn (C), maka terdapat matriks nonsingular S ∈ Mn (C) sehingga A = S −1 BS dengan B merupakan bentuk normal Jordan yaitu;      B=   

0 .. .

··· . J2 . . .. .. . .

0

···

J1

0

0

0 .. .



    , 0    Jk

     Ji =    

1 .. .

··· .. . λi .. .. . .

0

···

λi

0

1

0 .. .



     0    λi

λi merupakan nilai eigen yang bersesuaian dengan A, i = 1, 2, · · · , k

16 Untuk membuktikan Teorema II.1.9 diperlukan beberapa teorema berikut ini : Teorema II.1.10 (Teorema Schur) Misalkan A ∈ Mn (C), maka terdapat matriks uniter Q ∈ Mn dan matriks segitiga atas R ∈ Mn sehingga Q∗ BQ = R

dengan diagonal entri dari R adalah sama dengan nilai eigen A. Bukti: Untuk membuktikan Teorema Schur melalui induksi matematika terhadap n. Karena pernyataan ini benar untuk n = 1, akan ditunjukkan jika pernyataan benar untuk n = r − 1 maka pernyataan juga benar untuk n = r. Asumsikan pernyataan berlaku untuk sembarang matriks berukuran n − 1 ≥ 1, dan misalkan A berukuran n. Misalkan λ adalah satu dari nilai eigen A yang berkorespondensi dengan vektor eigen u1 . Jika ku1 k = 6 1, bentuk v1 =

u1 ku1 k

dan perhatikan bahwa λ merupakan nilai eigen

A yang berkorespondensi dengan v1 juga. Dari sini dapat kita asumsikan bahwa ku1 k = 1. Sekarang kita perluas u1 sehingga u1 , u2 , · · · , un adalah basis di Cn dan dengan proses Gram-Schmidt asumsikan basis tersebut ortonormal. Selanjutnya, definisikan U = [u1 , u2 , · · · , un ]. Karena kolom-kolom U saling ortogonal, maka U ∗ U = I, karenanya U −1 = U ∗ , dengan demikian U adalah matriks

17 uniter.      U ∗ AU =          =      =

u∗1



     Au1 Au2 · · · Aun ..  .    u∗n  u∗1    u∗2   λu1 λu2 · · · λun ..  .    u∗n  λ cT   0 B u∗2

dengan vektor 0, c ∈ Cn−1 mempunyai n − 1 entri dan B ∈ Mn−1 . Berdasarkan pernyataan induksi bahwa terdapat matriks uniter V sehingga V ∗ BV = R1 , dengan R1 adalah matriks segitiga atas. Definisikan W ∈ Mn (C), dimana 



T  1 c  W = , 0 V

jelas W adalah uniter.

18 Perhatikan bahwa

(U W )∗ A(U W ) = W ∗ U ∗ AU W = W ∗ (U ∗ AU )W  ∗    T T T  1 c   λ c  1 c  =     0 V 0 B 0 V   T  λ c V  = . 0 R1



 T

 λ c V  =  0 V ∗ BV

Dengan demikian dapat disimpulkan bahwa pernyataan benar untuk semua n, yaitu terdapat matriks uniter Q = U W sedemikian sehingga Q∗ AQ adalah matriks segitiga atas. Selanjutnya dengan memperhatikan

det(λI − R) = det(λI − U ∗ AU ) = det(U ∗ (λI − A)U ) = det(U ∗ )det(λI − A)det(U ) = det(λI − A),

dapat disimpulkan bahwa R dan A mempunyai nilai eigen yang sama.

2

Lema II.1.11 Misalkan R ∈ Cn×n matriks segitiga atas. Maka ada sebuah matriks nonsingular X ∈ Cn×n sehingga

X −1 RX = diag(R1 , R2 , · · · Rm ),

(2.3)

dengan R1 = λj I+Uj ,untuk j = 1, 2, ..., m dengan masing-masing Uj matriks segitiga atas sejati dan masing-masing λj berbeda. Bukti: Pembuktiannya dengan induksi matematika : Untuk n = 1 jelas benar.

19 Misalkan benar untuk matriks segitiga atas dengan orde lebih kecil dari n. Misalkan R ∈ Cn×n segitiga atas. Dengan dekomposisi Schur matriks umum dapat diperoleh dengan nilai eigen dalam sembarang order yang diberikan. Sehingga tanpa mengurangi keumuman bahwa 



 R1 S  R=  0 R2 dengan R1 dan R2 tidak mempunyai nilai eigen yang sama, dan R1 = λ1 I+U1 dengan U1 segitiga atas sejati. Sekarang ada matriks B dengan dimensi yang memenuhi 











 I B   R1 S   I −B   R1 0  ,    = 0 R2 0 I 0 R2 0 I jika dan hanya jika

S = R1 B − BR2 .

2

(2.4)

Persamaan matriks (2.4) mempunyai solusi tunggal B karena λ(R1 ) ∩ λ(R2 ) = ∅ seperti yang dinyatakan oleh lema berikut. Lema II.1.12 Misalkan R1 dan R2 berturut-turut adalah matriks segitiga atas dalam Ck1 ×k1 dan Ck2 ×k2 , dan misalkan S ∈ Ck1 ×k2 , maka persamaan matriks

R1 B − BR2 = S,

20 mempunyai solusi tunggal B ∈ Ck1 ×k2 jika dan hanya jika

λ(R1 ) ∩ λ(R2 ) = ∅.

Bukti: Pembuktian dengan induksi matematika. i . Untuk k1 , k2 = n = 1 jelas benar , yaitu λ1 (B) − (B)λ2 = σ1 ii . Misalkan lema benar untuk k1 , k2 ≤ n = k−1. Selanjutnya akan ditunjukkan lema benar untuk k1 , k2 = n = k. Perhatikan bahwa persamaan R1 B − BR2 S dapat ditulis sebagai 















T T T T T  λ1 r1   B b   B b   λ2 r2   σ1 s1  = −         ˆ2 ˆ ˆ ˆ1 s2 Sˆ 0 R w B w B 0 R

diperoleh  r1T w

 λ1 B +  ˆ1w R Jadi ,

T

λ1 b +

ˆ r1T B

ˆ1B ˆ R



b. (λ1 − λ2 )B = σ1 − r1T w ˆ 2 ) = sT1 − r1T B ˆ c. bT (λ1 − R ˆ1B ˆ −B ˆR ˆ 2 = Sˆ + wr2T . d. R

Br2T

T





ˆ2 +b R   σ1   Bλ2 = − T ˆ ˆ s2 wλ2 wr2 + B R2

ˆ 1 − λ2 )w = s2 a. (R

Jika λ(R1 ) ∩ λ(R2 ) = ∅ maka :





sT1 Sˆ

 .

21 (a). dari persamaan (λ1 − λ2 )β = σ1 − r1T w karena λ1 ∈ λ(R1 ), λ2 ∈ λ(R2 ) dan λ(R1 ) ∩ λ(R2 )=∅, yang berakibat λ1 6= λ2 , ini berarti β tunggal. (b). (R1 − λ2 I)w = s2 karena λ1 ∈ λ(R1 ), λ2 ∈ λ(R2 ) dan λ(R1 ) ∩ λ(R2 )=∅, akibatnya w tunggal. (c). bT (λ1 I − R2 ) = sT1 + βr2T − r1T B karena λ1 ∈ λ(R1 ), λ2 ∈ λ(R2 ) dan λ(R1 ) ∩ λ(R2 )=∅, akibatnya bT tunggal. ˆ 1 ) ⊆ λ(R1 ); λ(R ˆ 2 ) ⊆ λ(R2 ) dan λ(R1 ) ∩ λ(R2 ) = ∅ ˆ1B ˆ −B ˆR ˆ 2 = Sˆ + wrT . λ(R (d). R 2 ˆ 1 )∩λ(R ˆ 2 ) = ∅. Dengan demikian persamaan matriks (d) tersebut sehingga λ(R mempunyai solusi tunggal. Sebaliknya misalkan R1 B − BR2 = S mempunyai jawab tunggal. Perhatikan bahwa

ˆ 1 ) ∪ λ1 λ(R1 ) = λ(R

dan

ˆ 2 ) ∪ λ2 . λ(R2 ) = λ(R

ˆ 1 ) ∩ λ(R ˆ 2 ) = ∅. Dari (a) λ1 6= λ2 , akibatnya λ1 6∈λ(R2 ), dan Dari (d) diperoleh λ(R λ2 6∈λ(R1 ). Sehingga didapatkan λ(R1 ) ∩ λ(R2 ) = ∅.

2

Lema II.1.11 menjamin bahwa matriks segitiga pada Lema II.1.12 akan serupa dengan matriks bentuk (2.3). Selanjutnya akan dibahas mengenai blok Jordan.

22 Lema II.1.13 Misalkan k ≥ 1, dan memperhatikan blok Jordan      Jk (0) =    

maka



0 1 ··· . 0 0 .. .. .. . . . . .

0 .. .



     1    0 0 ··· 0



 0 0  p JkT (0)Jk (0) =   dan Jk (0) = 0 jika 0 Ik−1 Lebih lanjut , jika Jk (0)ei+1 = ei , untuk

p ≥ k.

i = 1, 2, · · · , n − 1 dan I − JkT (0)Jk (0)x =

(xT e1 )e1 dimana Ik−1 adalah matriks identitas ei adalah vektor basis baku ke i , dan x ∈ Cn . Kajian tentang Lema II.1.13 dapat dilihat pada A.Horn [1]. Kemudian akan dicari matriks yang serupa dengan bentuk matriks dalam Teorema II.1.9, yaitu melalui teorema berikut. Teorema II.1.14 Misalkan A ∈ Mn (C) adalah matriks segitiga atas sejati, maka terdapat matriks nonsingular S ∈ Mn (C) dan bilangan bulat n1 , n2 , · · · , nm dengan n1 ≥ n2 ≥ · · · ≥ nm ≥ 1 dan n1 + n2 + · · · + nm = n sehingga berlaku; 

0 ··· 0  Jn1 (0)  .. .  0 Jn2 (0) . . .  A=S .. .. ..  . . . 0   0 ··· 0 Jnm (0)

     −1 S   

(2.5)

23 Bukti: Teorema akan dibuktikan dengan menggunakan induksi matematika pada n. Jika n = 1 jelas A = (0) sehingga teorema benar untuk n = 1. Selanjutnya asumsikan teorema benar untuk n = k − 1 dan akan dibuktikan teorema juga benar untuk matriks berukuran n = k. Untuk A ∈ Mn (C) partisi A sedemikian rupa sehingga 

 T

 0 a  A= , 0 A1 dengan a ∈ Cn−1 , dan A1 ∈ Mn−1 (C) adalah matriks segitiga atas sejati. Berdasarkan pernyataan induksi, terdapat matriks nonsingular S1 ∈ Mn−1 sehingga      −1 S 1 A1 S 1 =    

Jk1 0 .. . 0

0

··· ...

0 .. .



     J k2   Jk1 0  =  .. .. . 0  . 0 J   · · · 0 Jkn

(2.6)

dengan k1 ≥ k2 ≥ · · · ≥ kn ≥ 1 , k1 + k2 + · · · + kn = n − 1, Jk1 = Jk1 (0) dan 



0  J k2  ...    0 Jks

   ∈ Mn−1−k1 .  

Perhatikan bahwa tidak ada diagonal blok Jordan dalam J yang mempunyai order lebih dari k1 , dengan demikian berdasarkan Lema II.1.13 J k1 = 0.

24 Selanjutnya 















T

 1 0   1 0   1 0  0 a  1 0   A =    0 S1−1 0 S1 0 S1−1 0 A1 0 S1   T a S1   0 =  0 S1−1 A1 S1

T

Partisi a S1 =



 aT1 aT2

, dengan a1 ∈ C1k1 dan a2 ∈ C n−1−k1 sehingga 

aT1

 0 T 0 a S 1     =  0 Jk1 −1  0 S 1 A1 S 1 0 0 



aT2



  0    J

karena (I − JkT1 Jk1 )a = (aT e1 )e1 . Perhatikan kesamaan matriks berikut;   1   0   0

−aT1 JkT1 I 0

 0  0   0   0  I 0

aT1 JkT1 Jk1 0

aT2



 1   0   0  J 0

aT1 JkT1 I 0





T

JkT1 Jk1 )

aT2

0   0 a (I −    0  J k1 0 = 0   I 0 0 J   T T  0 (a e1 )e1 a2    = J k1 0   0 .   0 0 J (2.7)

     

25 Dengan demikian terdapat dua kemungkinan yaitu; aT1 e1 = 0 atau aT1 e1 6= 0. Untuk kasus : aT1 e1 6= 0, maka      

1 aT 1 e1

0 0



T

  0 (a e1 )e1   Jk1 I 0   0  0 0 0 aT1e1 I 0

0



aT2

   0    J

aT1 e1 0 0

1



 0



0

  0 e1    I 0   =  0 J k1   0 aT1 e1 I 0 0  T ˜  J e1 a2 = 0 J

aT2



  0    J   

 eT1

 0  dengan J˜ =   = Jk1 +1(0) adalah blok Jordan order k1 + 1 dengan dia0 Jk1 ˜ i+1 untuk i = gonal utama adalah nol. Selanjutnya dengan menggunakan sifat Je 1, 2, · · · , k1 maka  I  0

e2 aT2 I

˜  J  0









e1 aT2 J

 I  0

e2 aT2 I



˜ 2 aT Je 2

˜   J = 0  T ˜  J e2 a2 J = 0 J

 +

e1 aT2 J

+

e2 aT2 J

 

  .

Secara rekursif perhitungan dilanjutkan; 











T i−1 T i−1 T i−1 T i ˜ ˜  I ei+1 a2 J   J ei a2 J   I −ei+1 a2 J   J ei+1 a2 J     =  0 I 0 I 0 I 0 J

dengan i = 2, 3, · · · .

26 Karena Jk1 = 0, maka dapat kita simpulkan bahwa A serupa dengan matriks  ˜  J 0    yang merupakan matriks Jordan segitiga atas sejati. 0 J   T  0 0 a2     Selanjutnya Untuk kasus aT1 e1 = 0, maka persamaan (2.7) menjadi  0 J 0 k   1   0 0 J dengan permutasi yang serupa diperoleh ; 



 0 I 0  0 0    I 0 0  0 J k1     0 0 I 0 0

aT2









  0 I 0   J k1 0 0       I 0 0  =  0 0 aT  . 0     2      J 0 0 I 0 J

(2.8)

Berdasar pernyataan induksi terdapat matriks nonsingular S2 ∈ Mn−k1 sehingga 

  0 S2−1  0

aT2 J

  S2 = J˜ ∈ Mn−k1

adalah matriks Jordan dengan diagonalutama nol.  Dengan demikian matriks ruas  Jk1 0  kanan persamaan (2.8) serupa dengan  . 0 J˜ Dari Lema II.1.11 berakibat untuk setiap blok segitiga serupa dengan bentuk matriks Teorema II.1.9. Karena untuk setiap blok diagonal Ri terdapat matriks nonsingular Xi sehingga Xi−1 (λI + Ui )Xi = λi I + diag(E1 , E2 , · · · , Em ).

2

27 Lebih lanjut tentang Lema II.1.11 sampai dengan Lema II.1.13 dapat dikaji pada R. Fletcher [9]. Setelah kita bahas mengenai bentuk Jordan berikut akan dibahas tentang

L = lim [ρ(A)−1 A]m m→∞

sebagai akibat dari Teorema II.1.8. Akibat II.1.15 Jika A ∈ Mn (C) dan A > 0, maka L = limm→∞ [ρ(A)−1 A]m adalah matriks positif dengan rank 1. Bukti: Misalkan

L = lim (ρ(A)−1 A)m m→∞

Berdasar Teorema II.1.9 terdapat matriks nonsingular S sehingga: 

L = lim (ρ(A)−1 S −1 JS)m m→∞

     dengan J =      

λ1

1

0

···

0

λ2

1

0 .. .

0 .. .

λ3 .. .

··· .. . .. .

0

0

0

···

0



  0    0     1   λn

28 L = S −1 lim (ρ(A)−1 J)m S m→∞    1 0 ··· 0     0 0 ··· 0    = S −1  . .  S.  .. .. . . . 0      0 0 ··· 0

2

Jadi, rang dari L = limm→∞ (ρ(A)−1 A)m adalah 1. Teorema II.1.16 Jika A ∈ Mn (C), dan A > 0, maka ρ(A) adalah nilai eigen dengan multiplisitas aljabar 1; yaitu ρ(A) adalah akar simpel dari persamaan karakteristik PA (t) = 0. Bukti: Berdasarkan Teorema II.1.10 dapat ditulis bahwa A = U ∗ 4U , dengan U adalah unitary, 4 adalah matriks segitiga atas dengan entri-entri diagonal utamanya : ρ, · · · , ρ, λk+1 , · · · , λn , dan ρ = ρ(A) adalah nilai eigen dengan multiplisitas aljabar k ≥ 1, semua nilai eigen λi mempunyai modulus kurang dari pada ρ(A), untuk semua i = k + 1, · · · , n. Tetapi dari Teorema II.1.8

L = lim [ρ(A)−1 A]m m→∞

= lim [ρ(A)−m U ∗ 4U ] m→∞   ρ  ..  .     ρ −m ∗  = lim ρ(A) U  m→∞  λk+1   ...  0  

m   ∗       U        λn

29 

 ρ       −m ∗  L = lim ρ(A) U  m→∞     0   



m

... ρm λm k+1

ρm

 ρm       ∗ = lim U  m→∞     0  

..

. ρm ρm λm k+1 ρm

...

  ∗      U     ..  .   λm n 

  ∗       U.        m

λn ρm

Untuk m → ∞ maka didapat: 



  1   .   .. ∗         1 ∗  U. L=U     0     .   0 ..     0

Berdasarkan Akibat II.1.15, karena matriks segitiga atas pada penyajian terakhir mempunyai rank = k, sedangkan L sendiri mempunyai rank 1. Hal ini berarti k=1 maka haruslah multiplisitas aljabarnya 1.

2

30 Berdasarkan uraian yang telah disebutkan di atas tentang sifat-sifat matriks positif, berikut ini merupakan rangkuman sifat-sifat tersebut yang dikenal dengan 1907). Dalam Teorema Perron ρ(A) merupakan nilai eigen terbesar pada matriks A. Hal ini sebagai dasar pada AHP yaitu λmaks merupakan nilai eigen terbesar pada matriks perbandingan berpasangan.

Teorema II.1.17 (Teorema Perron) Misalkan A ∈ Mn×n (C), A > 0, maka pernyataan berikut benar: 1. ρ := ρ(A) > 0 2. ρ(A) adalah nilai eigen A 3. Terdapat x ∈ Cn dengan x > 0 dan Ax = ρ(A)x; 4. ρ(A) merupakan akar sederhana dari A,yaitu ma(ρ(A)) = 1 5. |λ| < ρ(A) untuk setiap nilai eigen λ 6= ρ(A); 6. [ρ(A)−1 A]m → L, m → ∞, dimana L = xy T , Ax = ρ(A)x, AT y = ρ(A)y, x > 0, y > 0, dan xT y = 1. Teorema II.1.17 ini sebagai dasar dalam pembahasan pada bab III, terutama bagian (1) sampai bagian (4). Untuk bagian (4) akan digunakan dalam pembuktian bahwa vektor singular kiri dan kanan u dan v pada dekomposisi nilai singular adalah positif.