HUBUNGAN ANTARA MAYORISASI NILAI EIGEN EUCLIDEAN DISTANCE MATRIX (EDM) DENGAN MATRIKS SEMIDEFINIT POSITIF YANG BERSESUAIAN Harnoko Dwi Yogo Pembimbing : Arie Wibowo, M.Si Program Studi Matematika, Fakultas MIPA
Abstrak Euclidean Distance Matrix (EDM) mempunyai hubungan dengan matriks semidefinit positif yang mana hubungan tersebut direpresentasikan oleh fungsi dan fungsi , dengan dan merupakan fungsi yang saling invers (H. Kurata & P. Tarazaga, 2011). Sedangkan istilah dan notasi mayorisasi itu sendiri pertama kali diperkenalkan oleh Hardy, Littlewood, & Polya (1934) untuk mengungkapkan suatu vektor dikatakan “ less spread out ” dibanding vektor . Pada skripsi ini akan dipelajari bagaimana hubungan matriks semidefinit positif dan jika diketahui bahwa vektor dengan elemen nilai-nilai eigen matriks EDM dimayorisasi oleh vektor dengan elemen nilai-nilai eigen matriks EDM dengan bersesuaian . dengan Kata kunci: Euclidean Distance Matrix (EDM), mayorisasi, matriks semidefinit positif.
Abstract There is a relationship between Euclidean Distance Matrix (EDM) and positive semidefinite matrix, which is represented function and function, with and are mutually inverse (H. Kurata & P. Tarazaga, 2011). Meanwhile the term and notation of majorization was first introduced by Hardy, Littlewood, and Polya (1934), to express how the vector is said to be "less spread out" than the vector . In this paper, it will be studied how the relationship between the positive semidefinit matrix and , if it is known that a vector with elements eigenvalues of the EDM is majorized by a vector with elements eigenvalues of the EDM , where corresponds to . Keywords: Euclidean Distance Matrix (EDM), majorization, positive semidefinite matrix.
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
Pendahuluan Hasil yang paling bermanfaat dalam mempelajari Euclidean Distance Matrix atau yang disingkat dengan EDM telah terlihat dalam 30 tahun terakhir ini yaitu dalam hal multidimentional scaling pada statistik dan dalam hal molecular conformation pada bidang kimia dan biologi molekul (P. Tarazaga, B.S. Boatwright, K. Wijewardena, 2007). EDM ini sendiri mempunyai hubungan yang erat kaitannya dengan matriks semidefinit positif. Hubungan ini direpresentasikan oleh fungsi
dan fungsi , dengan
dan
merupakan fungsi yang saling
invers (H. Kurata & P. Tarazaga, 2011). Sedangkan istilah dan notasi mayorisasi itu sendiri pertama kali diperkenalkan oleh Hardy, Littlewood, & Polya (1934) untuk mengungkapkan suatu vektor dibanding vektor penjumlahan setiap
. Dan mereka menyatakan bahwa vektor elemen terbesar vektor
elemen terbesar vektor
untuk
dikatakan “ less spread out ” dimayorisasi vektor
jika
kurang dari sama dengan penjumlahan setiap dan penjumlahan semua elemen vektor
harus sama dengan penjumlahan semua elemen vektor
dengan
. Selanjutnya pada
tahun 1952, Rado mendefinisikan mayorisasi dalam istilah himpunan konveks yang secara kontekstual berbeda dengan yang didefinisikan Hardy, Littlewood, & Polya (1934). Kemudian Marshall & Olkin pada tahun 1979 membuka diskusi awal tentang pengembangan teori mayorisasi lewat buku yang berjudul “Inequalities: Theory of Majorization and Its Application”. Yang mana dalam buku ini dibahas banyak tentang penggunaan hubungan mayorisasi antar vektor yang elemennya adalah semua nilai eigen yang dimiliki matriks tertentu. Kemudian, setiap matriks yang mempunyai nilai eigen akan dapat dibandingkan berdasarkan mayorisasi antar vektor yang elemennya adalah nilai-nilai eigen matriks tersebut dengan matriks lain. Oleh karena itu pada penelitian ini akan dipelajari bagaimana hubungan matriks semidefinit positif eigen matriks EDM
dan
jika diketahui bahwa vektor dengan elemen nilai-nilai
dimayorisasi oleh vektor dengan elemen nilai-nilai eigen matriks EDM
dengan
bersesuaian dengan
seperti apakah hubungan antara nilai-nilai eigen matriks
dan
. Sebaliknya, akan dicari tahu pula
jika terlebih dahulu diketahui vektor dengan elemen
dimayorisasi oleh vektor dengan elemen nilai-nilai eigen matriks
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
.
Pembahasan Pada bab ini akan dibahas tentang hubungan antara nilai eigen Euclidean Distance Matrix atau yang disingkat dengan EDM dengan Matriks Semidefinit Positif yang bersesuaian. Secara rinci alur penjelasannya dimulai dengan pengertian EDM , kemudian dilanjutkan dengan pembahasan mayorisasi. Dan yang terakhir akan dibahas terkait lemma dan teorema yang menjelaskan hubungan mayorisasi nilai eigen EDM dengan matriks semidefinit positif yang bersesuaian. Matriks EDM merupakan bentuk khusus dari matriks predistance, oleh karena itu akan didefinisikan terlebih dahulu terkait matriks predistance sebagai berikut. Definisi 3.1 Matriks predistance merupakan matriks nonnegatif yang simetris dengan semua elemen diagonalnya bernilai nol. (Hiroshi Kurata & Pablo Tarazaga, 2011) Kemudian berikut ini definisi matriks EDM. (
Definisi 3.2 Matriks predistance bilangan bulat positif sehingga
‖
dan
) yang berukuran
disebut EDM, jika ada
titik koordinat yaitu
sedemikian
dengan ‖ ‖ merupakan norm Euclidean pada
‖
.
(Hiroshi Kurata & Pablo Tarazaga, 2011) Untuk teorema yang menghubungkan matriks EDM dengan matriks semidefinit positif bisa dilihat berikut ini. Teorema 3.3 Jika
merupakan vektor
yang semua elemennya bernilai 1, sedangkan
. Maka terdapat pemetaan linear invers fungsi untuk
, yang dinyatakan sebagai matriks identitas
dan
yang mempunyai dengan dengan
merupakan vektor yang terdiri dari elemen diagonal matriks . (Hiroshi Kurata & Pablo Tarazaga, 2011) Selanjutnya akan dilanjutkan dengan pembahasan dari Mayorisasi. Definisi Mayorisasi terbagi menjadi dua yaitu mayorisasi menurut Hardy, Littlewood, & Polya (1934) dan mayorisasi menurut Rado (1952). Secara tekstual keduanya beda tetapi mempunyai makna yang sama. Definisi 3.4 Untuk
,
dimayorisasi oleh
( yang ditulis
), jika
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
∑ dengan
[]
dan
[]
∑
[]
∑
[]
merupakan elemen terbesar ke- vektor
[]
∑
[]
dan .
(Hardy, Littlewood, & Polya, 1934) Definisi 3.4 di atas berbeda dengan definisi mayorisasi di bawah ini. ,
Definisi 3.5 Untuk
dimayorisasi oleh
( yang ditulis
merupakan anggota convex hull dari himpunan
) mempunyai arti dengan
matriks permutasi yang melakukan aksi pada himpunan
merupakan grup
. (Rado, 1952)
Dibawah ini diberikan lemma dan teorema yang membahas kaitan mayorisasi antar matriks simetris. Dan himpunan matriks simetris ukuran ̃
Lemma 3.6 Misalkan
dilambangkan dengan
.
̃ dipenuhi jika dan hanya
, maka pertidaksamaan
jika ̃ dapat dinyatakan dalam kombinasi konveks seperti berikut: ̃ untuk suatu bilangan bulat
∑ yang memenuhi ∑
, dan bilangan real positif
, dan beberapa matriks ortogonal
.
(Hiroshi Kurata & Pablo Tarazaga, 2011) Teorema 3.7 Misalkan
̃
dan ̃
dan misal
̃ . Maka
̃
terpenuhi jika dan hanya jika ̃ untuk suatu bilangan bulat
∑ yang memenuhi ∑
, dan bilangan real positif
, dan beberapa matriks ortogonal
.
(Hiroshi Kurata & Pablo Tarazaga, 2011) Bukti: Jika dimisalkan ̃ Maka berdasarkan lemma 3.6, pernyataan
∑ ̃ terpenuhi dikarenakan
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
.
̃ terpenuhi. Misalkan ̃
Untuk menunjukkan sebaliknya, diasumsikan [
dengan ̃
]
̃
dan ̃ adalah nol ;
maka elemen ke- dari
̃ ( * dengan
( ) ̃
̃ dan
̃
dan ,
. Sehingga dapat dinyatakan ̃.
, dan tentunya
Menurut teorema 2.6.3 dapat disimpulkan jika
̃
. Karena ̃
[ ̃]
̃ maka ̃
matrix doubly stochastis. Padahal menurut Teorema 3.3.2, ̃
, dengan
merupakan
bisa dinyatakan dalam
bentuk ̃ untuk suatu bilangan bulat
∑
dan beberapa matriks permutasi
, dengan
menyatakan himpunan
dan ̃ = Diag(̃) merupakan matriks berukuran
= Diag
yang mana notasi Diag
,
menyatakan matriks diagonal yang elemen diagonalnya merupakan
elemen dari vektor . Selanjutnya akan dibuktikan terlebih dahulu bahwa
Buktinya sebagai berikut: dimisalkan [ ]
(
,
(
[ ]
, (
dengan
[ ];
untuk
; merupakan matriks
bernilai 1 dan elemen lainnya 0, dan dengan elemen ke-[ ] bernilai [ ][ ][ ]
[
,
.
matriks permutasi ukuran Misalkan
yang memenuhi ∑
, dan bilangan real positif
[]
[]
; untuk
])
[
dengan elemen ke-[ ] , merupakan matriks
dan elemen lainnya 0, sedangnya notasi
] merupakan permutasi dari bilangan
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
.
[ ] [ ]
[(
(
,]
]
])
[
[(
,
[ ] [ ]
(
])
[
padahal [ ] [ ]
(
,(
(
[ ])
[ ]
])
[
[ ]
[ ] [ ]
(
[ ]
[
( ]
[ ]
[ ]
[ ])
[ ]
(
)
[
.
maka terbukti bahwa Sehingga, berdasarkan persamaan ̃ (̃)
̃
̃
Selanjutnya, karena
∑
(∑
dan hasil di atas, bisa didapat persamaan +
dengan
̃
.
Karena
̃
, yang berarti
dekomposisi spektral dari ⁄
∑
)(
dan ̃
̃
,
dan ̃ merupakan matriks semidefinit positif, maka ada dan ̃
dan ̃. Maka matriks )(
yang telah didefinisikan
dan ̃ sebagai berikut:
sedemikian sehingga
(
∑
maka dengan menggunakan matriks
sebelumnya, dapat dinyatakan matriks
̃
])
⁄
̃ ̃ ̃ , yang juga merupakan
dan ̃ dapat dinyatakan sebagai
*
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
̃
̃
⁄
(
)(
̃
*(
(̃ ̃ ̃
(̃
)
dan ( ̃
yang mana
(̃
*
⁄
)
)( ̃
)( ̃
)
) merupakan matriks ortogonal.
Berdasarkan bentuk persamaan yang diperoleh sebelumnya yaitu ̃
∑
dapat diperoleh persamaan ̃
∑
(
)
dengan ( merupakan matriks permutasi
*
.
Berdasarkan persamaan (3.6) dan (3.7) diperoleh ̃
(̃
)( ̃
(̃
) [∑
∑
(̃
∑
(̃
)( ̃
)
)
)( ̃
(
)
Kemudian karena [
)] ( ̃
(
(
][
̃
)
)
)
]
[
][
menyebabkan [
]
maka
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
]
yang
̃
∑
(̃
)
∑
(̃
)[
̃
(
)
]
∑ [ (̃
)
]
[
̃
[ (
Sedangkan jika dimisalkan [ ( ̃ )
]
[ (
̃
̃
∑ [ (̃
)
)
)
]
)
)
)
(̃
) (
(̃
̃
̃
[ (
]
[ (̃
dan tentunya
̃ ̃
̃
[ (
̃
(
)
]
∑
)
]
)
]
) )
)
)
][ ( ̃
(
̃
)
(
̃
) (̃
(
̃ ̃
(̃
) )
)
[ (̃
) (
]
untuk melengkapi pembuktian di atas.
][ (
(̃
)
] akan diperoleh nilai
Terakhir, tinggal dibuktikan bahwa [ (̃
̃
](
⁄
]
𝒆)( ̃
[(
⁄
)(
𝒆)( ̃ ⁄
)( 𝒆
*
(
⁄ ⁄
𝒆
*]
𝒆)( ̃
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
)(
√
*
⁄
(
𝒆) (
√
⁄
*
𝒆√
̃ terpenuhi maka
Kesimpulannya adalah jika
̃ untuk suatu bilangan bulat
𝒆
∑ yang memenuhi ∑
, dan bilangan real positif
, dan beberapa matriks ortogonal Pembahasan teorema 3.7 di atas mirip dengan lemma 3.6 yang perbedaanya cuma terletak pada grup yang melakukan aksi saja. Untuk pembahasan selanjutnya, grup yang melakukan aksi adalah grup
dengan
tentunya
menyatakan himpunan matriks permutasi
ukuran
. Kemudian, pembahasannya sendiri mengenai hubungan mayorisasi
antara nilai eigen EDM dengan matriks-matriks anggota himpunan melakukan aksi dalam bentuk konjugasi pada himpunan Teorema 3.8 Untuk ̃
dan
̃
. dan ̃
, misalkan
dan grup
̃ . Kemudian jika
terpenuhi, maka vektor nilai eigen matriks ̃ akan termayorisasi oleh vektor nilai
eigen matriks
̃
atau yang biasa dinyatakan sebagai
. (Hiroshi Kurata & Pablo
Tarazaga, 2011) Bukti: Karena ̃ dengan aksi
yang berarti ̃ anggota convex hull dari himpunan , maka ̃ dapat dinyatakan sebagai
berbentuk ̃
untuk suatu bilangan bulat
∑ yang memenuhi ∑
, dan bilangan real positif
dan beberapa matriks permutasi
.
Sebelum melanjutkan pembuktian akan dibuktikan terlebih dahulu bahwa . Buktinya sebagai berikut: misalkan [ ]
(
[ ]
, (
[ ])
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
,
dengan
[ ];
untuk
dengan elemen ke-[ ] bernilai 1 dan
; merupakan matriks
elemen lainnya 0, sedangnya notasi [ ] [ ]
[ ] merupakan permutasi dari bilangan
[ ] [ ]
[(
[(
[ ])
[ ]
]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
[ ]
,(
[ ]
[ ] )]
[ ]
[ ]
[ ][ ]
[ ][ ]
[ ][ ]
[ ][ ]
[ ][ ]
[ ][ ]
[ ][ ]
[ ][ ]
[ ][ ]
[ ]
[ ][ ]
,]
(
[ ][ ]
,
[ ][ ]
[ ]
[ ]
(
[ ]
[ ])
[ ]
[(
,(
(
(
[ ]
,
[ ])
(
,]
[(
[ ])
Dengan menggunakan hasil di atas didapat ̃
( ̃)
(∑
∑
[
∑
[
∑
∑
+
∑
[
]
[
[
[
]
]
]
]
]
∑
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
.
Berdasarkan persamaan ̃
∑
dan hasil dari contoh 3.2.10 maka diperoleh
kesimpulan bahwa ( ̃ ) Teorema selanjutnya akan menjelaskan hal yang serupa seperti teorema 3.8, namun grup yang melakukan aksi pada Teorema 3.9 Misalkan
adalah grup ̃
dan ̃
dengan
memayorisasi nilai eigen ̃ :
̃ . Andaikan nilai eigen
̃ , yang mana ̃ dinyatakan sebagai ̃
untuk suatu bilangan bulat
.
∑ yang memenuhi ∑
, dan bilangan real positif
. Maka ̃ dapat dinyatakan sebagai
, dan beberapa matriks ortogonal berikut:
̃
∑
dengan ̃ dimana
∑
= diag( ) dan ̃ = diag( ̃ ). Dan oleh karena itu, [̃
]
(Hiroshi Kurata & Pablo Tarazaga, 2011) Bukti: ̃
( ̃)
(∑
+
∑
∑ [ Misalkan ̃
∑ [
[
]
]
, maka ]
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
∑ [
]
∑ [
]
∑ [
]
∑ [
]
∑ [
]
Dan karena ̃
, sehingga didapat
∑ [
]
∑ [
∑
]
[∑
]
[∑
]
Kemudian dengan memisalkan [∑
]
maka ̃
∑
Untuk melengkapi pembuktian, akan dinyatakan ̃
dalam bentuk ∑
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
= diag( ) dan ̃ = diag( ̃ ).
dengan [∑
∑
]
∑
∑
∑
( ̃)
∑
̃
∑
∑ ̃
∑
∑
Akibat 3.10 Misalkan
̃
sama dan
( ̃ ) serta memenuhi
dengan masing-masing memiliki elemen diagonal yang ̃ . Maka
̃ . (Hiroshi
Kurata & Pablo Tarazaga, 2011) Bukti: dan ̃
Misalkan vektor ̃
dinyatakan sebagai ̃
( ̃ ), maka berdasarkan asumsi diatas
dengan
∑
∑
dan ̃ dapat
. Kemudian, berdasarkan teorema 3.9 didapat ∑
karena maka ̃
∑
∑ ( ̃)
Sehingga dapat disimpulkan
Berikut ini merupakan teorema terakhir yang dibahas pada skripsi ini dan juga merupakan konversi dari teorema 3.8. Teorema 3.11 Untuk ̃
̃
, misalkan
dan ̃
̃ . Kemudian jika
terpenuhi, maka vektor nilai eigen matriks ̃ akan termayorisasi oleh vektor nilai
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
eigen matriks
atau yang biasa dinyatakan sebagai
̃
. (Hiroshi Kurata & Pablo
Tarazaga, 2011) Bukti: karena ̃
yang berarti ̃ anggota convex hull dari himpunan , maka ̃ dapat dinyatakan sebagai
berbentuk
dengan aksi
̃
∑ yang memenuhi ∑
untuk suatu bilangan bulat m, dan bilangan real positif dan beberapa matriks permutasi
.
Sebelum melanjutkan pembuktian akan dibuktikan terlebih dahulu bahwa dengan
. Buktinya sebagai berikut: karena
,
maka (
*
(
*
Dengan menggunakan hasil di atas dan melihat teorema 3.1.5 didapat ̃
( ̃)
(∑
∑
∑
∑
+
[
]
[
]
∑
[
]
∑
∑
Berdasarkan persamaan ̃
∑
dan hasil dari contoh 3.2.10 maka diperoleh
kesimpulan bahwa ( ̃ )
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
,
Penutup Pada penelitian ini telah ditunjukkan bahwa jika vektor dengan elemen nilai-nilai eigen matriks semidefinit positif matriks semidefinit positif ̃ matriks EDM
memayorisasi vektor dengan elemen nilai-nilai eigen ( ̃ ) maka berakibat vektor dengan elemen nilai-nilai eigen
memayorisasi vektor dengan elemen nilai-nilai eigen matriks EDM ̃ dengan harus sama dengan elemen diagonal matriks ̃
kondisi elemen diagonal matriks
( ̃ ) serta masing-masing elemen itu sama satu dengan yang lain (Akibat 3.10). Kemudian berdasarkan teorema 3.8 dapat disimpulkan bahwa jika matriks semidefinit positif ̃
( ̃ ) merupakan anggota convex hull dari himpunan
maka berakibat vektor dengan elemen nilai-nilai eigen matriks EDM
memayorisasi vektor
dengan elemen nilai-nilai eigen matriks EDM ̃ . Dan teorema 3.11 merupakan konversi dari teorema 3.8, karena teorema 3.11 menyatakan bahwa jika matriks EDM ̃ merupakan anggota convex hull dari himpunan
maka akan berakibat vektor dengan elemen nilai-
nilai eigen matriks semidefinit positif eigen matriks semidefinit positif ̃
memayorisasi vektor dengan elemen nilai-nilai ( ̃ ).
Daftar Pustaka Anton, H., & Rorres, C. (2005). Elementary Linear Algebra 9th ed. New York: Willey. Bartle, R. G., & Sherbert, D. R. G. (2000). Introduction to Real Analysis (
ed.). New York:
John Wiley & Sons. Bhattacharya, P., Jain, S., & Nagpul, S. (1994). Basic Abstract Algebra 2nd ed. New York: Cambridge University Press. Eaton, M. L. (1984). On group induced ordering, monote functions, and convolution theorems. IMS Lecture Notes-Monograph Series, Vol. 5, 13-25. Hardy, G., Littlewood, J. E., & Polya, G. (1934). Inequalities. New York: Cambridge University Press.
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
Hayden, T. L., & Tarazaga, P. (1993). Distance Matrices and Regular Figures. Elsevier Science Publishing Co., Vol. 195, 9-16. Herstein, I. N. (1996). Abstract Algebra 3rd ed. New Jersey: Prentice-Hall. Horn, R. A., & Johnson, C. R. (1985). Matrix Analysis. New York: Cambridge University Press. Kurata, H., & Tarazaga, P. (2011). Majorization for the eigenvalues of Euclidean Distance Matrices. Elsevier Inc., Vol. 436, 1473-1481. Lipschutz, S. (1965). Theory and Problems of General Topology. New York: McGraw-Hill. Manfrino, R. B., Ortega, J. A. G., & Delgado, R. V. (2009). Inequalities. Basel: Birkhauser. Marshall, A. W., Olkin, I., & Arnold, B. C. (2009). Inequalities: Theory of Majorization and Its Applications (
ed.). New York: Springer.
Munkres, J. R. (2000). Topology (
ed.). Upper Saddle River: Prentise Hall.
Rado, R. (1952). An Inequality. J. London Math. Soc., Vol. 27, 1-6. Roman, S. (2008). Advanced Linear Algebra (
ed.). New York: Springer.
Tarazaga, P., Boatwright, B. S., & Wijewardena, K. (2007). Euclidean distance matrices: special subsets, systems of coordinates and multibalanced matrices. Computational and Applied Mathematic, Vol. 26, 415-438. Vinberg, E. B. (2002). A Course in Algebra. Providence: American Mathematical Society . Zhang, F. (1999). Matrix Theory. New York: Springer.
Hubungan antara..., Harnoko Dwi Yogo, FMIPA UI, 2013
