Teknologi dan Informasi: Belalajar Matematika MATRIKS , Rumus rumus

PENGANTAR MATRIKS

1.1. Pendahuluan

Dalam kehidupan sehari-hari sering dijumpai masalah yang membutuhkan perlakuan khusus. Hal itu dimaksudkan untuk keperluan penyajian dan pencarian metode penyelesaiaannya. Salah satu bentuk penyajian adalah menyusun item-item dalam bentuk baris dan kolom.

?Definisi 1.1.1 Matriks adalah susunan segiempat siku-siku dari bilangan-bilangan.

Ukuran (ordo) suatu matriks ditentukan oleh banyaknya baris dan banyaknya kolom yang dimilikinya. Bilangan-bilangan dalam suatu matriks disebut unsur (entri) dari matriks tersebut. Notasi matriks digunakan huruf besar, misal A, B, …dan notasi unsur digunakan huruf kecil yang berindek, misal a_ij adalah unsure dari suatu matriks pada baris ke-i dan kolom ke-j.

Secara umum, misal matriks A yang berukuran mxn, dapat ditulis

sebagai berikut

A _mxn = ,

dengan a_ij adalah unsur dari matriks A pada baris-i dan kolm-j.

CContoh Diberikan suatu matriks berukuran 3x3

A = .

Maka 3 adalah unsur dari A pada baris-1 dan kolom-2, 5 adalah unsur A pada baris-2 dan kolom-3.

1.2. Jenis-jenis Matriks

Dalam subbab ini akan dibicarakan beberapa jenis matriks. Pembahasan dibatasi pada jenis-jenis matriks yang banyak digunakan dalam materi selanjutnya.

?Definisi 1.2.1 Matriks A disebut matriks persegi jika banyaknya baris sama dengan banyaknya kolom. Notasi A_nxn

CContoh Matriks A, B dan C berikut masing-masing merupakan matriks persegi.

A = B = C =

?Definisi 1.2.2 Matriks A disebut matriks kolom jika banyaknya kolom adalah satu. Notasi A_mx1

CContoh

A = B = C =

?Definisi 1.2.3 Matriks A disebut matriks segitiga atas (bawah) jika setiap unsure di bawah(atas) diagonal utama adalah nol.

CContoh

A = B = C =

D = E = F =

Matriks A, B, C masing-masing merupakan matriks segitiga atas, sedangkan matriks D, E dan F masing-masing merupakan matriks segitiga bawah.

?Definisi 1.2.4 Matriks A disebut matriks identitas jika setiap unsur pada diagonal utamanya adalah satu dan unsur-unsur lainnya adalah nol. Notas I_nxn

CContoh

A = B =

?Definisi 1.2.5 Matriks B disebut matriks transpose A jika unsur pada baris matriks B didapat dari unsur pada kolom matriks A. Notas B = A’

CContoh Misalkan diberikan tiga matriks A , B dan C, sebagai berikut

A = , B = , C =

Maka didapat A’ = , B’ = dan C’ =

?Definisi 1.2.6 Matriks persegi A _nxn= [a_ij] disebut invertible (mempunyai balikan/invers) jika terdapat B_nxn sehingga berlaku AB = I dan BA = I, dengan I matriks identitas. Notasi B = A^-1

CContoh Misalkan diberikan matriks A , dengan A = . Maka B = adalah matriks invers dari A atau ditulis B = A^-1.

Hal itu karena AB = = = I

dan BA = == I.

Dengan kata lain, terdapat matriks B sehingga berlaku AB = I dan BA = I atau A adalah matriks yang mempunyai invers(invertible).

?Definisi 1.2.7 Matriks A disebut matriks eselon baris (MEB) jika memenuhi

i. baris nol terletak pada baris bagian bawah

ii. pada baris tidak nol, unsur tidak nol pertama (pivot) baris yang lebih bawah terletak pada kolom yang lebih kanan

CContoh Diberikan matriks-matriks berikut

A = B = C =

D = E =

Maka matriks A, B dan C masing-masing adalah MEB, sedangkan D dan E bukan merupakan MEB. Eksistensi MEB dari suatu matriks adalah tidak tunggal.

?Definisi 1.2.8 Matriks A disebut matriks eselon baris tereduksi (MEBT), jika memenuhi

i. A merupakan MEB

ii. Pivot setiap baris tidak nol adalah satu

iii.Pada kolom yang memuat pivot, unsur selain pivot adalah nol

CContoh Diberikan matriks-matriks berikut

A = B = C =

D = E =

Maka A, B dan C masing-masing merupakan MEBT, sedangkan D dan E bukan merupakan MEBT. Eksistensi MEBT dari suatu matriks adalah tunggal.

1.3

Operasi pada Matriks

Subbab ini membahas tentang operasi pada matriks. Operasi yang dibicarakan meliputi operasi jumlah dua matriks, operasi hasilkali matriks dengan skalar dan operasi hasilkali dua matriks. Sebelum masuk pada pembahasan operasi matriks akan diberikan pengertian kesamaan dua matriks.

?Definisi 1.3.1 Dua matriks A dan B dikatakan sama jika ukuran kedua matriks sama dan unsur yang seletak juga sama.

CContoh Misalkan A _mxn = [a_ij] dan B_mxn = [b_ij]. A = B jika a_ij= b_ij, untuk setiap i, j.

Definisi kesamaan dua matriks di atas memperlihatkan bahwa kajian tentang matriks itu meliputi setiap unsur-unsurnya.

?Definisi 1.3.2 Misalkan A _mxn = [a_ij] dan B_mxn = [b_ij]. Jumlah matriks A dan B adalah suatu matriks yang unsur-unsurnya merupakan jumlah unsur-unsur yang seletak dari matriks A dan B.

Notasi : A + B = [ c_ij ], dengan c_ij = a_ij + b_ij, untuk setiap i,j.

CContoh Misalkan A = dan B = .

Maka A + B = + = =

?Definisi 1.3.3. Misalkan A _mxn = [a_ij] dan k suatu bilangan riil. Hasilkali matriks A dan k adalah suatu matriks yang unsur-unsurnya merupakan hasilkali unsur-unsurnya dengan k

Notasi : kA = [ c_ij ], dengan c_ij = ka_ij, untuk setiap i,j.

CContoh Misalkan A = dan k=9

Maka kA = 9. = =

?Definisi 1.3.4 Misalkan A _mxn = [a_ij] dan B_nxp = [b_jk]. Hasilkali matriks A dan B adalah suatu matriks yang unsur pada baris-i dan kolom-k merupakan jumlahan dari hasilkali-hasilkali unsur pada baris-i matriks A dan unsur pada kolom-k matriks B.

Notasi : A B_mxp = [ c_ik ], dengan c_ik = , i = 1, 2, …, m, k=1,2,…,p

CContoh Misalkan A = dan B =

Maka AB = . = =

CContoh Misalkan A _3x3 = , matriks vector X_3x1 =

dan B_3x1 = . Jika AX = B maka diperoleh hubungan sebagai berikut

AX = B Û . = Û = .

Dengan menggunakan sifat kesamaan dua matriks diperoleh hubungan

a₁₁x + a₁₂ y + a₁₃ z = b₁

a₂₁x + a₂₂ y + a₂₃ z = b₂

a₃₁x + a₃₂ y + a₃₃ z = b₃.

SISTEM PERSAMAAN LINIER (SPL)

2.1. Persamaan Linier (PL)

?Definisi 2.1.1 Persamaan Linier dengan n variabel x₁, x₂, …, x_n adalah suatu persamaan yang berbentuk

a₁ x₁ + a₂ x₂ + … + a_n x_n = b,

dengan a₁, a₂, …, a_n, b bilangan riil.

Dalam suatu persamaan linier, variabel yang digunakan berderajat nol atau satu, variabel bukan fungsi trigonometri dan tidak terjadi perkalian antara variabelnya.

CContoh

1. 2 x + 3y - 6z = 9 adalah suatu persamaan linier dengan 3 variabel,

2. x₁ + 3x₂ + 2x₃ + 8x₄ + 4= 0 adalah suatu persamaan linier dengan 4 variabel.

3. 6x² + 2y – 3z = 1, bukan persamaan linier sebab memuat variable berpangkat 2

4. 2 sin x – 3 cos x + 4 y = 5, bukan persamaan linier sebab memuat fungsi trigonometrik

5. 6xy + 3y + z = 7 bukan persamaan linier sebab memuat hasl kali dua variable.

?Definisi 2.1.2 Solusi (selesaian) dari persamaan linier a₁ x₁ + a₂ x₂ + … + a_n x_n = b adalah pasangan n-bilangan terurut (s₁, s₂, …, s_n) yang jika s₁ disubstitusikan ke x₁, s₂ disub-stitusikan ke x₂, …, s_n disubstitusikan ke x_n maka berlaku a₁ s₁ + a₂ s₂ + … + a_n s_n = b

?Himpunan semua solusi dari persamaan linier a₁ x₁ + a₂ x₂ + … + a_n x_n = b disebut Himpunan Solusi (HS).

CContoh

1. Persamaan 3x + 7 = 0, untuk x bilangan bulat. Maka tidak terdapat x bilangan bulat yang memenuhi persamaan linier tersebut. Jadi, himpunan solusinya (HS) adalah himpunan kosong. Ditulis HS = { }

2. Himpunan Solusi dari persamaan linier 2x = 8 adalah HS = {4}.

3. Himpunan Solusi dari persamaan linier 2x + 3y + z = 7 adalah HS = {(s, t, 7-2s-3t/ s, t Î R}.

4. Proses penyelesaian : Dalam HS dari persamaan linier ini, terdapat dua variable bebas, yaitu variable x dan y. Untuk menentukan nilai variable z, dapat ditentukan dengan mensubstitusikan variable x dan y ke persamaan. Hasil perhitungan diperoleh nilai z = 7-2s-3t. Jadi, HS = {(s, t, 7-2s-3t ) / s, t Î R }.

( Hasil HS ini, dijelaskan pada waktu kuliah)

2.2. Sistem Persamaan Linier (SPL)

?Definisi 2.2.1 Sistem Persamaan Linier (SPL) dengan n variabel x₁, x₂, …, x_n dan m persamaan adalah suatu sistem yang berbentuk

a₁₁ x₁ + a₁₂ x₂ + … a_1j x_j + … + a_1n x_n = b₁

a₂₁ x₁ + a₂₂ x₂ + … a_2j x_j + … + a_2n x_n = b₂

. . . . . . . .

**(1)

a_m1 x₁ + a_m2 x₂ + … a_mj x_j + … + a_mn x_n = b_m

dengan a_ij Î R,I=1,2, …, m dan j=I,2, … , n.

?Definisi 2.2.2 Solusi (sesaian) dari Sistem Persamaan Linier (**) adalah pasangan n-bilangan terurut (s₁, s₂, …, s_n) yang jika s₁ disubstitu-sikan ke x₁, s₂ disubstitusikan ke x₂, …, s_n disubstitusikan ke x_n maka berlaku a_i1 s₁ + a_i2 s₂ + … + a_in s_n = b_i, i=1,2, …, m

Secara lengkap, jika (s₁, s₂, …, s_n) dari SPL (**) maka (s₁, s₂, …, s_n) merupakan solusi dari setiap persamaan dalam SPL (**). Artinya berlaku

a₁₁ s₁ + a₁₂ s₂ + … a_1j s_j + … + a_1n s_n = b₁

a₂₁ s₁ + a₂₂ s₂ + … a_2j s_j + … + a_2n s_n = b₂

. . . . . . . .

a_m1 s₁ + a_m2 s₂ + … a_mj s_j + … + a_mn s_n = b_m

CHimpunan semua solusi dari Sistem Persamaan Linier (**) disebut Himpunan Solusi

Notasinya HS

Sistem Persamaan Linier yang mempunyai solusi disebut Konsisten dan Sistem yang tidak mempunyai selesaian disebut tidak konsisten

CContoh

Diberikan suatu SPL sebagai berikut :

1. 2x + 3y =7 2. x + 2y = 5 3. 2x + 5y = 7

3x + y =7 2x + 4y = 10 6x + 15y = 10

¨Penyelesaian.

§Berdasarkan SPL di atas maka pasangan bilangan (2,1) merupakan selesaian dari SPL (1) karena x=2 dan y=1 memenuhi kedua persamaan, yaitu 2 . 2 + 3 . 1 = 7 dan 3 . 2 + 1 . 1 = 7 sehingga diperoleh HS = { (2,1) }.

§Pada SPL (2), persamaan-2 merupakan 2 kali persamaan-1 sehingga SPL mempunyai satu persamaan dengan 2 variabel. Maka terdapat 1 variable bebas dan misal variabel bebasnya adalah y. Variabel bebas y dapat dipilih y = t, t bilangan riil. Substitusikan y = t ke persamaan sehingga didapat nilai x = 7-2t . Jadi HS = {(7-2t, t) / t Î R}.

§Pada SPL(3), tidak terdapat pasangan bilangan (x,y) yang memenuhi kedua persamaan. Sebab, jika memenuhi persamaan 1 maka 6x + 15y = 3(2x + 5y) = 3 . 7 = 21 ¹ 10, sehingga HS = { }.

Untuk melihat tafsiran geometri dari selesaian suatu SPL, diberikan SPL dengan 2 persamaan dan 2 variabel, sebagai berikut :

a₁ x + b₁ y = c₁

a₂ x + b₂ y = c₂,

dengan a₁, a₂, b₁ dan b₂ konstanta riil tidak nol.

Grafik persamaan-persamaan ini merupakan garis, misal garis l₁ dan garis l₂. Karena titik (x,y) terletak pada sebuah garis jika dan hanya jika bilangan-bilangan x dan y memenuhi persamaan tersebut, maka selesaian SPL tersebut akan bersesuaian dengan titik perpotongan dari garis l₁ dan garis l₂. Terdapat 3 (tiga) kemungkinan, yaitu :

(a). garis l₁ dan garis l₂ sejajar, yaitu jika tidak terdapat titik perpotongan sehingga sistem tidak mempunyai selesaian

(b). garis l₁ dan garis l₂ berpotongan pada satu titik, sehingga sistem hanya mempunyai satu (tunggal) selesaian.

(c). garis l₁ dan garis l₂ berimpit artinya terdapat takterhingga banyak titik perpotongan. Dalam hal ini sistem mempunyai takterhingga banyak selesaian. Biasa dikatakan SPL mempunyai banyak solusi.

Secara visual dapat digambarkan, sebagai berikut :

Y y y

X x x

l₁ l₂ l₁ l₂ l₁ dan l₂

a) tidak ada solusi (b) satu solusi (c) takterhingga banyak solusi

Berdasarkan ilustrasi kasus di atas, maka SPL mempunyai tiga kemungkinan yang berkaitan dengan selesaian, yaitu tidak mempunyai selesaian, mempunyai satu selesaian dan mempunyai takterhingga banyak selesaian.

2.3.

Metode Penyelesaian SPL

2.3.1. Operasi Pers. Linier (OPL)

Metode dasar untuk menyelesaikan suatu SPL adalah mengganti sistem yang diberikan dengan sistem baru. Sistem baru yang mempunyai himpunan selesaian (HS) sama, dengan pemecahan yang lebih mudah. Sistem baru ini diperoleh dari suatu tahapan dengan menerapkan suatu langkah operasi. Operasi-operasi yang dilakukan dimaksudkan untuk menghilangkan variabel-variabel secara sistematis. Operasi Persamaan Linier (OPL) tersebut adalah

mengalikan suatu persamaan dengan skalar riil tidak nol, k

2. menukar letak dua persamaan

3. mengganti suatu persamaan dengan persamaan tersebut + k kali persamaan lain

Untuk menyelesaikan suatu SPL dapat dilakukan dengan satu atau lebih operasi persamaan linier (OPL).

CContoh Diberikan suatu SPL dengan 3 persamaan dan 3 variabel

1 x + 2y + 3z = 6

2x + 3y + 2z = 7 (2)

3x + y + 2z = 6

¨Penyelesaian. Untuk menyelesaikan SPL di atas digunakan langkah-langkah OPL :

§persamaan 2 diganti dengan persamaan-2 + (-2) kali persamaan-1, sehingga diperoleh SPL baru, yaitu

x + 2y + 3z = 6

0x+ -1 y - 4z = -5 (3)

3x + y + 2z = 6

§persamaan 3 pada SPL (3) diganti dengan persamaan 3 + (-3) kali persamaan 1, sehingga diperoleh SPL baru, yaitu

x + 2y + 3z = 6

- y - 4z = - 5 (4)

- y - 7z = -12

§persamaan 3 pada SPL (4) diganti dengan persamaan 3 + (-1) persamaan 2 sehingga diperoleh SPL baru, yaitu

x + 2y + 3z = 6

- y - 4z = - 5 (5)

-3z = - 3

§Berdasarkan persamaan 3 pada SPL (5), didapat z = 1. Dengan mensubstitusikan z=1 ke persamaan 2 diperoleh -y – 4 . 1 = -5 sehingga didapat y = 1. Kemudian, dengan mensubstitusikan z=1 dan y =1 ke persamaan 1 diperoleh x + 2 . 1 + 3 . 1 = 6 sehingga didapat x = 1. Dengan demikian didapat HS = { (1,1,1) }.

2.3.2.

Operasi Baris Elementer (OBE)

Proses penyelesaian SPL pada Contoh di atas, perbedaan SPL (1), SPL (2) hingga SPL (5) terletak pada koefisiennya, sedangkan variabel dan tanda “=” tetap. Oleh karena itu, untuk menyelesaikan suatu SPL dapat dilakukan dengan hanya mengoperasikan koefisen-koefisien dari setiap persamaannya. Hal ini dapat dilakukan dengan menggunakan operasi matriks.

Sistem Persamaan Linier (SPL **1) dengan m persamaan dan n variabel

a₁₁ x₁ + a₁₂ x₂ + … a_1j x_j + … + a_1n x_n = b₁

a₂₁ x₁ + a₂₂ x₂ + … a_2j x_j + … + a_2n x_n = b₂

. . . . . . . .

a_m1 x₁ + a_m2 x₂ + … a_mj x_j + … + a_mn x_n = b_m

dapat disajikan secara matriks A_mxn X_nx1 = B_mx1 dengan

A_mxn = X_nx1 = B_mx1 =

Untuk menyelesaikan SPL (1) digunakan matriks yang unsur-unsurnya merupakan gabungan unsur-unsur dari A dan B. Matriks ini dinamakan matriks lengkap dan notasinya [A|B], atau

[A | B] = .

Untuk proses pengerjaan pencarian HS, tidak menggunakan operasi persamaan linier (OPL). Operasi-operasi yang digunakan untuk menyelesaikan SPL melalui [A|B] adalah Operasi Baris Elementer (OBE). OBE adalah suatu operasi yang hanya melibatkan unsure (bilangan) dalam suatu matriks. OBE terdiri dari 3 (tiga) jenis langkah dan dapat digunakan satu atau semuanya.

Operasi Baris Elementer (OBE)

No	Operasi	Notasi
1	Mengalikan baris-i dengan konstanta tidak nol k	kR_i
2	Menukar baris-i dengan baris-j	R_i«R_j
3	Mengganti baris-j dengan baris j + k baris-i	R_j+kR_i

Operasi Baris Elementer tidak merubah HS dari sistem persamaan linier. Artinya SPL baru yang diperoleh dari SPL lama dengan menggunakan OBE, mempunyai selesaian yang sama. Untuk mempertegas hal ini, didefinisikan pengertian matriks ekivalen baris.

?Definisi 2.3.2.1 Dua matriks disebut matriks ekivalen baris jika salah satu matriks dapat diperoleh dengan melakukan OBE sebanyak hingga kali pada matriks yang lain.

Berdasarkan Definisi 2.3.2.1, dua sistem persamaan linier yang berkaitan dengan dua matriks yang ekivalen baris mempunyai selesain yang sama. Hal ini dipertegas dalam teorem berikut.

?Teorema 2.3.2.2 Jika matriks lengkap dari dua SPL merupakan matriks ekivalen baris maka kedua SPL mempunyai solusi yang sama.

Notasi : ~

CContoh Diberikan SPL dengan 3 persamaan dan 3 variabel, sebagai berikut

x + 2y + z = 0

3x + 8y + 7z = 8

2x + 7y + 9z = 15

®Penyelesaian. SPL dapat ditulis secara matriks A_3x3 X_3x1 = B_3x1, dengan

A = X = B = .

Matriks lengkap dari SPL adalah

[A|B] =

Untuk menyelesaikan SPL ini, dilakukan dengan membuat koefisien x pada persamaan-2 dan persamaan-3 menjadi nol atau unsur a₂₁ dan a₃₁ adalah nol. Untuk dilakukan operasi baris berikut

[A|B] = ~R₂+(-3)R₁

~R₃+(-2)R₁ ~ ½ R₂

~R₃+(-3)R₂.

Matriks terakhir merupakan matriks lengkap dari SPL

x + 2y + z = 0

y + 2z = 4

z = 3.

Substitusi z=3 ke persamaan-2 didapat y + 2 . 3 = 4 sehingga y = -2. Dengan mensubstitusikan z=3 dan y=-2 ke persamaan-1 diperoleh x + 2 . (-2) + 3 = 0 sehingga x = 1.

HS = {(1,-2,3)}.

2.3.3.Eliminasi Gauss dan Gauss-Jordan

Telah diketahui bahwa setiap SPL dapat diselesaikan dengan mengubah matriks lengkapnya menjadi suatu matriks tertentu sehingga selesaiannya dapat segera diperoleh. Maka kecepatan dalam menyelesaikan SPL tergantung pada proses pengubahan matriks lengkap ke bentuk matriks yang spesifik. Matriks spesifik yang dimaksud adalah MEB atau MEBT.

?Definisi 2.3.3.1 Proses perubahan matriks lengkap [A|B] ke bentuk MEB dengan OBE disebut Eliminasi Gauss. Sedangkan proses perubahan matriks lengkap [A|B] ke bentuk MEBT melalui OBE dinamakan Eliminasi Gauss-Jordan.

?Algoritma untuk Eliminasi Gauss

1. Cari kolom paling kiri yang memuat unsur tidak nol

2. Jika unsur pertama kolom yang diperoleh dari langkah 1 sama dengan nol, tukarlah baris pertama dari matriks baris yang unsur pada kolom tersebut tidak nol.

3. Buatlah unsur-unsur di bawahnya menjadi nol dengan OBE, sehingga matriks yang didapat akan berbentuk

, dengan * pivot yang ditemukan.

4. Ulangi proses 1 sampai dengan 3 pada matriks A₁.

?Algoritma untuk Eliminasi Gauss-Jordan

1. Rubah matriks [A |B] menjadi MEB

2. Buatlah pivot menjadi 1

3. Buat unsur pada kolom yang memuat pivot menjadi nol dengan OBE.

Produk dari Algoritma Gauss dan Algoritma Gauss-Jordan adalah matriks lengkap [A|B]* dalam bentuk MEB. Kemudian, SPL yang berkaitan dengan [A|B]* akan menunjukkan keterkaitan pivot dengan variabel dari SPL. Variabel tersebut adalah variabel tidak bebas dan variabel bebas. Pengertian keduanya tersaji dalam definisi berikut.

?Definisi 2.3.3.2 Variabel tidak bebas adalah suatu variabel yang berkaitan dengan pivot, sedangkan variabel bebas adalah variabel yang tidak berkaitan dengan pivot..

Untuk melengkapi Algoritma Eliminasi Gauss dan Gauss-Jordan, berikut disajikan langkah-langkah untuk menyelesaikan SPL dengan proses OBE. Perbedaan keduanya hanya terletak pada matriks lengkap [A|B]* yang dicapai.

®Langkah-langkah menyelesaikan SPL dengan OBE

1. Tulis SPL dalam bentuk matriks

2. Tulis matriks lengkap [A|B] dari SPL (1)

3. Rubah [A|B] ke [A|B]* suatu MEB (untuk Eliminasi Gauss) atau MEBT (untuk Eliminasi Gauss-Jordan) dengan OBE

4. Tulis SPL yang berkaitan dengan [A|B]*

5. Tentukan variabel tidak bebas dan variabel bebas

6. Tentukan nilai variabel dengan substitusi mundur

7. Tulis HS

Untuk mengetahui perbedaan kedua proses eliminasi ini, dijelaskan dengan contoh berikut..

CContoh Diberikan Sistem Persamaan Linier dengan 3 persamaan dan 3 variabel, yaitu

x + 2y + 3 z = 11

2x + 3y + z = 10

4x + y + 2z = 10

¨Penyelesaian.

1. SPL dapat ditulis secara matriks A_3x3 X_3x1 = B_3x1, dengan

A = X = B = .

2. Matriks lengkap dari SPL adalah

[A|B] =

3. [A|B] = ~R₂+(-2)R₁

~R₃+(-4)R₁ ~ -1R₂

~R₃+(7)R₂ ~(1/25) R₃*.

4. Matriks terakhir merupakan matriks lengkap yang berbentuk MEB dari SPL

x + 2y + 3z = 11

y + 5z = 12

z = 2.

5. Variabel tidak bebas x, y dan z sedangkan variabel bebasnya tidak ada

6. Substitusi z=2 ke persamaan-2 didapat y + 5 . 2 = 12 sehingga y = 2. Dengan mensubstitusikan z=2 dan y= 2 ke persamaan-1 diperoleh x + 2.2 + 3.2 = 11 sehingga x = 1.

7. HS = {(1,2,2)}.

Jika menggunakan Eliminasi Gauss-Jordan maka langkah proses OBE dilanjutkan hingga terbentuk MEBT. Perhatiakan hasil proses (2),

~R₁+(-2)R₂

~R₁+(7)R₃ ~R₂+(-5)R₃ **

3. SPL yang berkaitan dengan [A|B]** yang berbentuk MEBT adalah

x = 1

y = 2

z = 2

4. Variabel tidak bebas adalah x, y dan z, sedangkan variabel bebasnya tidak ada.

5. HS = {(1,2,2)}.

®Catatan. Jika [A|B] dalam bentuk MEBT dengan tidak terdapat variabel bebas maka A=I dan B adalah selesaiannya. Artinya selesaian akan langsung terlihat dari proses 2. Anda bandingkan dengan Eliminasi Gauss.

CContoh Diberikan SPL dengan 3 persamaan dan 4 variabel

x₁ + x₂ + x₃ + x₄ = 12

x₁ + 2x₂ + 5x₄ = 7

3x₁ + 2x₂ + 4x₃ - x₄ = 31

¨Penyelesaian.

1. SPL dapat ditulis secara matriks A_3x4 X_4x1 = B_3x1, dengan

A = X = B = .

2. Matriks lengkap dari SPL adalah

[A|B] =

3. [A|B] = ~R₂+(-1)R₁

~R₃+(-3)R₁ ~R₃ +1R₂ *

4. Matriks terakhir merupakan matriks lengkap yang berbentuk MEB dari SPL adalah

x₁ + x₂ + x₃ + x₄ = 12

x₂ - x₃ + 4x₄ = 5

0 = 0

5. Variabel tidak bebasnya adalah x₁ dan x₂, sedang variabel bebasnya adalah x₃ dan x₄.

6. Misalkan variabel bebas x₃ = s dan x₄ = t, dengan s, t sebarang bilangan riil. Substitusikan x₃ = s dan x₄ = t ke persamaan-2 didapat x₂ – s + 4t = 5 sehingga diperoleh x₂ = s – 4t + 5. Kemudian, dengan substitusi x₃= s, x₄= t dan x₂ = s – 4t + 5 ke persamaan-1 diperoleh x₁ + (s-4t+5) + s + t = 12 sehingga diperoleh x₁ = -2s + 3t + 7.

7. HS = { (2s + 3t + 7, s – 4t + 5, s, t ) / s, t Î R }

®Jika menggunakan Eliminasi Gauss-Jordan, dilanjutkan proses (2) hingga terbentuk MEBT. Perhatikan kembali hasil proses (2)

~R₁+(-1)R₂ **

(3) SPL yang berkaitan dengan [A|B]** adalah

x₁ + 2x₃ – 3x₄ = 7

x₂ - x₃ + 4x₄ = 5

(4) Variabel tidak bebasnya adalah x₁ dan x₂, sedangkan variabel bebas adalah x₃ dan x₄.

(5) Misalkan variabel bebas x₃ = s dan x₄ = t, dengan s, t sebarang bilangan riil. Substitusikan x₃ = s dan x₄ = t ke persamaan-2 didapat x₂ – s + 4t = 5 sehingga diperoleh x₂ = s – 4t + 5. Kemudian, dengan substitusi x₃= s dan x₄= t ke persa-maan-1 diperoleh x₁ + 2s – 3t = 12 sehingga diperoleh x₁ = -2s + 3t + 7.

(6) HS = { ( 2s + 3t + 7, s – 4t + 5, s, t ) / s, t Î R }.

Secara praktis, Eliminasi Gauss-Jordan tidak memberikan keuntungan yang berarti. Karena pada MEB sudah dapat menentukan nilai variabel dengan substitusi mundur. Keuntungan dari Elimanasi Gauss-Jordan menyangkut pengembangan teori. Misalkan sebarang SPL diberikan

a₁₁ x₁ + a₁₂ x₂ + … a_1j x_j + … + a_1n x_n = b₁

a₂₁ x₁ + a₂₂ x₂ + … a_2j x_j + … + a_2n x_n = b₂

. . . . . . . .

a_m1 x₁ + a_m2 x₂ + … a_mj x_j + … + a_mn x_n = b_m

Solusi dapat langsung diketahui berdasarkan MEBT-nya. Misalkan x_j1, x_j2, …, x_jr merupakan variabel bebas maka SPL yang berkaitan dengan MEBT dari matriks lengkapnya adalah

x₁ + å c_1k x_k = d₁

x₂ + å c_2k x_k = d₂

… …

x_jr + å c_jk x_k = d_r (3)

0 = d_r+1

…

0 = d_m ,

dengan å menyatakan jumlah yang memuat variabel bebas.

SPL tersebut mempunyai selesaian jika d_r+1 = d_r+2 = … = d_m = 0. Kemudian banyaknya unsur pivot adalah r = min{m,n}, yaitu r £ m dan r £ n.

Dalam kasus r < n, terdapat variabel bebas sebanyak (n-r) buah. Dengan demikian selesaian dari SPL tersebut mempunyai (n-r) buah parameter.

Dalam hal r = n, å pada SPL (3) tidak ada dan SPL mempunyai selesai tunggal, yaitu x_j1=d₁, x_j2 = d₂, …, x_jn = d_n.

2.3.3. Matriks Balikan (invers)

Telah diketahui bahwa matriks A dapat dibalik (invertible) jika terdapat matriks B sehingga berlaku AB = I dan BA = I, dengan I matriks identitas. Dalam subbab ini akan dibicarakan metode atau langkah-langkah dalam menentukan A^-1 dengan memanfaatkan OBE dan peran A^-1 untuk menyelesaikan suatu SPL.

?Langkah-langkah menetukan A^-1 dengan OBE

®Misalkan diberikan suatu matriks A_nxn = [ a_ij]. Akan ditentukan matriks A^-1 maka dilakukan langkah-langkah berikut :

1. Tulis [ A | I ]

2. Rubah [ A | I ] menjadi [ I | A^-1 ] dengan OBE.

Untuk menentukan peran matriks invers dari A terhadap proses penyelesaian suatu SPL, diberikan teorema berikut.

?Teorema 2.3.3.1 Misalkan A_nxn = [ a_ij ] suatu matriks yang dapat dibalik (invertible). Maka untuk setiap B_nx1, SPL A_nxn X_nx1 = B_nx1 akan mempunyai tepat satu solusi, yaitu X = A^-1 B.

CContoh Misalkan suatu SPL dengan 3 persamaan dan 3 variabel, sebagai berikut :

x + 2y + 4z = 8

2x + 3y + 2z = 9

4x + 2y + z = 11

¨Penyelesaian.

1. SPL dapat ditulis secara matriks A_3x3 X_3x1 = B_3x1, dengan

A = X = B = .

2. [A | B] = , dengan

~R₂+(-2)R₁

~R₃+(-4)R₁ ~(-1) R₂

~R₁+(-2)R₂ ~R₃+(7)R₂

~(1/21) R₃~R₁+(7)R₃

~R₂+(-5)R₃***

¨Berdasarkan hasil [A|I] diperoleh A^-1 = .

¨Untuk , X = A^-1 B =

= 1/21 = 1/21 =

¨HS = {( 2,1,1 )}

DETERMINAN

3.1. Pendahuluan

Misalkan A = , dengan a, b, c dan d bilangan riil. Jika nilai (ad – bc) ¹ 0 maka matriks A mempunyai balikan. Artinya dengan mengetahui sebuah bilangan yang dikaitkan dengan matriks tersebut dapat diketahui sifat kesingularan matriks. Hal ini merupakan penemuan yang luar biasa. Pada bab ini akan diperluas gagasan tersebut untuk sebarang matriks berukuran nxn. Pembahasan dikhususkan pada metode menentukan nilai determinan dengan sifat-sifat OBE dan metode Minor dan Kofaktor.

Definisi 3.1.1. Fungsi Determinan adalah suatu fungsi yang meng-asosiasikan sebuah matriks dengan sebuah bilangan riil.

Misalkan A = maka determinan dari A adalah (ad-bc). Notasi : det(A) = (ad-bc).

Berdasarkan hasil ini, akan dibicarakan beberapa sifat determinan yang dikaitkan dengan OBE. Akan dikaji operasi dalam OBE yang tidak merubah nilai determinan suatu matriks kuadrat.

?Teorema 3.1.2. Misalkan A = , dengan det(A) = ad - bc dan k suatu bilangan riil, maka berlaku :

i. Jika B_2x2 dan A ~ k R_i B_2x2 maka det(B) = k det(A)

ii. Jika B_2x2 dan A ~ R₁«R₂ B_2x2 maka det(B) = - det(A)

iii. Jika B_2x2 dan A ~ R₂+ kR_i B_2x2 maka det(B) = det(A)

iv. Jika B_2x2 dan B_2x2 = A’ maka det(B) = det(A)

®Bukti : Akan dibuktikan (iii). Karena A ~R₂+ kR_i B_2x2 maka B = sehingga det(B) = a(d+kb) – b(c+ka) = (ad –bc )+ (kab – kab) = ad – bc = det(A).

Berdasarkan Teorema 3.1.2, memberikan ilustrasi untuk memperluas untuk sebarang matriks kuadrat dan telah terbukti bahwa hal tersebut adalah benar. Sebagaimana tersaji dalam Teorema 3.1.3 berikut.

?Teorema 3.1.2. Misalkan A _nxn = [ a_ij ] dan k suatu bilangan riil

i. Jika B_nxn dan A ®k R_i B_nxn maka det(B) = k det(A)

ii. Jika B_nxn dan A ®R_i«R_j B_nxn maka det(B) = - det(A)

iii. Jika B_nxn dan A ®R_j+ kR_i B_nxn maka det(B) = det(A)

iv. Jika B_nxn dan B_nxn = A’ maka det(B) = det(A)

v. Jika I_nxn maka det(I) = 1

vi. Jika A_nxn, B_nxn dan C_nxn adalah tiga matriks yang hanya berbeda pada baris-i. Unsur-unsur Baris-i matriks A merupakan jumlahan dari unsur-unsur pada baris-idari matriks B dan C. Maka det(A) = det(B) + det(C).

3.2

Menentukan Nilai Determinan

3.2.1. Menggunakan OBE

Untuk menentukan nilai determinan dengan menggunakan OBE, dilakukan melalui matriks segitiga atas. Hal itu karena nilai determinan matriks segitiga atas sudah diketahui, sebagaimana Teorema berikut.

?Teorema 3.2.1 Misal A_nxn = [ a_ij ] suatu matriks segitiga atas. Maka det(A) adalah hasilkali unsur pada diagonal utama, yaitu det(A) = P a_ii

®Langkah-langkah menentukan determinan matriks dengan OBE

1. Tulis matriks kuadrat A

2. Rubah matriks A ke A* suatu matriks segitiga atas

3. Tentukan det(A*) = P a_ii

4. Tulis det(A) = det(A*)

CContoh

Misalkan A = maka det(A) dapat dihitung dengan OBE, yaitu

¨ A = ~R₂+(-2)R₁

~R₃+(-3)R₁~R₃+(7/3)R₂=B

¨Karena B suatu matriks segitiga atas maka det(B) = 1 . –3 . –14/3 = 14. Karena B diperoleh dari A dengan menggunakan OBE ke-3 maka det(A) = det(B) = 14.

3.2.1

Menggunakan Minor dan Kofaktor

Untuk membicarakan Minor dan Kofaktor suatu matriks kuadrat, di bawah ini diberikan ilustrasi contoh sehingga mudah difahami.

Misalkan A = . Menurut sifat determinan maka det(A) dapat ditulis sebagai det(A) = det() + det() + det().

®Sekarang perhatikan,

det() = a₁₁ det() = a₁₁ det()

Assumsikan a₂₂ ¹ 0, maka a₁₁ det() sehingga didapat

det() = a₁₁ ( 1 . a₂₂ . (a₃₃ – a₃₂/a₂₂ a₂₃) = a₁₁ ( a₂₂ a₃₃ – a₂₃ a₃₂).

atau det() = a₁₁ det ().

Dengan menggunakan cara serupa akan diperoleh

det() = - a₁₂ det() dan

det() = a₁₃ det().

Jadi, det(A) = a₁₁ det () - a₁₂ det() + a₁₃ det().

Atau dapat ditulis,

Det(A) = a₁₁ M₁₁ – a₁₂ M₁₂ + a₁₃ M₁₃ ,

dengan M_ij adalah det dari submatriks A yang berukuran 2x2 dan disebut Minor dari determinan semula.

?Definisi 3.2.3.1 Misalkan A_nxn = [ a_ij ]. Minor M_ij adalah determinan dari matriks berukuran (n-1)x(n-1) yang didapat dari A dengan menghapus baris-i dan kolom-j. Sedangkan Kofaktor A_ij = (-1)^I+j M_ij.

-Teorema 3.2.3.2. Misalkan A_nxn = [ a_ij ].

®Nilai det(A) dapat dihitung dengan cara perluasan baris –i, yaitu

det(A) = a_i1A_i1 + a_i2 A_i2 + … + a_in A_in

=(-1)^I+1 a_i1M_i1 + (-1)^I+2 a_i2 M_i2 + … +(-1)^I+n a_in M_in

®Nilai det(A) dapat dihitung dengan cara perluasan kolom-j, yaitu

det(A) = a_1jA_1j + a_2j A_2j + … + a_nj A_nj

=(-1)^j+1 a_1jM_1j + (-1)^j+2 a_2j M_2j + … +(-1)^j+n a_nj M_nj

-Contoh. Misalkan A =

¨Maka det(A) dengan cara perluasan baris-1 adalah

Det(A) = a₁₁A₁₁ + a₁₂ A₁₂ + a₁₃ A₁₃

= (-1)¹⁺¹ a₁₁M₁₁ + (-1)¹⁺² a₁₂ M₁₂ + (-1)¹⁺³ a₁₃M₁₃

= 1 - 3 + 5

= 1 (3-12) – 3(2-18) + 5(4-9) =-9 + 48 –25 = 14

¨ Maka det(A) dengan cara perluasan kolom-1 adalah

Det(A) = a₁₁A₁₁ + a₂₁ A₂₁ + a₃₁ A₃₁

= (-1)¹⁺¹ a₁₁M₁₁ + (-1)²⁺¹ a₂₁ M₂₁ + (-1)³⁺¹ a₃₁M₃₁

= 1 - 2 + 3

= 1 (3-12) – 2(3-10) + 3(18-15) = -9 + 14 + 9 = 14

3.2.2

Menyelesaiakan SPL dg Determinan

Sistem Persamaan Linier (SPL) dapat diselesaikan dengan menggunakan determinan melalui Rumus Cramer dan Matrikss Invers. Sebagaimana tertuang dalam Teorema berikut.

?Teorema 3.2.3.1 (Rumus Cramer). Misalkan SPL dengan n persamaan dan n variabel dapat ditulis secara matrikss A_nxn X_nx1 = B_nx1 dan det(A) ¹ 0. Maka nilai dari variabel x_i dapat dihitung dengan

x_i= , i =1,2,…, n

A_i adalah matriks yang diperoleh dari A dengan mengganti kolom-i dengan matriks kolom B.

CContoh Misakan diberikan SPL dengan 3 persamaan dan 3 variabel,

2x₁ + 3x₂ + x₃ = 13

-4x₁ + 5x₂ + 2 x₃ = 0

3x₁ - 2x₂ + 5x₃ = 10.

¨Penyelesaian. Akan diselesaikan dengan aturan Cramer,.

Det(A) =det( ) = 129

Det(A₁) = det( ) = 387

Det(A₁) = det() = 258

Det(A₁) = det() = 129

Sehingga x₁ = det(A₁)/det(A) = 387/129 = 3,

x₂ = det(A₂)/det(A) = 258/129 = 2 dan

x₃ = det(A₃)/det(A) = 129/129 = 1.

¨HS = {(3,2,1)}

?Teorema 3.2.3.2 Misalkan A_nxn= [ a_ij ] yang mempunyai balikan. Maka balikan dari matriks A adalah A^-1_nxn = = ,

dengan A_ijmerupakan kofaktor dari matriks A.

CContoh Misakan diberikan SPL dengan 3 persamaan dan 3 variabel,

x₁ + 2x₂ + x₃ = 0

3x₁ + 8x₂ + 7x₃ = 8

2x₁ + 7x₂ + 9x₃ = 15.

®Penyelesaian

®Berdasarkan SPL di atas diperoleh

det(A) = det() = 1(72-49) – 2(27-14) + 1(21-16) = 54

¨Kemudian dihitung kofaktor A_ij,

A₁₁ = M₁₁ = 23 A₂₁ = -M₂₁ = -11 A₃₁ = M₃₁ = 6

A₁₂ = -M₁₁ = -15 A₂₂ = M₂₂ = 7 A₃₂ = -M₃₂ = -4

A₁₃ = M₁₃ = 5 A₂₃ = -M₂₃ = - 3 A₃₃ = M₃₃ = 2

Sehingga diperoleh

Adj A = dan

A^-1 = 1/54

Akhirnya, diperoleh selesaiannya

X = A^-1 B

= 1/54 = 1/54 =.

¨HS = {(1,-2,3)}

TEORI BILANGAN

3.1. Keterbagian (divisibility)

Apabila dua bilangan a dan b dikalikan diperoleh bilangan ketiga yaitu c, maka c dikatakan terbagi oleh a dan b. Sebagaimana, operasi pengurangan merupakan kebalikan dari operasi tambah, operasi perkalian merupakan kebalikan dari operasi bagi. Dalam subbab ini akan dibicarakan keterbagian dan sifat-sifatnya.

-Definisi 3.1.1 Misalkan a dan b suatu bilangan bulat. a disebut membagi b jika terdapat suatu bilangan bulat k sehingga berlaku b = ka.

Notasi a|b

Jika a membagi b maka a disebut faktor b atau a pembagi b atau b kelipatan a. Beberapa sifat dari keterbagian tertuang dalam teorema berikut.

-Teorema 3.1.2

i. Jika d|a dan d|b maka d|(a+b)

ii. Jika d|a dan d|b maka d|(a-b)

iii. Jika d|a maka untuk sebarang bilangan bulat c berlaku d|ca

ïBukti : Akan dibuktikan (iii). Karena d|a maka terdapat bilangan bulat m sehingga a = md. Kemudian, untuk sebarang bilangan bulat c maka berlaku ca = cmd atau ca = (cm) d. Jadi, terdapat bilangan bulat cm sehingga ca = (cm) d atau d|ca.

Teorema (i) dan (iii) berakibat , jika d|a dan d|b maka untuk sebarang bilangan x dan y berlaku d|(xa+yb).

uContoh Karena 3|9 dan 3|15 maka 3|(5.9+6.15) atau 3|135.

-Teorema 3.1.3 (Algoritma Pembagian) Misalkan a dan b suatu bilangan bulat dengan b ¹ 0. Maka terdapat secara tungga bilangan bulat q dan r (sisa) sehingga berlaku a = qb + r, dengan 0 £ r < b.

ïBukti dapat dilihat pada [2] halaman 8-9.

3.2. Faktor Persekutuan Terbesar (FPB)

-Definisi 3.2.1 Suatu bilangan bulat d dikatakan sebagai faktor persekutuan (FP) dari a dan b jika dan hanya jika d|a dan d|b.

uContoh 5 adalah factor persekutuan dari 10 dan 25 karena 5|10 dan 5|25.

-Definisi 3.2.2 Suatu bilangan bulat d dikatakan sebagai faktor persekutuan terbesar (FPT) dari a dan b jika dan hanya jika d merupakan factor persekutuan a dan b serta setiap c factor persekutan a dan b berlaku c £ d. Notasi (a,b) = d.

uContoh ( 8,20 ) = 4 , sebab 4 merupakan faktor persekutuan dan setiap c faktor persekutuan dari 8 dan 20 berlaku c £ 4. Hal ini benar karena himpunan faktor persekutuan bulat positip dari 8 dan 20 adalah {1,2,4}.

3.3 Kongruensi

Salah satu konsep yang banyak digunakan dalam teori bilangan adalah kongruensi bilangan bulat. Dengan kongruensi dapat dipelajari konsep keterbagian dan sifat-sifatnya. Teorema berikut akan menyajikan 3 ekivalensi dari kongruensi bilangan bulat.

-Teorema 3.3.1 Statemen berikut adalah ekivalen :

i. Misalkan m suatu bilangan bulat positip, a kongruen dengan b modulo m, ditulis a º b mod m jika hanya jika m|(a-b)

ii. a º b mod m jikan dan hanya jika dan hanya jika a dan b mempunyai sisa yang sama, apabila masing-masing dibagi oleh m

iii. iii. a º b mod m jika dan hanya jika a = b + km, untuk suatu bilangan bulat k.

ïBukti : Akan dibuktikan (ii ®i) Karena a dan b mempunyai sisa yang sama atas pembagian m maka menurut algoritma pembagian diperoleh a = qm + r dan b = sm + r dengan 0 £ r < m. Dengan mengurangkan didapat (a-b) = (s-q)m atau m|(a-b).

(i®iii) Karena a º b mod m maka menurut (i) didapat m|(a-b). Artinya terdapat bilangan bulat k sehingga berlaku a-b = km. Dengan kata lain berlaku a = b + km, untuk suatu bilangan bulat k.

(iii ®ii) Misalkan a º b mod m. Maka menurut (iii) berlaku a = b + km, untuk suatu bilangan bulat k. Berdasarkan teorema pebagian bulat , terdapat dengan tunggal bilangan bulat q dan r sehingga berlaku a = qm + r, dengan 0 £ r < m. Karena b = a – km maka b = (qm + r) – km = (q-k)m + r.

uContoh

i. 20 º 2 mod 3 maka 3|(20-2) =18

ii. 20 º 2 mod 3 maka 20 = 2 + 6 . 3

iii. 20 º 2 mod 3 maka 20 º2 º 5 mod 3 sehingga 20 dan 5 mempunyai sisa yang sama yaitu 2 jika dibagi 3.

Berdasarkan algoritma pembagian, jika a dan m bilangan bulat dan m > 0 maka a dapat dinyatakan sebagai a = qm + r, untuk suatu bilangan bulat tunggal q dan r, dengan 0 £ r < m. Hal ini berarti a º r mod m. Karena 0 £ r < m maka kemungkinannya adalah 0, 1, …, (m-1). Akibatnya setiap bilangan bulat kongruen modulo m dengan tepat satu di antara 0, 1, …, (m-1). Sebagaimana tertulis dalam teorema berikut.

-Teorema 3.3.2 Setiap bilangan bulat kongruen modulo m dengan tepat satu diantara 0, 1, …, (m-1)

uContoh 15 º 3 mod 4, 57 º 1 mod 4, 156 º 0 mod 4, dst

Jika a º r mod m denngan 0 £ r < m maka r disebut residu terkecil dari a modulo m.

Kekongruenan adalah suatu relasi antara bilangan-bilangan bulat. Ternyata dapat ditunjukkan bahwa relasi tersebut merupakan relasi ekuivalensi.

-Teorema 3.3.4 Jika m, a, b dan c adalah bilangan-bilangan bulat dan m > 0, maka

i. a º a mod m [sifat refleksif ]

ii. Jika a º b mod m maka b º a mod m [ sifat simetrik ]

iii. Jika a º b mod m dan b º c mod m maka a º c mod m [ sifat transitif ]

ïBukti. Akan dibuktikan (iii) Karena a º b mod m dan b º c mod m maka terdapat bilangan bulat k dan t sehingga berlaku a = b + km dan b = c + tm. Akibatnya, diperoleh a = (c + tm) + km = c + (k+ltm atau a º c mod m.

-Teorema 3.3.5 Jika a º b mod m dan c º d mod m maka a ± c º b ± d mod m

Teorema ini dapat diperluas, yaitu jika a º b mod m dan c º d mod m maka berlaku xc ± yc º xb ± yd mod m, untuk setiap bilangan bulat x dan y.

uContoh Karena 15 º 3 mod 4 dan 10 º 2 mod 4 maka (15 ± 10) º (3 ± 2) mod 4

-Teorema 3.3.6 Jika ac º bc mod m dan (m,c) = 1 maka a º b mod m

ïBukti : Karena ac º bc mod m maka m| (ac-bc) atau m| c(a-b). Karena diketahui (m,c) = 1 maka m|(a-b) yaitu a º b mod m.

-Teorema 3.3.7 Jika ac º bc mod m dan (m,c) = d maka a º b mod (m/d).

ïBukti : Karena ac º bc mod m maka m|ac –bc sehingga m|c (a-b). Karena (c,m) = d maka m/d dan c/d merupakan bilangan bulat. dan (c/d, c/d) = 1. Akibatnya m/d | c/d (a-b), dengan (c/d, m/d) =1 maka m/d|(a-b) atau a º b mod (m/d).

KRiPTOGRAFi

& MATLAB

4.1. Encoding dan Decoding

-Definisi 4.1.1 Misalkan A adalah himpunan huruf dalam abjad (alphabet). Fungsi F : A ® A disebut encoding (penyandian) jika f suatu fungsi 1-1. Sedangkan decoding (pengembalian penyandian) adalah fungsi invers dari encoding.

Suatu encoding mengaitkan suatu huruf dalam abjad ke huruf yang lain. Suatu encoding haruslah merupakan fungsi 1-1, sebab jika f(a₁) = f(a₂) = b maka tidak diketahui decoding dari b, apakah a₁ atau a₂.

Encoding f dapat diperluas untuk sebarang barisan huruf (kata), yaitu

f ( a₁ a₂ … a_n ) = f (a₁) f(a₂) …f(a_n).

Artinya untuk melakukan encoding suatu kata maka dikerjakan dengan encoding huruf demi huruf.

uContoh : Misalkan diketahui suatu encoding yang didefinisikan sebagai berikut

A B C … Z

¯ ¯ ¯ ¯

H I J C

ïMaka encoding dari pesan I LOVE ALE adalah P SVCL HSL dan decoding dari pesan P FBLL HSL adalah I MISS ALE

Salah satu contoh encoding sederhana yang menggunakan modulo aritmetik adalah Caesar Cypher. Encoding ini dinamakan Caesar cypher sebab Julius Caesar yang menggunakannya. Dalam Caesar cypher, Yulius menentukan suatu bilangan bulat tertentu, yaitu 3, untuk melakukan encoding. Encoding dalam Caesar Cypher adalah

A B C … Z

¯ ¯ ¯ ¯

D E F C

Secara matematik, Caesar cypher dapat dijelaskan sebagai berikut : asosiasikan huruf-huruf dalam abjad A, B, C, …, Z dengan bilangan-bilangan bulat 1, 2, 3, …, 25, 0. Ingat 26 º 0 mod 26.

A B C … Y Z

¯ ¯ ¯ ¯ ¯

1 2 3 25 0

Misalkan bilangan bulat tertentu dipilih b maka huruf y yang berkaitan dengan x, didefinisikan sebagai f(x) = y º (x + b) mod 26. Sisi kanan dari kongruensi dimaksudkan sebagai residu terkecil dari f(x) modulo 26. Berdasarkan definisi ini maka Caesar cypher dapat ditulis sebagai f(x) = y º (x+3) mod 26.

Untuk menentukan bayangan huruf G, dengan G adalah huruf ke 7 dalam abjad maka f(7) = y º (7+3) mod 26 = 10, yaitu huruf J sehingga G dikaitkan dengan J.

Untuk menentukan decoding dalam Caesar cypher, dilakukan dengan menentukan x dalam modulo26. Perhatikan, y º (x+3) mod 26 Û x º (y-3) mod 26. Misal decoding dari huruf H, dengan huruf H adalah huruf ke 8 dalam abjad maka didapat x º (8-3) mod 26 = 5, yaitu huruf E.

Caesar cypher dapat diperluas dengan menggunakan kongruensi f(x) = y º (ax+b) mod 26. Untuk menentukan decodingnya berarti kita mencari selesaian konguensi f(x) = y º (ax+b) mod 26 untuk x dalam y. Perhatikan,

y º (ax+b) mod 26 Û (ax+b) º y mod 26

Û ax º (y-b) mod 26,

sehingga untuk menentukan selesaian kongruensi ini kedua sisi harus dibagi dengan a. Hal ini dapat dilakukan jika fpb(a,26)=1. Berdasarkan kenyataan ini, didefinisikan suatu encoding modulo, sebagaimana tertuang dalam definisi berikut.

-Definisi 4.1.2 Misalkan b suatu bilangan bulat tertentu. Suatu encoding f disebut encoding modulo jika f(x) = y º (ax+b) mod 26, dengan fpb (a,26) = 1.

uContoh. Misalkan encoding modulo didefinisikan dengan f(x) = y º (3x+2) mod 26. Tentukan encoding dari pesan DARTH VADER dan decoding dari pesan GKEDLQJ L ZEDE.

ïPenyelesaian. Berdasarkan definisi encoding modulo didapat bayangan huruf D dan huruf D huruf ke 4 adalah y º (3 .4 + 2) mod 26 = 15 yaitu huruf N. Dengan cara yang sama, encoding dari DARTH VADER adalah NEDJZ PENQD.

Akan dicari decoding dari pesan GKEDLQJ L ZEDE. Karena y º (3x+2) mod 26 maka 3x º (y-2) mod 26. Kalikan kedua sisi dengan 9 sehingga didapat

27x º 9(y-2) mod 26.

Tetapi dari sisi lain diketahui bahwa

27x º x mod 26

sehingga didapat

x º 9(y-2) mod 26.

Berdasarkan kongruensi ini, decoding huruf G, huruf ke 7 dalam abjad adalah x º 9(7-2) mod 26 º 45 mod 26 =19 mod 26 yaitu huruf S. Dengan cara yang sama, diperoleh decoding dari pesan GKEDLQJ L ZEDE adalah SCARLET OHARA.

Sering dalam pengiriman pesan, fungsi encodingnya tidak didefinisikan sehingga penerima pesan (receiver) harus membongkar dengan berbagai kemungkinan. Salahsatu cara yang digunakan adalah dengan mengurutkan berdasarkan banyaknya huruf yang muncul dalam suatu bahasa. Misal bahasa Inggris, urutan huruf yang sering muncul adalah huruf E, kemudian T , N, dan seterusnya. Maka huruf yang terbanyak muncul dalam pesan tersebut dikaitkan dengan huruf E, huruf berikutnya dengan T, dan seterusnya.

uContoh. Misalkan F suatu encoding modulo, tentukan decoding dari pesan berikut (dalam bahasa Inggris) CFFYB RFFYB OZCCOF CRFFCB QZSA.

uPenyelesaian. Berdasarkan pesan yang dikirim, urutan huruf yang sering muncul adalah F kemudian C. Jika encoding modulo f(x) = y º (ax+b) mod 26 maka diprediksikan f(E) = F dan f(T) = C.

Karena E, F, T, C masing-masing adalah huruf ke 5, 6, 20 dan 3 dalam huruf abjad maka diperoleh hubungan

5a + b º 6 mod 26

20a + b º 3 mod 26

Dengan mengurangkan kedua persamaan kongruensi di atas, didapat

15a º -3 mod 26 º 49 mod 26 º 75 mod 26.

Dengan membagi kedua ruas dengan 15, diperoleh

a º 5 mod 26.

Substitusikan a=5 ke persamaan 5a + b º 6 mod 27, didapat

5 5 + b º 6 mod 26 º b º -19 mod 26 º 7 mod 26.

Kesimpulan, fungsi encoding modulo yang digunakan adalah f(x) = y º (5x+7) mod 26. Berdasarkan definisi ini didapat fungsi decoding adalah x º 21(y-7) mod 26 (buktikan). Akibatnya, decoding dari huruf C, huruf ke 3 dalam abjad adalah

x º 21(3-7) mod 26 º -84 mod 26 º 20 mod 26, yaitu huruf T.

Dengan cara yang sama, decoding dari pesan CFFYB RFFYB OZCCOF CRFFCB QZSA adalah TEENY WEENY LITTLE TWEETY BIRD.

4.2. Kriptografi dengan menggunakan matriks

Dalam persandian pada 4.1, huruf yang sama pada pesan ternyata mempunyai image huruf yang sama juga. Hal ini mempunyai tingkat resiko yang tinggi karena mudah ditebak. Tujuan membuat encoding adalah aman dari para pembongkar sandi sehingga hanya penerima saja yang mengetahui isinya.

Pesan dikemas dan ditulis dalam bentuk barisan bilangan atau huruf tidak beraturan. Pesan sandi yang dikirim merupakan hasil pengolahan dan pemrosesan dengan satu atau lebih operasi matriks. Tingkat keamanan suatu pesan tergantung pada kompleksitas pemrosesan operasi matriks yang digunakan.

Pada proses pengiriman pesan, sender(pengirim) menyertakan juga perangkat yang digunakan untuk mengolah/merubah pesan. Perangkat yang dimaksud adalah aturan konversi dan matriks pemrosesnya (matriks kunci). Berdasarkan ketiga perangkat inilah receiver (penerima) dapat membongkar /membaca makna pesan yang dikirim.

Pada Seksi ini akan dibahas proses pengiriman dan pembacaan suatu pesan sandi yang sangat sederhana. Diharapkan dapat digunakan sebagai ilustrasi untuk mengembangkan peran invers suatu matrikss dalam dunia persandian(kriptografi).

4.2.1 Mengirim Pesan

uLangkah-langkah mengirim pesan

1. Tulis pesan Anda [ dalam deretan huruf yang bermakna]

2. Tentukan “aturan konversi” yang Anda gunakan

Misal, A, B, C, …, Z, _, , , ., ?, !,

× × × × × × × × ×

1, 2, 3,…, 26, 27, 28, 29, 30, 31

4. Tulis pesan (1) dalam bentuk konversi

5. Tulis pesan (3) dalam bentuk matriks, misal M

6. Tentukan matriks kunci A, dengan kriteria sbb:

· Semua unsur dari matriks A dan A^-1 adalah bulat

· Matriks A dan M dapat dikalikan(multiplicable)

7. Tentukan matriks P, dengan P = AM

8. Tulis matriks P dalam deretan bilangan. [ P inilah pesan yang dikirim]

uDalam proses pengiriman pesan tersebut, seorang penerima (receiver) akan menerima beberapa perangkat. Perangkat yang disertakan digunakan untuk membongkar /membaca pesan yang dikirimkan.

Perangkat tersebut adalah :

· Pesan dalam deretan bilangan [pesan (7)]

· Aturan konversi [pesan (2)]

· Matriks kunci [pesan (5)].

uContoh. Seseorang mengirim pesan kepada sahabatnya. Pesan tersebut adalah “BE SELF FOREVER.”, sehingga dia tidak keluar dari jati dirinya. Agar tidak menyinggung perasaan orang yang membaca dan lebih menarik maka pesannya dikirim dalam sandi.

uLangkah-langkahnya, adalah sbb:

1. Pesan : BE SELF FOREVER.

2. Aturan konversi :

A, B, C, …, Z, _, , , ., ?, !,

× × × × × × × × ×

1, 2, 3,…, 26, 27, 28, 29, 30, 31

3. Pesan (1) menjadi : 2 5 27 19 5 12 6 27 6 15 18 5 22 5 18 29

4. Tulis pesan (3) dalam matriks,

M _2x8 =

uPerhatian. Ukuran matriks M bergantung pada ukuran matriks kunci A. Ukuran M adalah (2x…), angka 2 mengacu pada ukuran A, yaitu 2x2.

5. Misalkan diberikan matriks kunci A, dengan A = .

uIngat, bahwa semua unsur dari A dan unsur A^-1 adalah bulat. Hal itu dapat dilakukan (salah satunya) dengan membuat det(A)=1.

6. Misalkan P, dengan P = AM maka diperoleh

P =

7. Pesan akhir yang didapat adalah

22 55 108 53 76 39 66 141 14 35 63 29 49 22 42 85

uPerangkat yang dikirim terdiri 3 hal yaitu :

âpesan : 22 55 108 53 76 39 66 141 14 35 63 29 49 22 42 85

âaturan konversi :

A, B, C, …, Z, _, , , ., ?, !,

× × × × × × × × ×

1, 2, 3,…, 26, 27, 28, 29, 30, 31

âmatriks kunci A,

A =

4.2.2 Membaca isi pesan

Seseorang mengirim pesan mengharapkan pesan tersebut dapat dibaca sehingga isi pesan segera diketahui oleh penerima. Maka penulisan alamat, bahasa dan teknik penulisan sangatlah penting untuk diketahui kedua pihak. Khusus teknik penulisan pesan, disamping faham cara membacanya, juga diberi fasilitas untuk membongkarnya. Dengan demikian penerima(receiver) cukup mudah untuk melakukan pembacaan pesan yang diterimanya.

uLangkah-langkah membaca pesan

1. Tulis pesan yang diterima dalam bentuk matriks, misal P. Ukuran P multiplicable dengan matriks A^-1 artinya matriks A^-1 dan matriks P dapat dikalikan. [ ingat : ukuran matriks A^-1 = ukuran matriks A]

2. Tentukan A^-1 (dengan menggunakan metode yang telah diketahui)

3. Tentukan M = A^-1 P. [ karena A^-1 P = A^-1 (AM) = (A^-1.A) M = I. M = M]

4. Tulis M dalam bentuk deretan bilangan

5. Tulis konversi dari (4) dengan aturan konversi

6. Tulis pesan yang dimaksud.

uContoh. Anda perhatikan contoh pada 4.2. Kita akan membaca pesan yang dikirim dari contoh tersebut. Perangkat yang dikirim adalah

âpesan : 22 55 108 53 76 39 66 141 14 35 63 29 49 22 42 85

âaturan konversi :

A, B, C, …, Z, _, , , ., ?, !,

× × × × × × × × ×

1, 2, 3,…, 26, 27, 28, 29, 30, 31

âmatriks kunci A,

A =

uKita akan membaca pesan yang dikirim berdasarkan petunjuk langkah-langkah di atas.

1. Tulis pesan dalam matriks P, yaitu

2. Mencari A^-1.

Karena A = maka didapat A^-1=

3. Mencari

M = A^-1 P =

4. Menulis pesan P dalam deretan bilangan, yaitu :

2 5 27 19 5 12 6 27 6 15 18 5 22 18 29

5. Tulis pesan dalam bentuk konversi yang dikirim, yaitu :

B E _ S E L F _ F O R E V E R .

6. Pesan yang dikirim adalah : BE SELF FOREVER.

uContoh. Seorang teman mengirim pesan/nasehat kepada Anda dalam bentuk sandi. Dia sangat mengharapkan Anda dapat membaca dan merealisasikan dalam kehidupan sehari-hari. Disamping mengirim pesan dia juga mengikutkan perangkat (fasilitas) untuk membaca-nya. Pesan dan perangkat yang dikirim adalah sebagai berikut :

1. Pesan :

32 31 45 18 41 32 32 79 44 47 23 25 27 12 27

2. Aturan Konversi :

A, B, C, …, Z, _,

× × × × ×

1, 2, 3,…, 26, 0

dan

f(X*)=(X*+5) mod 27, dengan X* huruf alphabet.

( contoh : f(A)=(A+5) mod 27 ï f(1)=(1+5) mod 27 = 6,

f(D)=(D+5) mod 27 ï f(4)=(4+5) mod 27 = 9,

f(X)=(X+5) mod 27 ï f(24)=(24+5) mod 27 = 2, dst)

3. Matriks kunci A, dengan

A =

¨Penyelesaian : Langkah-langkah yang dilakukan untuk membaca pesan terse-but, adalah :

1. Tulis pesan dalam matriks P dengan mengingat ukuran A. Karena A(3x3) maka ukuran P adalah 3x5, yaitu data pesan dibagi tiga baris. Matriks P adalah

P =

2. Menentukan matriks A^-1 dengan menggunakan metode matriks Adjoint, yaitu A^-1 = Adj A / |A|.

Karena A = maka dengan menggunakan perluasan baris –1, didapat

Det(A) = a₁₁ M₁₁ – a₁₂ M₁₂ + a₁₃ M₁₃

= 2 (1-0) – 0 (3-0) + 1 (0-1)

= 2 – 0 + 1(-1) = 1

Adj A = , (mohon diperhatikan unsur-unsurnya)

Diperoleh

A₁₁ = + M₁₁= (1-0) = 1

A₂₁ = - M₂₁= - (0-0) = 0,

A₃₁ = + M₃₁= (0-1) = -1

A₁₂ = - M₁₂= -(3-0) = -3

A₂₂ = + M₂₂= (2-1) = 1,

A₃₂ = - M₃₂= -(0-3) = 3

A₁₃ = + M₁₃= (0-1) = -1

A₂₃ = - M₂₃= -(0-0) = 0

A₃₃ = + M₃₃= (2-0) = 2.

Maka didapat

Adj A = sehingga menurut rumus diperoleh

A^-1 = Adj A / det(A) = / 1 =

3. Menentukan matriks M, yaitu :

M = A^-1 * P = =

4. Pesan M pada (4), disusun membentuk deretan bilangan, yaitu :

9 6 18 6 14 5 14 25 26 5 14 19 9 6 13

5. Pesan pada (4), dikonversi dengan menggunakan Aturan Konversi, didapat :

9 = 9 mod 27 = (4+5)mod 27 shg 9 ï 4 yaitu D

6 = 6 mod 27 = (1+5)mod 27 shg 6 ï 1 yaitu A

18 = 18 mod 27 = (13+5) mod 27 shg 18 ï13 yaitu M,

6 = 6 mod 27 = (1+5)mod 27 shg 6 ï 1 yaitu A

14 = 14 mod 27 = (9+5)mod 27 shg 14 ï 9 yaitu I,

dan seterusnya

Sehingga didapat pesan

D A M A I _ I T U _ I N D A H

6. Pesan yang dimaksud adalah : DAMAI ITU INDAH

4.3 Belajar ALE dengan Matlab

Dalam mempelajari ALE titik tekannya pada pemahaman konsep. Untuk memahami konsep dibutuhkan keseriusan dan kesabaran sehingga memakan waktu. Sebagai contoh, pemahaman tentang Selesaian SPL maka diperlukan waktu untuk berlatih mengoperasikan OBE pada matriks lengkapnya. Pada SPL yang berukuran besar, kegiatan secara manual dalam pengoperasi dengan OBE tidak bisa dilakukan lagi. Oleh sebab itu diperlukan sarana untuk membantu kebutuhan ini. Pada subbab ini disajikan salah satu software yang dapat digunakan sebagai alternatif penyelesaian. Software yang dimaksud adalah MatLab

Dalam pembahasannya dengan MatLab, disajikan penggunaan fungsi dalam MatLab secara singkat dan langsung. Khususnya, fungsi-fungsi yang berkaitan dengan proses mencari selesaian suatu SPL. Proses penyajian mengikuti langkah-langkah dalam penyelesaian SPL yang telah dikaji pada bab 2.

uContoh 1 . Diberikan SPL dengan 3 persamaan dan 3 variabel, sbb :

x + 2y + 3 z = 11

2x + 3y + z = 10

4x + y + 2z = 10

¨Penyelesaian.

1. SPL dapat ditulis secara matriks A_3x3 X_3x1 = B_3x1, dengan

A = X = B = .

uDengan MatLab

>>A= [1,2,3;2,3,1;4,1,2] (tekan enter)

A =

>>X= [x;y;z] ¿

X =

>>B= [11;10;10] ¿

B =

2. Matriks lengkap dari SPL adalah

[A|B] =

uDengan MatLab

>>C = [A B] ¿

C = [ C adalah matriks lengkap dari SPL ]

3. [A|B] = ~R₂+(-2)R₁

~R₃+(-4)R₁ ~ -1R₂

~R₃+(7)R₂ ~(1/25) R₃*.

uDengan Maple

>>D:=Gausselim(C) ;

D:=

4. Matriks terakhir merupakan matriks lengkap yang berbentuk MEB dari SPL

x + 2y + 3z = 11

y + 5z = 12

z = 2.

5. Variabel tidak bebas x, y dan z sedangkan variabel bebasnya tidak ada

6. Substitusi z=2 ke persamaan-2 didapat y + 5 . 2 = 12 sehingga y = 2. Dengan mensubstitusikan z=2 dan y= 2 ke persamaan-1 diperoleh x + 2.2 + 3.2 = 11 sehingga x = 1.

uDengan Maple

>X:=backsub(D);

X:= [ 1, 2, 2 ]

6. HS = {(1,2,2)}.

Jika menggunakan Eliminasi Gauss-Jordan maka langkah proses OBE dilanjutkan hingga terbentuk MEBT. Perhatikan hasil proses (2),

~R₁+(-2)R₂

~R₁+(7)R₃ ~R₂+(-5)R₃ **

uDengan Maple

>>E:=GaussJord(D);

E :=

3. SPL yang berkaitan dengan [A|B]** yang berbentuk MEBT adalah

x = 1

y = 2

z = 2

7. Variabel tidak bebas adalah x, y dan z, sedangkan variabel bebasnya tidak ada.

uDengan Maple

>X:=backsub(D);

X:= [ 1, 2, 2 ]

6. HS = {(1,2,2)}.

Contoh-contoh berikut akan dikerjakan dengan menggunakan Maple. SPL yang diberikan berukuran besar dan lama jika dikerjakan dengan manual.

uContoh2 Diberikan SPL dengan 6 persamaan dan 3 variabel, sebagai berikut :

x₁ + 2x₂ + 3x₃ + 2x₄ + 3x₅ + x₆ = 15

2x₁ + 3x₂ + 5x₃ + x₄ + 2x₅ + 3x₆ = 10

3x₁ + 4x₂ + 2x₃ + x₄ + x₅ + x₆ = 8

4x₁ + x₂ + x₃ + 2x₄ + 3x₅ + 2x₆ = 17

ïPenyelesaian :

>with(linalg):

>A:=matrix(4,6,[1,2,3,2,3,1,2,3,5,1,2,3,3,4,2,1,1,1,4,1,1,2,3,2]);

A:=

>X:=matrix(6,1,[x₁,x₂,x₃,x₄,x₅,x₆]);

X:=

>B:=matrix(4,1,[15,10,8,17]);

B:=

>C:=concat(A,B); [ C adalah matriks lengkap]

uDetailnya lihat lampiran halaman 1-2.

uContoh 3 Tentukan HS dari SPL berikut

2x₁ + 3x₂ + x₃ + 4x₄ + 3x₅ + x₆ = 30

3x₁ + x₂ +2x₃ + 2x₄ + 4x₅ +3x₆ = 32

4x₁ + 5x₂ +2x₃ + x₄ + x₅ +2x₆ = 23

5x₁ + x₂ +3x₃ + 2x₄ + x₅ + x₆ = 23

6x₁ + x₂ + x₃ + 3x₄ + 4x₅ + x₆ = 32

8x₁ + 6x₂ +3x₃ + 4x₄ + 3x₅ +2x₆ = 45

Teknologi dan Informasi

Sunday, 30 October 2016

Belalajar Matematika MATRIKS , Rumus rumus

No

No comments:

Post a Comment

MY WEB