Himpunan Spektrum Real Untuk Masalah Balikan Nilai Eigen Dari Matriks Tak Negatif
Andi Kresna Jaya †

## Abstrak
Pada  paper  ini  akan  dibahas  representasi  geometri  dari  himpunan  spektrum  nilai  eigen real  yang  nilai  eigen  maksimalnya  1  untuk  masalah  balikan  nilai  eigen  ( invers eigenvalues  problem ).  Untuk  menunjukkan  representasi  tersebut  akan  digunakan  sifat invarian  dari  jumlah  konveks  matriks  stokastik  terhadap  jumlah  konveks  spektrum matriks stokastik tersebut. Representasi geometri yang diperoleh hanya pada R n untuk n
=  2,  3  dan  4.  Sifat  invariant  di  atas  juga  akan  digunakan  untuk  menunjukkan  bahwa sebuah  spektrum  matriks  tak  negatif  ditulis  dalam  bentuk  vektor
) ,..., , , 1 ( 3 2 n    ,
maka   n t t t    ,..., , , 1 3 2 merupakan  spektrum  dari  sebuah  matriks  positif  untuk
  1 , 0  t .
Keywords: Spektrum, matriks tak negatif, matriks stokastik, jumlah konveks.

## 1.  Pendahuluan
Misalkan sebuah vektor  =   n    ,..., , 2 1 , maka  yang dimaksud dengan masalah balikan  nilai  eigen  ( invers  eigenvalue  problem )  adalah  mencari  beberapa  syarat  perlu  dan cukup agar vektor tersebut dapat dipandang sebagai spektrum atau kumpulan nilai eigen dari sebuah matriks tak negatif [1, 2, 3, 4, 7]. Dalam banyak literatur mengenai masalah balikan nilai eigen ini, para ahli telah mengemukakan syarat perlu dan cukup agar sebuah vektor real dapat  dipandang  sebagai  spektrum  matriks  tak  negatif  walaupun  peninjauan  tersebut  hanya bersifat  kasus-kasus  khusus  [2,  3,  4].    Namun  untuk  vektor  real  berdimensi n =  2,  3,  syarat perlu dan cukup itu telah diberikan [10].
Teorema  utama  dari  matriks  tak  negatif  dan  nilai  eigennya  adalah  Teorema  Perron- Frobenius [6,10] yang menyatakan bahwa jika A matriks ordo n tak negatif dan tak tereduksi, maka A mempunyai nilai eigen  sedemikian sehingga setiap nilai eigen i  untuk i = 1, 2, …, n dari A berlaku i    ,  vektor  karakeristik  untuk  adalah  vektor  positif,  dan multiplisitas  aljabarnya  adalah  1.  Nilai  eigen  yang  demikian  ini  disebut  nilai  eigen maksimal A .  Pengertian  matriks  tereduksi  sendiri  diberikan  di  [10],  yaitu  matriks  ordo n.  A disebut tereduksi jika terdapat matriks permutasi P sedemikian sehingga berlaku
P D C B P A T        0
dengan B dan D adalah  sub  matriks  bujur  sangkar.  Matriks A dikatakan  tak  tereduksi  jika tidak terdapat matriks permutasi P .
Pembahasan  pada  makalah  ini  memberikan  bukti  positif  untuk  sebuah  problem terbuka  ( open  problem )  pada  [8],  dengan  terlebih  dahulu  menjelaskan  beberapa  teorema mengenai  matriks  tak  negatif  dan  masalah  balikan  nilai  eigen.  Untuk  menunjukkan  secara
† Staf Pengajar pada Jurusan Matematika FMIPA Universitas Hasanuddin Makassar

## Andi Kresna Jaya
lengkap,  akan  ditinjau  pada  matriks  yang  sifatnya  tereduksi  dan tak  tereduksi  untuk  matriks stokastik [10], dan sifat invarian jumlah konveksnya. Kemudian di bagian terakhir diberikan representasi geometri khusus pada spektrum real dari matriks tak negatif berorde n = 2, 3 dan 4. Misalkan N n × n menyatakan himpunan matriks tak negative, dan P n × n menyatakan himpunan matriks  positif.  Untuk  menyederhanakan  persoalan,  spektrum  real  dari  matriks  tak  negatif dapat dipandang sebagai himpunan bagian dari ruang R n sebagai berikut
  
        
        n nxn n n n n nxn n n n i n n n A P A Z P A N A Z N n i R Z                   ,..., , , 1 :
,..., , , 1
, ,..., , , 1 :
,..., , , 1 , ,..., 3 , 2 1 : ,..., , , 1 3 2 3 2 3 2 3 2 3 2                 
dengan  ( A ) adalah spektrum real matriks A .

## 2. Matriks Stokastik
Suatu matriks bujursangkar tak negatif disebut matriks stokastik jika jumlah entri- entri setiap barisnya adalah 1.
Teorema 2.1. Jika A matriks stokastik orde n, maka berlaku pernyataan-pernyataan berikut:
a. Nilai eigen maksimalnya 1 .
b. Misal J adalah matriks n×n yang seluruh entri-entrinya adalah 1 , AJ = J . c. Vektor u = ( 1, 1, · · · , 1 ) adalah vektor eigen untuk nilai eigen 1 .
Bukti :
(a)  Misalkan A =   ij a dan  nilai  eigen  maksimal A adalah r ,  maka max min r r r   (lihat [10],Ch.2).  Karena 1 max min   r r ,  maka r = 1. 
(b)  Misalkan A =   ij a ,  maka untuk setiap i = 1,…, n berlaku    n j ij a 1 . 1  Misalkan J =
  , ij b dengan ij b =  1,   , ,..., 1 , n j i   maka AJ =   ij n k ik n k kj ik d a b a                   1
1 ,
dengan    n k ik ij a d
1 dan untuk setiap i = 1, 2, … , n berlaku    n k ik a 1 1, maka matriks AJ = J.
 Diketahui AJ=J ,  dengan J matriks n  ×  n dengan  entri-entri  1,  maka AJ =   ij n k ik n k kj ik a b a 1 1 1                   , dengan   n j i ij ,..., 2 , 1 , , 1 1    . Untuk i = 1, 2, … ,
n    n k ik a 1 1 adalah jumlah baris matriks A , maka A adalah matriks stokastik. 
(c)  Diketahui  dari  poin  a) r =1,  dan  misalkan u adalah  vektor  eigen  yang berkorespondensi  dengan r =1.  Misalkan u =   n u u ,..., 1 , Au =   ij a ' u =   ' 1 ,..., n u u ,
dengan    n k i k ik u u a 1 , untuk setiap i = , 2, … , n .  Misalkan u s = max{ u 1 , … , u n } untuk suatu s  {1, … , n }, maka
   n k s k sk u u a
1
1 ,
     n k n k s k sk sk u u a a 1 1           n k s k sk u u a 1 1 0 . 0  sk a untuk  setiap  k  =  1,2,…, n dan    n k sk a 1 1,  maka  haruslah 0 1   s k u u ,
untuk setiap k = 1, 2,…, n . s k u u  untuk setiap k = 1, 2,…, n , maka vektor u = (1, 1,
…, 1)  adalah vektor eigen yang berkorespondensi dengan nilai eigen 1. 
 Diketahui  vektor  eigen  yang  berkorespondensi  dengan  nilai  eigen  maksimal  1 adalah u = (1, 1,…, 1), untuk A . Misalkan A =   , ij a   n j i ,..., 2 , 1 ,   , atau
Au   ij a  u
= u
Maka jumlah entri-entri dalam setiap baris matriks A adalah 1, atau A adalah matriks stokastik. 
Teorema 2.2. Misalkan A dan B adalah dua matriks stokastik, maka a. AB adalah matriks stokastik b.   Untuk   [ 0, 1 ) , maka  A + ( 1 −  ) B adalah matriks stokastik.
Bukti :
(a)  Misalkan A dan B adalah  matriks  stokastik,  dengan  menggunakan  sifat  (b)  pada Teorema 2.1, maka ( AB ) J = A ( BJ ) = AJ = J , diperoleh ( AB ) J = J maka AB adalah matriks stokastik. 
(b)  Pembuktian  dengan  memakai  poin  (b)  pada  Teorema  2.1,  dan  misalkan A dan B adalah matriks stokastik, maka untuk setiap
  1 , 0   berlaku
(  A + (1 −  ) B ) J =  AJ + (1 −  ) BJ =  J + (1 −  ) J = J
maka  A + (1 −  ) B matriks stokastik untuk   (0, 1]. 
Misalkan k Z Z Z ,..., , 2 1 adalah  bilangan-bilangan  dalam  bidang  kompleks,  dan
k    ,..., , 2 1 adalah  bilangan  tak  negatif  yang  jumlah  keseluruhannya  1,  maka  titik    k i i i Z
Z 1  disebut  jumlah  konveks  dari k Z Z Z ,..., , 2 1 .  Sifat  ini  kemudian  akan dikembangkan dalam dua akibat berikut.
Akibat 2.1. Jika  adalah nilai eigen dari matriks stokastik A berorde n dan  adalah jumlah konveks  dari , ,..., , , 1 2 n    untuk     k i i c i c 0
, 0 , 1 maka  adalah  nilai  eigen  dari matriks stokastik B = 0 c I n + c 1 A + c 2 A 2 + … + c k A k .
Akibat  2.2. Jika  nilai  eigen  dari  matriks stokastik A berordo  n,  maka  untuk sembarang bilangan tak negatif c < 1 , c  nilai eigen dari matriks stokastik.
Kedua  akibat  di  atas  telah  diberikan  bukti  di  [1].  Selanjutnya  Perhatikan  bentuk  matriks J dengan entri-entrinya 1, nilai karakteristik dari J adalah n dan 0, atau spektrumnya adalah ( n ,

## Andi Kresna Jaya
0, … , 0). Jika dikalikan dengan skalar 1/ n maka matriks J n J n 1  adalah matriks stokastik dengan spektrumnya adalah (1, 0, ... , 0). Teorema berikut merupakan rangkuman Akibat 2.1 dan Akibat 2.2.
Teorema 2.3. Jika  ( A ) = ) ,..., , 1 ( 2 n   adalah spektrum matriks stokastik A , maka B =  A + (1 −  ) Jn adalah matriks stokastik dengan spektrum  ( B )=   n   ,..., , 1 2 untuk setiap
1 0    .
Bukti : Untuk 1 0    , pandang jumlah konveks matriks A dengan J n , B =  A + (1 −  ) J n , maka dengan  Teorema  2.2  poin  (b), B adalah  matriks  stokastik.  Diketahui J n matriks  stokastik dengan  spektrum  (1,  0,  …  ,  0),  maka  terdapat P matriks  tak  singulir  sedemikian  sehingga P Jn P - 1 = diag(1, 0, … , 0). Sehingga
1 1 1 ) 1 (       P J P AP P PBP n   1 1 ) 1 (      P PJ PAP n   ) 0 ,..., 0 , 1 ( ) 1 ( 1 diag PAP      
dengan PBP -1 similar dengan B dan PAP -1 similar dengan A . Misalkan
PAP - 1              nn n n n n d d d d d d
d d d
       2 1 2 22 21 1 12 11
Klaim: Spektrum matriks B adalah   n   ,..., , 1 2 . Misalkan C = diag   n   ,..., , 1 2 , maka
PBP - 1 − C =  PAP - 1 + (1 −  ) diag(1, 0, … , 0) − C
 
    
             n nn n n n n d d d d d d d d d    
     
  
  

  2 1 2 2 22 21 1 12 11 1 1 PBP - 1 − C
   
            n nn n n n n d d d d d d d d d              
     2 1 2 2 22 21 1 12 11    
            n nn n n n n d d d d d d d d d           2 1 2 2 22 21 1 12 11 1 =  ( PAP -1 – diag ) ,..., , 1 ( 2 n   )
Akan ditunjukkan determinan PBP - 1 − C = 0 .
Andi Kresna Jaya
det( PBP - 1 − C ) = n  det( PAP - 1 − diag ) ,..., , 1 ( 2 n   )
Karena ) ,..., , 1 ( 2 n   adalah  spektrum  matriks A ,  maka ) ,..., , 1 ( 2 n   juga  spektrum  dari PAP - 1 .  Jadi  det( PAP -1 −  diag ) ,..., , 1 ( 2 n   )  =  0,  maka  det( PAP -1 − C )  =  0.  Spektrum  dari matriks PBP -1 adalah ) ,..., , 1 ( 2 n   . Jadi spektrum B adalah  ( B ) = ) ,..., , 1 ( 2 n   untuk setiap 1 0    . 
Untuk  sembarang  matriks  tak  negatif  dengan  nilai  eigen  maksimal  1  yang  akan dibahas  pada  bab  berikut, senantiasa  terdapat  matriks  stokastik  yang  similar  dengan  matriks tersebut dan dituangkan dalam teorema berikut.
Teorema  2.4. Jika A matriks  tak  negatif  dengan  nilai  karakteristik  maksimal  r  dan  suatu vektor  karakteristik  positif  untuk  nilai  karakteristik  r,  maka r - 1 A serupa  secara  diagonal dengan suatu matriks stokastik.

## Bukti
Misalkan x =   n x x x ,..., , 2 1 adalah  vektor  karakteristik  positif  untuk  nilai  karakteristik maksimal r dari A . Jika D = diag   n x x x ,..., , 2 1 , maka x = Du dengan u = (1, 1, … , 1)
D -1 ( r -1 A ) D = r -1 D -1 AD ( r -1 D -1 AD ) u = r -1 D -1 Ax = r -1 D -1 rx = D -1 x = u
Maka dengan Teorema 2.2, r -1 D -1 AD adalah matriks stokastik. 

## 3. Himpunan Spektrum Real Matriks tak Negatif
Permasalahan  yang  akan  dibahas  dalam  makalah  ini  adalah  pertanyaan  pada  paper
Alberto  Borobia  dan Julio Moro  [8].  Apakah  benar jika ) ,..., , 1 ( 2 n   spektrum  matriks  tak negatif (yang tidak similar dengan sembarang matriks positif), maka terdapat dua komponen di  =   n   ,..., , 1 2 yang  sama,  atau  terdapat  suatu  subset   s   ,..., 1 dari  sehingga
s 
   ... 1 =  0.  Untuk  itu  akan  kembali  diperhatikan  himpunan-himpunan N n dan P n yang telah didefinisikan di awal makalah ini.
Teorema  3.1. Jika n n N  ) ,..., , , 1 ( 3 2    , maka  untuk  setiap  t [0.1) berlaku n n P t t t  ) ,..., , , 1 ( 3 2    .
Bukti :
Misal n n N  ) ,..., , 1 ( 2   , maka terdapat matriks A yang tak negatif dengan spektrum  ( A ) = ) ,..., , 1 ( 2 n   . Sehingga untuk matriks A tersebut ada 2 kasus, yaitu :
1. Jika A matriks  tak  tereduksi, maka untuk setiap t di dalam  [0, 1), maka  matriks P = t S +(1 − t ) Jn adalah matriks positif dengan spektrum  ( P )= ) ,..., , 1 ( 2 n   .
2. Jika A adalah matriks tereduksi, maka terdapat matriks permutasi P sedemikian sehingga
PAP T                    K S K K S S A B A B B A B B B A 0 0 0 0 , 1 1 2 23 2 1 13 12 1           
A 1 , … , A k adalah matriks tak tereduksi, di mana k  n .  Pilih matriks tak negatif G , yaitu:

## G
             K A A A 0 0 0 0 0 0 2 1       
maka  spektrum G adalah  ( G )  = ) ,..., , 1 ( 2 n   . S k = D K -1 A k D k adalah  matriks  stokastik k n k n  yang similar  dengan A k , dan D k = diag( nk k k w w w ,..., , 2 1 ). Untuk setiap i = 1,…, k −1, A i adalah  matriks  tak  negatif i n i n  yang  tak  tereduksi  (diketahui: n n n k    ... 1 ). Misalkan  nilai  karakteristik  maksimal A i adalah pi  untuk  suatu   n p i ,..., 2  ,  maka
terdapat   ni i u u u ,..., 1  vektor  positif  yang  berkorespondensi  dengan  nilai  karakteristik
, pi  maka i i i i pi S D A D    1 1  , dengan D i = diag   ni i u u ,..., 1 dan Si adalah matriks stokastik ( n i ) × ( n i ). Bentuk matriks G dapat ditulis menjadi
                    1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 k k k k k pk k p D S D D S D D S D        
yang dapat dipisahkan dalam perkalian tiga matriks berikut.
G = D
              k k pk p S S S 0 0 0 0 0 0 1 1 1 1         
D - 1 , dengan D
           k D D     
0 0 1 .
Matriks
   
 

## 
    
  k k pk p S S S 0 0 0 0 0 0 1 1 1 1         
similar dengan matriks G . Pandang matriks stokastik berikut.
S                 k k k pk p S E S E S 0 0 0 0 1 1 1 1 1 1  
       untuk i = 1, … , k − 1, E i adalah matriks berukuran n i × n i +1 yang berbentuk
E i              0 0 1 0 0 1
      pi pi   S adalah matriks stokastik n×n dengan spektrum, maka   n   ,..., , 1 2 dengan cara yang sama dengan kasus A yang tak tereduksi, matriks P = t S + (1 − t ) Jn adalah matriks positif n × n dengan spektrum  ( P ) = ) ,..., , , 1 ( 3 2 n t t t    . Jadi n n P t t t  ) ,..., , , 1 ( 3 2    . 
Kemudian pandang himpunan B n = N n − P n . Himpunan B n merupakan batas himpunan N n . Misalkan n n B  ) ,..., , , 1 ( 3 2    , maka ) ,..., , , 1 ( 3 2 n    adalah spektrum dari A matriks tak negatif dan tidak ada satupun matriks positif yang similar dengan A . Contohnya, (1, 1, … ,
1) dan ) ,..., , , 1 ( 3 2 n    sedemikian sehingga
0 ... 1 2     n   , merupakan spektrum dari matriks tak negatif tapi bukan spektrum matriks positif manapun.
Gambar 1 .  Representasi Himpunan N 2 .
Perhatikan  jika   n N  2 , 1  ,  maka  untuk 2  =  1  atau 2  =  −1,  vektor  (1, 2  )  adalah  titik pada  batas  atau  tidak  ada  matriks  positif  yang  spektrumnya  adalah  (1, 2  ).  Nilai-nilai 2  hanya  terletak  pada  interval  [−1,  1].  Himpunan N 2 adalah  segmen  garis  yang  berada  satu satuan ke atas dari sumbu - 2  , sebagaimana yang diperlihatkan pada Gambar 1 di atas. Untuk
Himpunan N 3 di Ruang R 3 , himpunan tersebut adalah sebuah bidang yang terletak pada 1  = 1 yang dibatasi oleh garis 2  + 3  = −1, 2  = 1, 3  = 1, 2  = −1, dan 3  = −1, sebagaimana yang diberikan pada Gambar 2 berikut.

## Andi Kresna Jaya
Gambar 2. Representasi Himpunan N 3 .
Untuk himpunan N 4 di ruang R 4 , himpunannya adalah volume ruang yang berbentuk kubus  terpotong  oleh  persamaan  bidang 2  + 3  + 4  =  0.  Namun  untuk  memberikan  bentuk geometrisnya  agak  sulit  dilakukan,  sehingga  tampilan  grafiknya  belum    diberikan  dalam makalah ini.

## 4. Penutup
Untuk n =  2,  pertanyaan  pada  [8]  terjawab  secara  trivial,  yaitu  batas  himpunan N 2 adalah (1, 1) dan (1,−1). Untuk n = 3, bidang yang dibatasi oleh 2  + 3  = −1, 2  =1, 3  = 1, 2  = −1, dan 3  = −1 di atas bidang 2  O 3  sejauh 1 satuan. Titik (1, 0, 0, … , 0) di Ruang R n adalah  unsur P n ,  dan  setiap  kita  menarik  garis  lurus  ke  sembarang  titik  pada  batas himpunan N n , maka titik-titik yang kita peroleh senantiasa unsur dalam P n . Akibatnya, bentuk pertanyaan  tadi  harus  lebih  spesifik  jika ) ,..., , 1 ( 2 n   spektrum  matriks  tak  negatif  (yang tidak  similar  dengan  sembarang  matriks  positif),  maka  terdapat i =  2,  3,  …  , n sedemikian sehingga i  = 1. Sebaliknya tidak selalu benar bahwa terdapat suatu subset   s   ,..., 1 dari  sehingga s     ... 1 =  0,  maka ) ,..., , 1 ( 2 n   spektrum  matriks  tak  negatif  (yang  tidak similar dengan sembarang matriks positif).
Open problem yang muncul adalah spesifikasi pertanyaan tersebut menjadi : “Apakah benar jika ) ,..., , 1 ( 2 n   spektrum matriks tak negative (yang tidak similar dengan sembarang matriks  positif),  maka  terdapat i =  2,  3,  …  , n sedemikian  sehingga i  =  1,    atau
0 ... 1 3 2      n    ?”  Di  sini  telah  diperlihatkan,  dan  demikian  pula  di  [1,2],  bahwa untuk n = 2, 3 dan 4, maka jawaban permasalahan pada open problem adalah positif.

## Daftar Pustaka
[1]   KresnaJaya,  A.,  2001,  “Masalah  nilai  karakteristik  invers  real  tak  negative”, Thesis, Magister Matematika ITB.
[2]   Wuwen,  G.,  1996,  “An inverse  eigenvalue  problem  for  nonnegative  matrices”, Linear Algebra and Its Applications , 249, pp : 67-78.

## Andi Kresna Jaya
[3]   Radwan,  N.,  1996,  “An  inverse  eigenvalue  problem  for  symmetric  and  normal matrices”, Linear Algebra and Its Applications , 248 , pp : 101-109.
[4]   Fiedler, M., 1974, “Eigenvalues of  non negative symmetric matrices”, Linear Algebra and Its Applications , 9, pp : 119-142.
[5]   Kellogg,  R.B.,  1971,  “Matrices  similar  to  a  positive  or  essentially  positive  matrix”, Linear Algebra and Its Applications , 4, pp :191-204.
[6]   Marcus,  M.  &  Minc,  H.,  1964,  “ Matrix  Theory  and  Matrix  Inequalities ”,  Allyn  and Bacon Inc., Boston.
[7]   Borobia,  A.  and  Moro,  J.,  1997,  “On  non  negative  matrices  similar  to  positive matrices”, Linear Algebra and Its Applications , 266, pp : 365-379.
[8]   Borobia,  A.  and  Moro,  J.,  1998,  “On  the  boundary  of  the  set  of  real  spectra  of nonnegative matrices”, Linear Algebra and Its Applications , 278, pp : 287-293.
[9]   Borobia,  A.,  1998, “On  the  nonnegative  eigenvalue  problem”, Linear  Algebra and  Its Applications , 223/224, pp : 93-97.
[10]  Minc,  H.,  1998,  “ Nonnegative  Matrices ”,  John  Wiley-Interscience  Publication,  New York.