BAB II LANDASAN TEORI. himpunan bilangan bulat dan diberi simbol dengan hurup besar B. Anggota

4

BAB II LANDASAN TEORI

A. Bilangan Bulat Himpunan bilangan – bilangan {…..,-3,-2,-1,0,1,2,3,…..} disebut himpunan bilangan bulat dan diberi simbol dengan hurup besar B. Anggota – anggota dari {-1,-2,-3,…..} disebut bilangan – bilangan bulat negatif. Definisi II.A.1 Sistem

bilangan

bulat

terdiri

atas

himpunan

B = {.....,−3,−2,−1,0,1,2,3,......} dengan operasi biner penjumlahan

(+ )

dan

perkalian (×) untuk a, b, c bilangan – bilangan bulat sebarang. Memenuhi sifat – sifat : 1. Sifat tertutup terhadap penjumlahan. Jika a, b ∈ B maka (a + b ) ∈ B 2. Sifat tertutup terhadap perkalian. Jika a, b ∈ B maka (a × b ) ∈ B 3. Sifat komutatif penjumlahan, a + b = b + a 4. Sifat komutatif perkalian, a × b = b × a 5. Sifat assosiatif penjumlahan, (a + b ) + c = a + (b + c) 6. Sifat assosiatif perkalian, (a × b ) × c = a × (b × c) 7. Sifat distributif kiri perkalian terhadap penjumlahan, a × (b + c ) = (a × b ) + (a × c )

8. Sifat

distributif

kanan

perkalian

terhadap

penjumlahan,

(a + b ) × c = (a × c ) + (b × c ) 4 Aplikasi Kriptografi Hill Cipher..., Lilis Dwi Hendrawati, FKIP UMP, 2010

5

9. Jika a bilangan bulat maka a + (− a ) = (− a ) + a = 0 , (− a ) disebut lawan ( invers ) penjumlahan dari a. Hal ini menyatakan bahwa untuk setiap bilangan bulat a ada dengan tunggal bilangan bulat (− a ) sedemikian hingga a + (− a ) = (− a ) + a = 0 10. Untuk setiap a , ada dengan tunggal elemen 0 dalam B sehingga a + 0 = 0 + a = a , 0 disebut elemen identitas penjumlahan. 11. Untuk setiap a , ada dengan tunggal elemen 1 dalam B sehingga a × 1 = 1 × a = a , 1 disebut elemen identitas perkalian.

B. Matriks Definisi II.B.1 ( Ali, 2004 : 81 ) Matriks adalah suatu susunan elemen-elemen atau entri-entri yang diatur dalam bentuk baris dan kolom. Susunan elemen ini diletakkan dalam tanda kurung biasa ( ), atau kurung siku [ ]. Elemen-elemen atau entri-entri tersebut dapat berupa bilangan atau berupa huruf. Matriks dinotasikan dengan huruf kapital seperti A, B, C dan seterusnya. Sedangkan elemennya, jika berupa huruf, maka ditulis dengan huruf kecil.  a11 a A =  21  .  a m1

a12 a 22 . am2

a13 .... a1n  a 23 .... a 2 n  . . .   a m 3 .... a mn 

Matriks A = [aij ] , dengan i dan j merupakan bilangan asli yang menunjukan baris ke-i dan kolom ke-j.

Aplikasi Kriptografi Hill Cipher..., Lilis Dwi Hendrawati, FKIP UMP, 2010

6

1. Macam – macam matriks a. Matriks persegi, ialah suatu matriks yang memiliki baris dan kolom yang sama banyaknya ( m = n ) Contoh II.B.1 : Matriks persegi m = n = 4 2 4 A = 1  5

0 1 2 1

2 7 3 4

4 7  4  1

b. Matriks diagonal, ialah suatu matriks persegi dimana semua elemen di luar diagonal utama mempunyai nilai 0 dan paling tidak satu elemen pada diagonal utama ≠ 0 , biasanya diberi simbol D. Contoh II.B.2 : 1 0 0 D = 0 3 0 0 0 2 c. Matriks identitas, ialah suatu matriks persegi dimana elemen – elemennya mempunyai nilai 1 pada diagonal utama dan 0 pada tempat – tempat lain di luar diagonal utama. Contoh II.B.3 : 1 0 0 E = 0 1 0 0 0 1 d. Matriks skalar, ialah suatu bilangan konstan. Jika k suatu bilangan konstan, maka hasil kali k.I dinamakan matriks skalar.


7

Contoh II.B.4 : 1 0 0 k 0 0  k .I = k 0 1 0 = 0 k 0  0 0 1 0 0 k  e. Matriks segi tiga atas, ialah matriks persegi dimana elemen – elemen yang terletak di bawah diagonal utama semuanya nol, atau matriks

A = [aij ] disebut matriks segi tiga atas jika aij = 0 untuk i > j . Contoh II.B.5: a11 A =  0  0

a12 a 22 0

a13  a 23  a33 

f. Matriks segi tiga bawah, ialah matriks persegi dimana elemen – elemen yang terletak di atas diagonal utama semuanya nol, atau matriks A = [aij ] disebut matriks segi tiga bawah jika aij = 0 untuk i< j. Contoh II.B.6 :  a11 A = a 21  a31

0 a 22 a32

0  0  a33 

g. Matriks Transpose Misal A = [aij ] berukuran ( m × n ) maka transpose dari A adalah matriks AT berukuran ( n × m ) maka AT = [a ji ] .


8

Contoh II.B.7 : 1 2 A = 3 4 5 6 1 3 5  maka AT =    2 4 6 Beberapa sifat matriks transpose : a. ( A + B ) T = AT + BT b. (AT ) T = A c. λ( AT ) = (λA)T

d.

( AB ) T = BT AT

h. Matriks Simetris, ialah matriks yang transposenya sama dengan dirinya sendiri, dengan perkataan lain bila A = AT atau aij =a ji Contoh II.B.8 : 3 1 2  A = 2 6 − 1 3 − 1 5  maka, 3 1 2  A = 2 6 − 1 3 − 1 5  T

i. Matriks Orthogonal Definisi II.B.2 ( Howard, 1985 : 216 ) Matriks A adalah sebuah matriks persegi n × n dengan sifat AAT = AT A = I atau AT = A −1 dikatakan matriks orthogonal.


9

Contoh II.B.9 :  0 − 1 A=  − 1 0   0 − 1 maka AT =   − 1 0   0 − 1  0 − 1 1 0 sehingga AAT =   = =I  − 1 0   − 1 0  0 1  1. Rank Matriks Definisi II.C.2 ( Howard , 1985 : 174 ) Dimensi ruang baris dan ruang kolom dari sebuah matriks A dinamakan rank dari A, ditulis rank(A) Contoh II.B.10 : 1 2 0 − 1 Diberikan matriks A = 2 6 − 3 − 3   3 10 − 6 − 5 dengan serangkaian operasi baris elementer ( OBE ), dapat ditentukan rank(A), yaitu : 1 2 0 − 1  A = 2 6 − 3 − 3 b2 − 2b1 3 10 − 6 − 5 b3 − 3b1

1 2 0 − 1 A = 0 2 − 3 − 1 0 4 − 6 − 5 b3 − 2b2

1 2 0 − 1 A = 0 2 − 3 − 1 0 0 0 0  Dari langkah tersebut, terlihat bahwa banyaknya baris yang taknol pada matriks terakhir adalah 2, maka rank(A) = 2


10

Definisi II.B.3 Diberikan matriks A berukuran m × n , matriks A dikatakan mempunyai rank kolom penuh ( full column rank ) jika rank(A) = n dan mempunyai rank baris penuh ( full row rank ) jika rank(A) = m Contoh II.B.11 : 1 2 a. Diberikan matriks A = 3 4 5 6 dengan menggunakan operasi baris elementer, didapat : 1 2  A = 0 − 2 0 0  rank(A) = 2 dan rank(A) sesuai dengan banyaknya kolom pada matriks A ( rank(A) = n ), maka matriks A mempunyai rank kolom penuh. 1 5 1  b. Diberikan matriks B =    4 6 2 dengan menggunakan operasi baris elementer, didapat : 5 1  1 B=  0 − 14 − 2 rank(B) = 2 dan rank(B) sesuai dengan banyaknya baris pada matriks B ( rank(B) = m ), maka matriks B mempunyai rank baris penuh.


11

2. Operasi matriks a. Operasi Penjumlahan Definisi II.B.4 ( Howard, 1985 : 27 ) Jika A dan B adalah sebarang dua matriks yang ukurannya sama, maka jumlah A + B adalah matriks yang didapatkan dengan menambahkan bersama – sama entri yang bersangkutan di dalam kedua matriks tersebut. Matriks – matriks yang ukurannya berbeda tidak dapat dijumlahkan. Contoh II.C.12 : Diberikan matriks : 5 3 A=  2 1

− 2 6  B=   4 − 3

2 C=  − 8

maka 3 9  A+ B =   6 − 2  sedangkan A + C dan B + C tidak didefinisikan karena matriks C ukurannya berbeda dengan matriks A dan matriks B. b. Operasi Perkalian Definisi II.B.5 ( Howard, 1985 : 28 ) Jika A adalah sebuah matriks m × r dan B adalah matriks r × n , maka hasil kali AB adalah matriks m × n yang entri – entrinya ditentukan sebagai berikut. Untuk mencari entri di dalam baris i dan kolom j dari AB, maka pilihlah baris i dari matriks A dan kolom j dari matriks B. Kalikanlah entri – entri yang bersangkutan dari baris dan


12

kolom tersebut bersama – sama dan kemudian tambahkanlah hasil perkalian yang dihasilkan. Contoh II.B.13 : Diberikan matriks : 1 2 4  A=  2 6 0

 4 1 4 3 B = 0 − 1 3 1  2 7 5 2

maka 12 27 30 13 AB =    8 − 4 26 12 Sifat II.B.1 ( Howard, 1985 : 33 ) Secara umum perkalian matriks tidak bersifat komutatif, yaitu tidak selalu berlaku AB = BA Contoh II.B.14 :  − 2 4 6 1 Diberikan matriks A =  dan matriks B =     3 1 4 1 dengan mengalikannya maka akan memberikan :  4 2 AB =   22 4 − 9 25 BA =   − 5 17  jadi AB ≠ BA


13

Definisi II.B.6 ( Howard, 1985 : 27 ) Jika A adalah suatu matriks dan k adalah suatu skalar, maka hasil kali ( product ) kA adalah matriks yang diperoleh dengan mengalikan masing – masing entri dari A oleh k. Contoh II.B.15 : 3 − 2 Diberikan A =   1 4  maka 3 − 2 6 − 4 2A = 2  =  1 4  2 8  dengan k = 2 Penjumlahan dua matriks, perkalian skalar dan perkalian dua matriks, memenuhi sifat sebagai berikut : 1). A + B = B + A

( Sifat komutatif pada penjumlahan )

2). A + (B + C ) = ( A + B ) + C

( Sifat asosiatif pada penjumlahan )

3). A(BC ) = ( AB )C

( Sifat asosiatif pada perkalian )

4). A(B + C ) = AB + AC

( Sifat distributif )

(B + C )A = BA + CA

( Sifat distributif )

5).

6). A(B − C ) = AB − AC 7).

(B − C )A = BA − CA

8). k (B + C ) = kB + kC 9). k (B − C ) = kB − kC 10).

(k + l )C = kC + lC


14

11).

(k − l )C = kC − lC

12).

(kl )C = k (lC )

13). k (BC ) = (kB )C = B (kC ) k, l adalah skalar C. Fungsi Determinan Definisi II.C.1 ( Howard, 1985: 67 ) Diberikan A adalah matriks persegi n × n . Fungsi determinan dinyatakan oleh det( A ), dan det( A ) didefinisikan sebagai jumlah semua hasil kali elementer bertanda dari A. Jumlah det( A ) dinamakan determinan A. Contoh II.C.1 : a det  11 a 21

a12  = a11 a 22 − a12 a 21 a 22  Selanjutnya akan diperlihatkan hubungan dari invers matriks dengan

determinan matriks. Definisi II.C.2 ( Howard, 1985 : 83 ) Jika A adalah matriks persegi, maka minor entri aij dinyatakan oleh M ij dan didefinisikan sebagai determinan submatriks A setelah baris ke i dan kolom ke j dihilangkan dari A. Bilangan (−1)

i+ j

M ij dinyatakan oleh C ij dan

dinamakan kofaktor entri aij . Contoh II.C.2 :  3 1 − 4 Diberikan A = 2 5 6  1 4 8 


15

Minor entri a11 adalah :

M 11

 3 1 − 4 5 6 = 2 5 6  =  = 16 4 8  1 4 8 

Kofaktor a11 adalah : C11 = (− 1) M 11 = M 11 = 16 1+1

Demikian juga, minor entri a32 adalah :

M 32

 3 1 − 4  3 − 4 = 2 5 6  =  = 26 2 6   1 4 8 

Kofaktor a32 adalah : C 32 = (− 1)

3+ 2

M 32 = − M 32 = −26

Determinan dari matriks A dapat dihitung dengan mengalikan entri – entri dalam baris pertama A dengan kofaktor – kofaktornya dan menambahkan hasil kalinya. Metode menghitung det( A ) ini dinamakan ekspansi kofaktor sepanjang baris pertama A. Contoh II.C.3 : 1 0  3 Diberikan matriks A = − 2 − 4 3   5 4 − 2

maka det ( A) = 3

−4 3 −2 3 −2 −4 −1 +0 4 −2 5 −2 5 4


16

= 3(− 4 ) − 1(− 11) + 0 = −1

Definisi II.C.3 (Howard, 1985:88) Jika A adalah sebarang matriks n × n dan C ij adalah kofaktor a ij , maka martiks C11 C12 C  21 C 22  ..... .....  C n1 C n 2

..... ..... ..... .....

C1n  C 2 n  .....   C nn 

Dinamakan matriks kofaktor A. Transpose matriks ini dinamakan adjoint dari A dan dinyatakan dengan adj ( A) . Contoh II.C.4 : 3 2 − 1 Diberikan A = 1 6 3  2 − 4 0  Sehingga matriks kofaktor A adalah : 6 − 16 12 4 2 16   12 − 10 16 

4 12   12  dan adjoint A adalah adj ( A) =  6 2 − 10 − 16 16 16 


17

D. Invers Matriks Definisi II.D.1 ( Howard , 1985 : 38 ) Jika A adalah matriks persegi, dan jika dapat dicari matriks B sehingga AB = BA = I , maka A dikatakan dapat dibalik ( invertible ) dan B dinamakan invers ( inverse ) dari A. Teorema II.D.1 ( Howard, 1985 : 39 ) Jika B dan C keduanya adalah invers dari matriks A, maka B = C. Bukti : Karena B adalah invers A, maka BA = I . Dengan mengalikan kedua ruas dari sebelah kanan dengan C maka akan memberikan (BA)C = IC = C . Tetapi

(BA)C = B( AC ) = BI = B , sehingga B = C Metode / cara mencari invers matriks : 1. Metode Adjoint Langkah – langkahnya adalah : a. Menentukan nilai determinan dari matriks b. Menentukan adjoint matriks c. Mengalikan Adjoint matriks dengan kebalikan determinan A −1 =

1 ⋅ adj ( A) det ( A)

Contoh II.D.1 : 1 0 0    Diberikan matriks C = 2 3 5 4 1 3


18

0 0  4  14 3 − 5 Adj (C) =  − 10 − 1 3  det (C ) = 4

0 0  1 0 0   4    3 − 5 =  7 / 2 3 / 4 − 5 / 4 Jadi C-1 = 1  14 4 − 10 − 1 3  − 5 / 2 − 1 / 4 3 / 4 

2. Metode Transformasi Elementer baris Diberikan An× n , dan A merupakan matriks non singular ( det ( A) ≠ 0 )

[A I ] → [I A ] −1

maka

Contoh II.D.2 : 1 1 Diberikan matriks A=   4 3

[A I ] = 14 

1 1 1 0   0 − 1 − 1 1  4b2 4 4 

1 1 0  3 0 1 1 4 b2 − b1

1 1 1 0 b1 + b2   0 − 1 − 4 1 

[

1 0 − 3 1  −1  = I A 0 1 4 − 1  

1 0 − 3 1   0 − 1 − 4 1 − b2

]

− 3 1  Jadi A−1 =    4 − 1


19

E. Kombinasi Linier Definisi II.E.1 ( Howard, 1985 : 148 ) Sebuah vektor w dinamakan kombinasi linier dari vektor – vektor v1 , v 2 ,.......v r jika vektor tersebut dapat diungkapkan dalam bentuk : w = k1v1 + k 2 v 2 + ....... + k r v r

dimana k1 , k 2 ,......., k r adalah skalar. Contoh II.E.1: Diambil vektor v1 = (1,2,−1) dan v 2 = (6,4,2) didalam R 3 , akan dinyatakan bahwa w = (9,2,7) adalah kombinasi linier dari v1 dan v 2 . Supaya w merupakan kombinasi linier dari v1 dan v 2 , maka harus ada skalar k1 dan k 2 sehingga w = k1v1 + k 2 v 2 diperoleh

(9,2,7 ) = k1 (1,2,−1) + k 2 (6,4,2) atau

(9,2,7 ) = (k1 + 6k 2 ,2k1 + 4k 2 ,−k1 + 2k 2 ) artinya k1 + 6 k 2 = 9 2 k1 + 4 k 2 = 2 − k1 + 2 k 2 = 7


20

atau dapat dituliskan : 9   1 6   2  =  2 4   k1   k     7  − 1 2  2  dengan menyelesaikan persamaan diatas diperoleh k1 = −3, k 2 = 2 w = −3v1 + 2v 2

Jadi

F. Dekomposisi Nilai Singular Sebelum dekomposisi nilai singular, terlebih dahulu dibahas mengenai nilai eigen dan vektor eigen. Berikut ini definisi dari vektor eigen dan nilai eigen. Definisi II.F.1 ( Howard, 1985 : 279 ) Jika A adalah matriks persegi n × n , maka vektor tak nol x didalam R n dinamakan vektor eigen dari A jika Ax adalah kelipatan skalar dari x, yaitu Ax = λx untuk suatu skalar λ . Skalar λ dinamakan nilai eigen dari A dan x

dikatakan vektor eigen yang bersesuaian dengan λ Mencari nilai eigen : menyelesaikan persamaan karakteristik det ( A − λI ) = 0 sehingga didapat akar – akar persamaannya. Mencari vektor eigen : menentukan basis untuk ruang solusi ( A − λI ) x = 0 untuk λ yang bersesuaian. Contoh II.F.1 : 4 2  A=  3 − 1


21

Persamaan karakteristiknya : 4 2   4 − λ − λI  = det  det   3 − 1   3

2   = (4 − λ )(− 1 − λ ) − 6 = 0 − 1 − λ  

(4 − λ )(− 1 − λ ) − 6 = 0 ⇒ −4 − λ − 4λ + λ2 − 6 = 0 ⇒ λ2 − 3λ − 10 = 0 ⇒ (λ − 5)(λ + 2 ) = 0 ⇒ λ1 = 5

λ 2 = −2

Nilai eigennya adalah λ1 = 5 dan λ 2 = −2  x Vektor eigen yang bersesuaian dengan λ1 = 5 , misalkan v1 =    y 2   x  0   − 1 2   x  0  4 − 5 = ⇒   3   =     − 1 − 5  y   0    3 − 6   y  0  Sehingga –x + 2y = 0

atau -x + 2y = 0 x = 2y, misal y = α

3x – 6y = 0 2α   2 maka v1 =   = α   α  1 

 2 Jadi vektor   merupakan vektor eigen yang bersesuaian dengan nilai eigen 1 

λ1 = 5 4 2  2 10  2 3 − 1 1  =  5  = 51         Definisi II.F.2 ( NN, 2007 : 6 ) Diberikan matriks Am×n , dengan rank(A) = r, nilai eigen dari matriks AT A adalah :

λ1 ≥ λ 2 ≥ ..... ≥ λ r > λ r +1 = ......... = λn = 0


22

dengan σ i = λi , dan i = 1, 2, 3,......,n disebut nilai singular dari matriks A. Contoh II.G.2 : 1 0 Tentukan nilai singular dari matriks A = 0 0 1 1 2 1 AT A =   1 1

3± 5   , sehingga nilai singular dari A adalah Nilai eigen dari AT A adalah    2  3+ 5 dan 2

3− 5 2

Definisi II.F.3 ( NN, 2007 : 11 ) Diberikan A matriks berukuran m × n , bilangan positif σ dikatakan nilai singular matriks A jika ada vektor tak nol u ∈ R m dan v ∈ R n , sedemikian sehingga Av = σ u dan AT u = σ v Dari pengertian nilai eigen dan nilai singular matriks A, dapat dinyatakan hubungan bahwa jika λ2 nilai eigen matriks AT A maka λ merupakan nilai singular matriks A. Definisi II.F.4 ( Howard, 1985 : 193 ) Sebuah himpunan dari vektor – vektor di dalam sebuah ruang perkalian dalam dinamakan himpunan orthogonal jika semua pasangan vektor – vektor yang berbeda di dalam himpunan tersebut orthogonal. Sebuah himpunan orthogonal dimana setiap vektor mempunyai norm / jarak sama dengan 1 dinamakan ortonormal.


23

Teorema II.F.1 ( Datta dalam Ariyanti, 2008 : 2 ) Jika diberikan A matriks berukuran m × n dengan rank r, maka terdapat matriks orthogonal U m×n dan Vm×n sedemikian sehingga A = USV T dengan S adalah matriks m × n dengan bentuk S = diag (∑,0 ) = diag (σ 1 , σ 2 ,......., σ r ,0,.......,0 ) Dengan σ 1 , σ 2 ,......, σ r adalah nilai – nilai singular dari A. Bukti : Dapat ditunjukan bahwa AT A dan AAT adalah matriks simetri. Oleh karena itu nilai eigen tak nolnya adalah positif dan sama serta akar positif dari nilai eigen didefinisikan sebagai nilai singular matriks A. Diberikan : V = [v1

v2

v3 .... v r

v r +1 .... v n ]

adalah matriks n × n yang kolomnya adalah vektor – vektor orthonormal. Misalkan rank(A) = r, bisa diasumsikan r kolom pertama dari V adalah vektor eigen yang bersesuaian dengan nilai eigen dari AT A , yaitu AT Avi = σ i vi , 2

untuk i = 1, 2, 3, ...., r. Sisanya, n – r kolom dalam V adalah vektor – vektor eigen dari AT A berkorespondensi dengan nilai eigen nolnya. Karena kolom dari V orthonormal, maka V matriks yang orthogonal. Dari sini terbentuk matriks V dengan elemen – elemen yang terdefinisi. Selanjutnya didefinisikan U sebagai berikut : untuk i = 1, 2,.....,r dibentuk ui = (1 σ i )Avi dimana himpunan {u1 , u 2 ,....., u r } adalah orthonormal. Sebanyak r vektor orthonormal ini membentuk r kolom pertama dari U.


24

Selanjutnya diperlihatkan : U T AV = U T A[v1 .... vr

vr +1 .... vn ]

= U T [Av1 .... Av r

= U T [σ 1u1 .... σ r u r

[

Av r +1 .... Av n ] 0 .... 0]

= σ 1U T u1 .... σ rU T u r = [σ 1e1 .... σ r er

0 .... 0

0 .... 0] = S

]

Contoh II.F.3 : 1 1 Tentukan dekomposisi nilai singular matriks A = 0 1 1 0 2 1  AT A =   , nilai eigen dari matriks ini adalah λ1 = 1, λ2 = 3 , masing – 1 2 

masing

berkorespondensi

dengan

vektor

eigen

− 2  2 v1 =   2  2  

dan

 2  v2 =  2  , himpunan vektor – vektor eigen tersebut orthonormal.  2   2  Sehingga dapat dibentuk matriks orthogonal V : V = [v1

− 2 2 v2 ] =   2  2

2  2 2  2  −1

Kemudian matriks U dibentuk dari vektor eigen ui = σ i Avi , yaitu 2 6     0 6     u1 =  2  , dan u2 =  6  2 6    6  − 2   2  6  


25

sehingga bentuk matriks orthogonal U adalah :

U = [u1

 0   u2 ] =  2 2 − 2  2 

1 Matriks singular S =  0

2 6  6 6  6  6  6  0 3 

Dekomposisi nilai singular :  0 1 1    A = 0 1 =  2 2 1 0 − 2  2 

2 6  6 6  1 6  0 6  6 

U

 0  − 2 2 3   2 2 

S

2  2 2  2 

VT

G. Pseudoinvers ( Invers semu suatu matriks Am×n ) Definisi II.G.1 ( Boullion dan Odell, 1971 : 41 ) Diberikan matriks A berukuran m × n , sebuah matriks A+ berukuran n × m dikatakan sebagai pseudoinvers dari matriks A jika dan hanya jika A+

memenuhi sifat – sifat berikut : 1. A + AA + = A + 2. AA + A = A 3.

( A A)

= A+ A

4.

(AA )

= AA +

+

T

+ T

Teorema II.G.1 Untuk sebuah matriks Am×n , terdapat dengan tunggal matriks An+×m


26

Bukti : Akan dibuktikan sifat ketunggalan dari invers semu suatu matriks Misal A # adalah sebarang matriks yang memenuhi sifat 1 sampai sifat sampai 4 pada Definisi II.G.1 Dari Definisi II.G.1.2

(

)

AA # = AA + A A # Dari persamaan ini, dan karena matriks – matriks AA + dan AA # simetri, menurut Definisi II.G.1.4

(

AA # = AA #

) = ((AA )(AA )) = (AA ) (AA ) T

+

#

T

# T

+ T

(

)

= AA # AA + = AA # A A + = AA +

Dengan cara yang sama, A#A = A+A. Dengan mengalikan AA# = AA+ dari kiri dengan A# dan menurut Definisi II.G.1.1 maka diperoleh A# AA# = A# AA+ atau A# = A# AA+ . Selanjutnya, dengan mengalikan A#A = A+A dari kanan dengan A+ diperoleh A# A A+ = A+ AA+ = A+. Hal ini membuktikan, A# = A+ , artinya A+ tunggal Selanjutnya, dibuktikan eksistensi matriks invers semu dari A. Menurut Teorema II.F.1, untuk setiap matriks Am× n terdapat matriks-matriks orhogonal U, V dan matriks S sedemikian sehingga A = USVT dengan S = diag (∑,0 ) = diag (σ 1 , σ 2 ,......., σ r ,0,.......,0 )


27

didefinisikan :

(

)

(

S + = diag ∑ + ,0 = diag σ 1−1 , σ 2−1 ,......., σ r−1 ,0,.......,0

)

Akibatnya, A+ = (USVT)+ = VS+UT . Dibuktikan, VS+UT memenuhi keempat sifat pada Definisi II.G.1 Sifat –sifat : 1. A+AA+ = VS+UTAVS+UT = VS+UTUSVTVS+UT = VS+SS+UT = VS+UT = A+ 2. AA+A = AVS+UTA = USVTVS+UTUSVT = USS+SVT = USVT = A ; dengan mengingat sifat SS+. 3. Dengan menggunakan (S+S)T = S+S dan A+A = VS+ UT USVT = VS+ SVT, (A+A)T = (VS+UTUSVT)T = (VS+SVT)T = V(S+S)TVT = VS+SVT = A+A 4. Dengan menggunakan (SS+)T = SS+ dan AA+ = USS+UT (AA+)T = (USVTVS+UT)T = (USS+UT)T = U(SS+)TUT = USS+UT = AA+ Matriks A+ ini disebut p-invers dari A, yang merupakan singkatan dari pseudo-inverse dan diartikan sebagai invers semu dari A.


28

Lemma II.G.1 Diberikan C matriks atas bilangan real. 1. Jika C matriks dengan rank baris penuh ( jika m < n dan rank (C) = m),

CC T non singular, maka CT(CCT)-1 adalah invers semu kanan dari C. 2. Jika C matriks dengan rank kolom penuh ( jika m > n dan rank(C) = n),

C T C non singular, maka (CTC)-1CT adalah invers semu kiri dari C.

Bukti : 1. X = CT(CCT)-1 adalah invers semu dari C, sebab : CXC

= C CT(CCT)-1 C = C

XCX

= CT(CCT)-1CCT(CCT)-1 = CT(CCT)-1 = X

(XC)T = (CT(CCT)-1C)T = CT ((CCT)-1)TC = CT(( CCT)T)-1C = CT(CCT)-1 C = XC (CX)T = ( CCT(CCT)-1)T = ((CCT)-1)TCCT = ((CCT)T)-1CCT = (CCT)-1CCT


29

= CCT(CCT)-1 = CX Dengan demikian X adalah invers semu dari C atau CT(CCT)-1 = C+. 2. X

= (CTC)-1CT adalah invers semu dari C, sebab :

CXC

= C(CTC)-1CT C = C

XCX

= ((CTC)-1CTC(CTC)-1CT = (CTC)-1CT = X

(XC)T = (CTC)-1CTC)T = CT((CTC)-1CT)T = CTC((CTC)-1)T = CTC((CTC)T)-1 = CTC(CTC)-1 = (CTC)-1CTC = XC (CX)T = (C(CTC)-1CT)T = ((CTC)-1CT )T CT = C((CT C)-1)TCT = C((CT C)T)-1CT = C(CT C)-1CT = CX


30

Dengan demikian X adalah invers semu dari C atau (CTC)-1CT = C+. Contoh II.G.1 : Tentukan pseudoinvers ( invers semu ) dari matriks : 1 −1 0  1. A =  0 1 1 matriks A memiliki rank baris penuh dan m = 2 , n = 3 (m < n ) , maka menggunakan invers semu kanan

(

A + = AT AAT

)

−1

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

 1 0   2 − 1  1 − 1 0   − 1 1  =   AA =   0 1 1  0 1   − 1 2    T

(AA )

T −1

1 2 1  =  3  1 2 

(

maka A + = AT AAT

)

−1

 1 0   1 2 1  =  − 1 1  ⋅   0 1 3 1 2    2 1  1 = −1 1 3   1 2


31

2 1  2. B = 1 2 1 1  matriks B memiliki rank kolom penuh dan m = 3 , n = 2 (m > n ) , maka menggunakan invers semu kiri

(

B + = BT B

)

−1

BT

6 5  BT B =   5 6 

(B B ) T

−1

=

1  6 − 5 11 − 5 6 

− 5  2 1 1 6 11 ⋅ maka B + =  11 1 2 1 − 5 6  11  11   1  −4 7 11 11 =  11 − 411 7 11 111 H. Kekongruenan Definisi II.H.1 Jika m suatu bilangan bulat positif maka a kongruen dengan b modulo m ditulis a ≡ b(mod m ) bila dan hanya bila m membagi (a − b ) . Jika m tidak membagi (a − b ) maka dikatakan bahwa a tidak kongruen dengan b modulo m ( ditulis a ≡ b(mod m) ) Definisi II.H.1 tersebut dapat ditulis bahwa jika m > 0 maka m (a − b ) bila dan hanya bila a ≡ b(mod m ) . m (a − b ) berarti ada bilangan bulat k sehingga


32

(a − b ) = mk ,

karena (a − b ) = mk maka sama artinya dengan a = mk + b ,

sehingga a ≡ b(mod m ) bila dan hanya bila a = mk + b . Contoh II.H.1 : 25 ≡ 1(mod 4 ) sebab 4 membagi ( 25 – 1 ). 31 ≡ 5(mod 5) sebab 6 tidak membagi ( 31 – 5 ). Teorema II.H.1 Jika

a

bilangan bulat dan m,b bilangan bulat positif, maka

a ≡ b(mod m ) bila dan hanya bila ada bilangan bulat k sehingga a = mk + b. Bukti : Diketahui a dan b bilangan – bilangan bulat dan m > 0 , (⇒ ) Berdasarkan Definisi II.H.1, a ≡ b(mod m ) ini berarti m (a − b ) , karena (a − b ) = mk maka sama artinya dengan a = mk + b dengan 0 ≤ b < m . (⇐) a = mk + b dapat dinyatakan sebagai (a − b ) = mk , ini berarti m (a − b ) , maka sama artinya dengan a ≡ b(mod m ) . Contoh II.H.2 : 26 ≡ 4(mod 11) sama artinya dengan 26 = 11.2 + 4 I. Kriptografi Kriptografi berasal dari bahasa yunani “ cryptos “ artinya rahasia, sedangkan “ graphein “ artinya tulisan. Jadi secara morfologi kriptografi berarti tulisan rahasia. Ada beberapa definisi kriptografi yang telah dikemukakan di dalam berbagai literatur. Definisi yang kita pakai dalam penelitian ini : Kriptografi


33

adalah ilmu dan seni untuk menjaga keamanan pesan. Kata “ seni “ di dalam definisi di atas berasal dari fakta sejarah bahwa pada masa – masa awal sejarah kriptografi, setiap orang mungkin mempunyai cara yang unik untuk merahasiakan pesan. Pada perkembangan selanjutnya, kriptografi berkembang menjadi sebuah disiplin ilmu sendiri karena teknik – teknik kriptografi dapat diformulasikan secara matematik sehingga menjadi sebuah metode yang formal. 1. Prinsip Kerja Kriptografi Pembahasan penulisan pada kriptografi dapat ditulis dalam bahasa matematika. Fungsi – fungsi yang mendasar dalam kriptografi adalah enkripsi dan deskripsi. Enkripsi adalah proses mengubah suatu pesan asli ( plaintext ) menjadi suatu pesan dalam bahasa sandi ( ciphertext ). C = A⋅ P

dimana P = pesan asli A = kunci enkripsi C = pesan dalam bahasa sandi Sedangkan deskripsi adalah proses mengubah pesan dalam suatu bahasa sandi menjadi pesan asli kembali.

P = A+ ⋅ C A + = kunci deskripsi


34

Umumnya, selain menggunakan fungsi tertentu dalam melakukan enkripsi dan deskripsi, seringkali fungsi itu diberi parameter tambahan yang disebut dengan istilah kunci. 2. Jenis – jenis Kunci Jenis kunci dalam kriptografi terbagi menjadi 2, yaitu kunci simetris dan kunci asimetris. a). Kunci Simetris Ini adalah jenis kriptografi yang paling umum dipergunakan. Kunci untuk membuat pesan yang disandikan sama dengan kunci untuk membuka pesan yang disandikan itu. Jadi pembuat pesan dan penerimanya harus memiliki kunci yang sama persis. Siapapun yang memiliki kunci tersebut, termasuk pihak – pihak yang diinginkan, dapat membuat dan membongkar rahasia ciphertext. Problem yang paling jelas disini terkadang bukanlah masalah pengiriman ciphertextnya, melainkan masalah bagaimana menyampaikan kunci simetris tersebut kepada pihak yang diinginkan. b). Kunci Asimetris Kunci asimetris adalah pasangan kunci – kunci kriptografi yang salah satunya dipergunakan untuk proses enkripsi dan untuk deskripsi. Semua orang yang mendapatkan kunci publik dapat menggunakannya untuk mengenkripsikan satu pesan, sedangkan hanya satu orang saja yang memiliki rahasia tertentu, dalam hal ini kunci privat, untuk melakukan pembongkaran terhadap sandi yang dikirim untuknya.


35

Dengan cara seperti ini, jika seorang pihak pertama mengirim pesan untuk pihak kedua, pihak pertama tersebut dapat merasa yakin bahwa pesan tersebut hanya dapat dibaca oleh pihak yang bersangkutan, karena hanya dia yang bisa melakukan deskripsi dengan kunci privatnya. Tentunya si pihak pertama harus memiliki kunci publik milik pihak kedua untuk melakukan enkripsi. Pihak pertama bisa mendapatkannya dari pihak yang bersangkutan, ataupun dari pihak ketiga yang dipercaya. 3. Hill Cipher Hill Cipher termasuk dalam salah satu kriptosistem polialfabetik, artinya setiap karakter alfabet bisa dipetakan ke lebih dari satu macam karakter alfabet. Hill Cipher ditemukan pada tahun 1929 oleh Lester S. Hill. Hill Cipher ini menggunakan matriks persegi sebagai kuncinya. Secara singkat, Hill Cipher dapat dijelaskan sebagai berikut. Misalkan n adalah bilangan bulat positif, didefinisikan

P = C = (Z 26 )

n

dengan P adalah himpunan plaintext dan C adalah himpunan ciphertext. Ide dari Hill Cipher adalah untuk membuat n kombinasi linier dari n karakter alfabet di dalam satu elemen plaintext, sehingga menghasilkan n karakter alfabet sebagai elemen dari ciphertext. Misalkan n = 2, maka dapat dituliskan elemen – elemen plaintext dalam bentuk x = ( x1

x 2 ) dan elemen – elemen ciphertext sebagai


36

y = ( y1

y 2 ) . Dalam hal ini, y1 dan y 2 adalah kombinasi linier dari x1

dan x 2 . Contoh II.I.1 : Diberikan : y1 = 11x1 + 3 x 2 y 2 = 8 x1 + 7 x 2 Kombinasi linier diatas dapat dituliskan dalam notasi matriks sebagai berikut :  y1  11 8   x1   y  =  3 7 ⋅  x    2  2  ( Ariyus, 2006 : 27 )


BAB II LANDASAN TEORI. himpunan bilangan bulat dan diberi simbol dengan hurup besar B. Anggota

Recommend Documents