## RANK MINIMUM MATRIKS HERMITE YANG DIGAMBARKAN GRAF G

## Mohamad Syafi’i
Program Studi Pendidikan Matematika STKIP Kusumanegara, Jakarta
moh.syafii@stkipkusumanegara.ac.id

## Abstrak
Rank  minimum  dari  matriks  Hermite  yang  digambarkan  oleh  graf  G  didefinisikan  dengan rank terkecil dari matriks Hermite suatu graf  G. Graf yang digunakan adalah graf komplit, graf  lintasan,  graf  sikel,  graf  bipartisi  komplit,  dan  graf  star.  Dalam  menentukan  rank minimum yang digambarkan graf tersebut dengan cara membuat matriks adjacency dari graf G  tersebut,  kemudian  dikembangkan  menjadi  beberapa  matriks  Hermite,  kemudian  dicari rank dari beberapa matriks tersebut, sehingga diperoleh rank minimum. Dalam mencari rank matriks  digunakan  operasi  baris  elementer  dan  dibantu  dengan  program  Matlab.  Hasil penelitian ini diperoleh:
1. ( )
2. ( ) 3. ( ) 4. ( ) 5. ( )
Kata Kunci : Rank Minimum, Matriks Hermite, Graf, Matriks Adjacency.

## PENDAHULUAN
Matriks adjacency merupakan
matriks  simetri  dan  menjadi  representasi matriks yang menyatakan hubungan antar  titik  dalam  suatu  gra,  bernilai  1  jika terdapat  dua  titik  yang  saling  terhubung, dan  bernilai  0  jika  kedua  titik  tidak terhubung. Matriks adjacency yang didapatkan dirubah menjadi matriks Hermite,  yang  mana  unsur  –  unsurnya adalah bilangan kompleks tak nol jika antar titik dalam graf tersebut terhubung langsung dan nol jika antar titik dalam graf
tersebut tidak terhubung langsung, sedangkan untuk unsur diagonalnya diabaikan. Setelah dibentuk menjadi matriks  Hermite,  maka  dapat  dicari  rank dari  matriks  Hermite  tersebut,  karena pemberian  unsur-unsur  bilangan  kompleks bersifat random , maka dapat diperoleh rank minimum  dari    matriks  Hermite  yang digambarkan graf . Berdasarkan pengantar tersebut  peneliti  ingin  mengembangkan kajian  ini  karena    pada  penelitian sebelumnya  telah  dibahas  tentang  rank minimum  dari  matriks  yang  digambarkan
Volume 4  No.2  Bulan Desember  Tahun 2018
dengan  graf hanya  dikaji  dalam  bentuk matriks adjacency ,  matriks  simetri  yang unsur  –  unsurnya  modulo dan  matriks simetri  real.  Oleh  karena  itu  penulis  ingin mengembangkan  dan  meneliti  tentang  rank minimum  pada  matriks  Hermite  yang digambarkan  pada  graf ,  sehingga diperoleh  pola  umum  rank  minimum matriks  Hermite  yang  digambarkan  oleh graf .
Definisi Graf Graf adalah pasangan )     )) dengan ) adalah
himpunan  tidak  kosong  dan  berhingga  dari objek – objek yang disebut sebagai titik dan ) adalah  himpunan  (mungkin  kososng) pasangan  tak  nerurutan  dari  titik  –  titik berbeda  di ) yang  disebut  dengan  sisi.
Banyaknya  unsur  di ) disebut  order dari dan dilambangkan dengan ) dan banyaknya  unsur  di ) disebut  ukuran dari  yang  dilambangkan  dengan ) (Abdussakir, Azizah dan Nofandika, 2009). Suatu graf disebut terhubung (connected) jika untuk setiap titik dan di terdapat lintasan  yang  menghubungkan  kedua  titik tersebut  (Chartrand  dan  Ortrud,  1993). Adapun graf yang digunakan pada penelitian ini adalah:

## 1. Graf Komplit
Graf adalah  komplit  jika  setiap  titik terhubung langsung ke setiap titik yang lain,  graf  komplit  dengan titik dinyatakan  dengan (Lipschutz  and
Lipson, 2002).
Contoh:

## 2. Graf Lintasan
Graf  berbentuk  lintasan  dengan  titik sebanyak dinamakan  graf  lintasan order
dan  ditulis  dengan (Abdussakir,  Azizah  dan  Nofandika, 2009).
Contoh:

## 3. Graf Sikel
Graf    berbentuk  sikel  dengan  titik sebanyak , ,  disebut  graf  sikel
dan  ditulis  dengan (Abdussakir, Azizah and Nofandika, 2009).
Contoh:
4. Graf Bipartisi Komplit
Graf bipartisi adalah graf yang himpunan  titiknya  dapat  dipisahkan menjadi  dua  himpunan  tak  kosong dan sehingga masing – masing sisi di graf tersebut menghubungkan satu titik di dan satu titik di ; dan disebut himpunan partisi (Wilson and Walkins, 1990).  Suatu  Graf disebut  bipartisi komplit jika adalah graf bipartisi dan masing – masing titik pada suatu partisi terhubung langsung dengan semua titik pada  partisi  yang  lain.  Graf  bipartisi komplit dengan titik pada salah satu partisi  dan titik  pada  partisi  lain ditulis  dengan
(Abdussakir,
Azizah and Nofandika, 2009).

## Hubungan Matriks Dengan Graf
Misal graf  dengan  order )
dan  ukuran serta  himpunan  semua  titik
) Matriks keterhubungan (Matriks
Adjacency ) dari graf , dinotasikan dengan ) Matriks Adjacency dapat  ditulis sebagai berikut:
FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 4 (2), pp:97-104.
[ ] Dengan Contoh:
Sumber: Sumartoyo, 1983
Dengan melihat adanya
keterhubungan  antara  matriks  dengan  graf, maka dapat dikembangkan dengan mensubtitusi elemen dari matriks Adjacency dengan elemen bilangan kompleks yang memenuhi matriks Hermite.
Adapun langkah-langkahnya sebagai berikut:
1. Diketahui graf G
2. Membentuk  matriks Adjacency dari  graf tersebut
3. Membentuk matriks Hermite dari matriks Adjacency. Dengan aturan sebagai berikut:
a. Elemen diagonal diabaikan nilainya
b. Unsur nol selain di diagonal utamanya harus nol
c. Unsur  tak  nol  pada  matriks  dirubah dengan  unsur  tidak  boleh  nol  dengan semesta bilangan komplek dan diberikan  secara  random  (Fallat  dan Hogben, 2007).
Berdasarkan  langkah-langkah  diatas maka terdapat banyak kemungkinan matriks  Hermite.    Matriks-matriks  tersebut memiliki  rank  masing-masing,  sehingga
dapat ditentukan rank minimum yang dapat didefinisikan sebagai berikut:
Rank  minimum  dari  matriks  Hermite  yang digambarkan  graf dapat  didefinisikan:
)              )
Matriks bujur sangkar dengan unsur bilangan  kompleks  disebut Hermite ,  jika
(Anton  dan  Rorres,  2004).  Dalam memudahkan  mengenali  matriks Hermite , misalkan adalah  suatu  matriks dengan untuk setiap dan .  Sehingga dapat  ditulis dalam bentuk: Dengan dan mempunyai entri bilangan real.
Didefinisikan matriks sekawan dengan
̅
Jadi ̅ adalah  matriks  yang  terbentuk dengan  mengambil  komples  sekawan  dari setiap entri . Tranpose dari ̅ dilambangkan  dengan ,  jadi  suatu matriks disebut Hermite jika Contoh:
[ ]

## Maka
̅   [ ]
Sehingga ̅ [ ]
Jadi adalah matriks Hermite .
Rank  dari  suatu  matriks adalah dimensi  dari  ruang  baris (Leon,  2001). Menentukan  rank  dari  suatu  matriks, dengan mereduksi matriks yang bersangkutan  menjadi  bentuk  eselon  baris. Baris-baris tak nol dari matriks eselon baris akan  membentuk  basis  untuk  ruang basisnya.
Volume 4  No.2  Bulan Desember  Tahun 2018
Adapun teorema-teorema yang mendukung  penelitian  ini  adalah  sebagai berikut (Fallat dan Hogben, 2007):

## Teorema 1.
Diberikan  suatu  graf dengan titik ) ,
)               )       ) .
Teorema 2.
Untuk  setiap field dan  graf dengan order , maka )   | |
Teorema 3. Untuk  graf dengan  order maka )         ) . ) atau  diameter  suatu  graf merupakan  jarak  terbesar  antara  dua  titik yang terdapat pada graf .

## METODE PENELITIAN
Metode yang dilakukan dalam penelitian ini adalah melalui studi kepustakaan  dengan  mempelajari  buku, makalah,  dan  penelitian  sebelumnya  yang berkaitan rank minimum pada matriks yang digambarkan  Graf  G  untuk  digunakan sebagai dasar teori.

## HASIL DAN PEMBAHASAN
Pada awal pembahasan ini diterapkan pada  Graf  komplit
) dengan  n  titik, dimana , graf komplit
merupakan  graf  sederhana  yang  setiap titiknya terhubung ke titik yang lainnya. Di bawah ini adalah   graf yang merupakan contoh dari graf komplit dengan 6 titik.
Gambar 1. Graf
Matriks adjacency graf  komplit )
tersebut adalah sebagai berikut:
[ ]
Berdasarkan  matriks adjacency tersebut dibentuk menjadi matriks Hermite dengan cara:
1. Unsur diagonal diabaikan nilainya
2. Unsur  nol  selain  di  diagonal  utama  tetap nol
3. Unsur tak nol pada matriks diganti dengan konstanta tak nol secara random Dikarenakan tujuan penelitian ini adalah mencari  rank  minimum  dari  matriks Hermite dan  terdapat  beberapa  kemungkinan  bentuk matriks Hermite yang  dapat  digambarkan  graf
, oleh karena itu di cari bentuk pola matriks Hermite yang  mempunyai  nilai  rank  paling minimum  dengan  berpedoman  pada  Teorema 3.
Teorema  4.
Jika graf  komplit  dengan titik  dimana dan , maka ( ) . Bukti: Diketahui  :  Graf  komplit ) dengan titik dimana dan . Maka matrik adjacency dari graf adalah:
[ ] Akan dibuktikan bahwa ( ) Berdasarkan Teorema 3 diperoleh ( )       ( ) . Sehingga
( ) Cukup  ditunjukkan  bahwa
) .  Untuk  memperoleh  matriks
Hermite dengan ( ) , maka diambil matriks  secara  random  (acak).  Adapun  untuk mempermudah  mendapatkan  pola  matriks Hermite dengan minimum rank 1, maka penulis dibantu dengan menggunakan program Matlab,
Mohamad Syafi’i : Rank Minimum Matriks Hermite yang Digambarkan Graf G.
FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 4 (2), pp:97-104.
sehingga  didapatkan  pola  matriks  Hermite sebagai berikut
[ ]
Dimana  rank  dari  matriks  Hermite  tersebut adalah 1.
Ambil matriks Hermite:
[ ] dengan dan √
dengan  menggunakan  eliminasi  Gauss-Jordan, diperoleh  rank  dari  matriks  Hermite  tersebut adalah  1.  Jadi ( ) ,  Karena
) dan
) maka
( ) . Sehingga Teorema 4 terbukti.
Bentuk  matriks adjacency dari  graf di atas adalah:
[ ]
Salah  satu  kemungkinan  Matriks Hermite
dari  matriks adjacency yang  digambarkan graf Adalah:
[
]

## Menggunakan  program  Matlab  diperoleh
( ) . Berdasarkan langkah – langkah dalam menentukan ) ,  dapat  diterapkan pula  dengan  bentuk  graf  lain.  Pada penelitian  ini  selain  menentukan )
juga mencari ( ) , ( ) , ( ) , ( ) .
Teorema 5.
Jika graf  lintasan  dengan titik  dimana dan , maka ( ) (Chenette dan Droms, 2007). Bukti: Diketahui  :  Graf  lintasan ) dengan titik dimana dan . Maka matrik adjacency dari graf adalah:
[ ] Akan dibuktikan bahwa ( ) Berdasarkan Teorema 3. diperoleh ( )       ( ) .  Sehingga ( ) . Cukup ditunjukkan bahwa ( )
Ambil matriks Hermite:
[ ] dengan dan √ . dengan  menggunakan  eliminasi  Gauss-Jordan, diperoleh  rank  dari  matriks  Hermite  tersebut adalah Jadi ( ) . Karena ) dan )
maka ( ) .  Sehingga  Teorema
5 terbukti.
Teorema 6.
Jika graf sikel dengan titik dimana dan , maka ( ) .
Bukti:
Volume 4  No.2  Bulan Desember  Tahun 2018
Diketahui  :  Graf  sikel
) dengan titik dimana dan .  Maka  matrik adjacency dari graf adalah:
[ ]
Akan dibuktikan bahwa ( )
Graf sikel ) bukan merupakan graf lintasan
) .  Akan  tetapi  graf  sikel
) memuat
subgraf  lintasan  terdukung  dengan  lintasan
titik ) ,  berdasarkan  Teorema  1. diperoleh:
) )
( )         )
( )
Sehingga diperoleh ( )
Cukup ditunjukkan bahwa ( ) Ambil matriks Hermite: Dengan , karen maka diperoleh ( ) Untuk ,  ambil  matriks Adjacency dari graf sikel atau
maka:
 maka pilih matriks
) .  ,  dan maka  pilih matriks ) .  ,  dan
maka  pilih
matriks ) .  ,  dan maka  pilih
matriks
) .
Dengan  menggunakan  program  Matlab,  maka diperoleh Rank dari matriks – matriks tersebut adalah . Jadi ( ) . Karena
( ) dan ( ) maka ( ) . Sehingga teorema 5 terbukti.
Teorema 7.
Jika graf  bipartisis  komplit  dengan titik dimana , maka ( ) . Bukti: Diketahui:  Graf  bipartisi  komplit ) dengan titik  dimana .  Maka matrik adjacency dari graf adalah: Akan dibuktikan bahwa ( ) Berdasarkan Teorema 3. diperoleh ( )       ( ) Sehingga ( ) Cukup  ditunjukkan  bahwa ( ) . Ambil matriks Hermite:
dengan dan √ . Dengan menggunakan eliminasi Gauss-Jordan,
diperoleh  rank  dari  matriks  Hermite  tersebut adalah Jadi ( ) . Karena ) dan ) maka ( ) Sehingga Teorema 7.
Terbukti.
Akibat  Teorema  7.  dapat  disimpulkan  bahwa ( ) , dikarenakan graf bintang ) sama  dengan  graf  bipartisi  komplit  dengan bentuk
Mohamad Syafi’i : Rank Minimum Matriks Hermite yang Digambarkan Graf G.
FIBONACCI : Jurnal Pendidikan Matematika dan Matematika. Vol. 4 (2), pp:97-104.
Teorema 8.
Jika merupakan  graf  bintang  dengan
, maka ( ) .

## SIMPULAN
Berdasarkan  pembahasan  tentang  rank minimum dari matriks Hermite yang digambarkan oleh Graf , diperoleh kesimpulan:
1. Rank  minimum  matriks Hermite yang digambarkan graf (graf komplit dengan titik,
) adalah atau ( )
.
2. Rank  minimum  matriks Hermite yang digambarkan graf (graf lintasan dengan titik, )  adalah atau ( ) .
3. Rank  minimum  matriks Hermite yang digambarkan graf (graf sikel dengan titik, ) adalah atau ( ) .
4. Rank  minimum  matriks Hermite yang digambarkan  graf (graf  bipartisi dengan titik, )  adalah atau ( ) .
5. Rank  minimum  matriks Hermite yang digambarkan graf (graf bintang dengan titik, )  adalah atau
( ) .

## DAFTAR PUSTAKA
Abdussakir,  Azizah,  N.  N.  dan  Nofandika,  F.  F.  2009. Teori  Graf .  Malang:  UIN-Malang Press.
Anton, H. dan Rorres, C. 2004. Aljabar Linier Elementer . Jakarta: Erlangga.
Chartrand,  G.  dan  Ortrud,  O.  1993. Applied  and  Algorithmic  Graph  Theory .  Canada: McGraw-Hill Inc.
Chenette, Nathan L. dan Droms, S. V. 2007. “Minimum Rank of a Graph Over an Arbitrary Field”. Electronic Journal of Linear Algebra . Vol. 16, pp. 183-186.
Fallat, S. dan Hogben, L. 2007. “The Minimum Rank of Symmetric Matrices Described by a Graph: A Survey”. Linear Algebra and Its Applications . Vol. 462, pp. 558–582.
Leon, S. J. 2001. Aljabar Linear dan Aplikasinya . Jakarta: Erlangga.
Lipschutz,  S.  dan  Lipson,  M.  L.  2002. Matematika  Diskrit .  Jakarta:  Penerbit  Salemba Teknika.
Sumartoyo, N. N. 1983. Aljabar Linear . Jakarta: Erlangga.
Wilson,  R.  J.  dan  Walkins,  J.  J.1990. Graphs  an  Intoductory  Approach:  A  First  Course  in Discrete Mathematic . New York: John Wiley & Sons Inc
Volume 4  No.2  Bulan Desember  Tahun 2018