PROSIDING
ISBN : 978 – 979 – 16353 – 6 – 3
A–1 Sistem Persamaan Linear Atas Ring Ari Dwi Hartanto (Mahasiswa S2 Matematika FMIPA UGM) E-mail:
[email protected] Dian Ariesta Yuwaningsih (Mahasiswa S2 Matematika FMIPA UGM) E-mail:
[email protected] Sri Wahyuni (Dosen PS S2 Matematika Jurusan Matematika FMIPA UGM) E-mail:
[email protected] Abstrak Dalam makalah ini akan dibicarakan sistem persamaan linear atas ring komutatif dengan elemen satuan, sifat-sifat, serta kaitannya dengan sistem persamaan linear atas lapangan. Pada sistem persamaan linear atas lapangan, salah satu cara untuk menentukan solusi dari SPL AX = b adalah dengan melakukan serangkaian operasi Gaussian pada matriks yang diperluas [ A | b] . Namun, operasi Gaussian belum tentu dapat digunakan untuk mencari solusi dari sistem persamaan linear atas ring. Oleh karena itu, akan dibahas syarat perlu dan syarat cukup agar sistem persamaan linear atas ring mempunyai solusi. Selanjutnya, dari syarat perlu dan syarat cukup tersebut dapat dikonstruksikan suatu algoritma untuk menentukan solusi dari sistem persamaan linear atas ring. Sebagaimana halnya sistem persamaan linear homogen atas lapangan; sistem persamaan linear homogen AX = O atas ring juga selalu konsisten (mempunyai solusi) yakni X = 0 . Terkait dengan kekonsistenan sistem persamaan linear homogen atas ring akan dipaparkan Teorema McCoy. Pada bagian akhir akan dibicarakan penggunaan aturan Cramer dalam menentukan solusi sistem persamaan linear atas ring. Kata kunci : SPL atas ring, konsintensi SPL, aturan Cramer.
1. PENDAHULUAN Salah satu pembahasan menarik di bidang matematika, khususnya bidang aljabar, adalah sistem persamaaan linear. Sistem persamaan linear yang telah dikenal oleh khalayak umum adalah sistem linear atas lapangan F . Sistem persamaan linear (disingkat SPL) atas lapangan biasanya dinyatakan dengan
AX = B
dimana
A ∈ M mxn ( F ) , X ∈ R n , dan B ∈ R m . Apabila B ∈ R m dalam SPL AX = B merupakan vektor nol, maka SPL AX = B disebut sistem persamaan linear homogen (disingkat SPLH). Pembahasan dalam SPL dan SPLH atas lapangan diantaranya meliputi bagaimana cara mencari solusinya, syarat-syarat serta kondisi apa saja yang harus dipenuhi agar SPL dan SPLH memiliki solusi. Dalam ilmu aljabar, telah diketahui bahwa lapangan sendiri merupakan suatu ring komutatif dengan elemen satuan. Dalam keseluruhan isi makalah ini R dinotasikan sebagai ring dengan elemen satuan. Selanjutnya, bagaimana apabila dikonstruksikan suatu sistem persamaan linear
atas R . Apakah sifat-sifat dan kondisi dalam
menentukan solusi dari sistem persamaan linear atas lapangan masih dapat Makalah dipresentasikan dalam Seminar Nasional Matematika dan Pendidikan Matematika dengan tema ”M Matematika dan Pendidikan Karakter dalam Pembelajaran” pada tanggal 3 Desember 2011 di Jurusan Pendidikan Matematika FMIPA UNY
PROSIDING
ISBN : 978 – 979 – 16353 – 6 – 3
dipertahankan dalam sistem persamaan linear atas R . Jikalau ada sifat yang tidak bisa dipertahankan, sifat-sifat atau kondisi apa saja yang harus ditambahkan dalam sistem persamaan linear atas R agar sifat dari sitem persamaan linear atas lapangan tetap berlaku. Dalam makalah ini akan dibicarakan generalisasi dari sistem pesamaan linear atas lapangan ke sistem persamaan linear atas R . Syarat perlu dan syarat cukup apa saja yang dibutuhkan agar SPL dan SPLH atas R memiliki solusi. Kekonsistenan dari sistem persamaan linear homogen dipaparkan pada Teorema McCoy dalam buku McCoy(1948). Sedangkan mengenai syarat cukup dan syarat perlu agar sistem persamaan linear konsisten dipaparkan dalam buku Brown(1993). Selain itu, juga akan dibicarakan mengenai Aturan Cramer pada sistem persamaan linear atas R .
2. SISTEM PERSAMAAN LINEAR ATAS R Pembahasan pertama dalam makalah ini mengenai sistem persamaan linear homogen atas R , yang kemudian dilanjutkan pembahasan sistem persamaan linear atas R . Sama halnya dengan sistem persamaan linear homogen atas lapangan, SPLH atas R
minimal memiliki solusi trivial. Untuk mengetahui apakah SPLH atas R memiliki solusi nontrivial atau tidak, berikut diberikan suatu teorema yang menjamin SPLH atas R memiliki solusi nontrivial atau tidak.
Teorema 2.1. (N. McCoy) Diberikan A ∈ M m x n ( R ) .Sistem Persamaan Linear Homogen
AX = O mempunyai solusi nontrivial jika dan hanya jika rk ( A) < n . Bukti. ( ⇒ ) Diketahui SPLH AX = O mempunyai solusi nontrivial. Misal v ∈ R n ,
dengan v ≠ 0, merupakan solusi nontrivial dari AX = O . Akan ditunjukkan rk ( A) < n . Jika m < n , maka diperoleh rk ( A) ≤ min{m, n} = m < n. Oleh karena itu, untuk kasus
m < n telah terbukti. Selanjutnya akan dibuktikan untuk kasus m ≥ n . Misal Δ (i1 , i2 ,L in ;1, 2,L , n) adalah minor n x n dari
A . Terdapat matriks permutasi
P ∈ GL ( m, R ) sedemikian hingga PA merupakan matriks dengan n baris pertamanya
adalah baris-baris i1 , i2 ,L in dari A . Jadi, Row1 ( PA) = Rowi1 ( A), Row2 ( PA) = Rowi2 ( A),L , Rown ( PA) = Rowin ( A)
dan
Seminar Nasional Matematika dan Pendidikan Matematika Yogyakarta, 3 Desember 2011 MA ‐ 2
PROSIDING
⎡ ai11 ⎢ ⎢ ai2 1 PA = ⎢ M ⎢ ⎢ ain 1 ⎢ ⎣⎢
ISBN : 978 – 979 – 16353 – 6 – 3
ai1 2 L ai1n ⎤ ⎥ ai2 2 L ai2 n ⎥ M M ⎥. ⎥ ain 2 L ain n ⎥ ⎥ * ⎦⎥
Dibentuk
⎡ ai11 ai1 2 L ai1n ⎤ ⎢ ⎥ ⎢ ai2 1 ai2 2 L ai2 2 ⎥ D=⎢ M M M ⎥ ⎢ ⎥ ⎢⎣ ain 1 ain 2 L ain n ⎥⎦ dan diperoleh Δ = det( D) = Δ(i1 , i2 ,L in ;1, 2,L , n). Dari yang diketahui bahwa Av = O , berakibat Dv = O dan Δv = (ΔI n )v = (adj ( D)) Dv = 0 . Diperoleh Δ[v]k = 0 untuk setiap
k , 1 ≤ k ≤ n . Karena Δ = Δ (i1 , i2 ,L in ;1, 2,L , n) sebarang minor n x n dari A, dapat disimpulkan bahwa [v]k ∈ AnnR ( I n ( A)) . Oleh karena itu, AnnR ( I n ( A)) ≠ {0} dan rk ( A) < n .
( ⇐ ) Diketahui rk ( A) < n . Akan ditunjukkan AX = O mempunyai solusi nontrivial. Misalkan rk ( A) = r < n . Jika r = m , maka dengan menambahkan persamaan-persamaan
⎡ A⎤ dengan koefisien nol akan diperoleh persamaan baru ⎢ ⎥ X = O . Jika v solusi ⎣O ⎦ ⎡ A⎤ nontrivial dari Ax = O , maka jelas v juga merupakan solusi nontrivial dari ⎢ ⎥ X = O . ⎣O ⎦ ⎡ A⎤ Sebaliknya, jika v solusi nontrivial dari ⎢ ⎥ X = O , maka v juga merupakan solusi ⎣O ⎦
⎛ ⎡ A⎤ ⎞ nontrivial dari AX = O . Di lain pihak, I t ⎜ ⎢ ⎥ ⎟ = I t ( A) , untuk setiap t ∈ Z , sehingga ⎝ ⎣O ⎦ ⎠ ⎛ ⎡ A⎤ ⎞ ⎡ A⎤ rk ( A) = rk ⎜ ⎢ ⎥ ⎟ . Dengan demikian jika AX = O diganti ⎢ ⎥ X = O maka dapat ⎣O ⎦ ⎝ ⎣O ⎦ ⎠ diasumsikan r < min{m, n} . Karena rk ( A) = r , maka AnnR ( I r +1 ( A)) ≠ {0} . Misal a ∈ AnnR ( I r +1 ( A)), a ≠ 0.
Seminar Nasional Matematika dan Pendidikan Matematika Yogyakarta, 3 Desember 2011 MA ‐ 3
PROSIDING
ISBN : 978 – 979 – 16353 – 6 – 3
i. Jika r = 0 , maka a ∈ AnnR ( I1 ( A)) . Dibentuk v = ( a, a,L , a ) ∈ R n , maka Av = O T
sehingga v adalah solusi nontrivial dari AX = O . ii. Jika
1 ≤ r ≤ min{m, n} .
Karena
rk ( A) = r ,
AnnR ( I r ( A)) = {0}
maka
dan
AnnR ( I r +1 ( A)) ≠ {0} . Misal a ≠ 0 ∈ AnnR ( I r +1 ( A)) , maka a ∉ AnnR ( I r ( A)) sehingga terdapat
minor
Δ (i1 , i2 ,L , ir ; j1 , j2 ,L , jr )
dari
aΔ (i1 , i2 ,L , ir ; j1 , j2 ,L , jr ) ≠ 0 . Terdapat matriks
A
sedemikian
hingga
permutasi P ∈ GL ( m, R ) dan
⎡ ai1 j1 L ai1 jr ⎤ ⎡C *⎤ ⎢ ⎥ , dengan C = ⎢ M M ⎥. Q ∈ GL ( n, R ) sedemikian hingga PAQ = ⎢ ⎥ ⎣ * *⎦ ⎢ ai j L ai j ⎥ r r ⎦ ⎣ r1
Dari sini diperoleh det(C ) = Δ(i1 , i2 ,L , ir ; j1 , j2 ,L , jr ). Jika ( PAQ ) X = O memiliki solusi nontrivial yaitu β ∈ R n , akan ditunjukkan
AX = O memiliki solusi nontrivial, katakan v ∈ R n . Dari Av = O , berarti PAv = O . Karena Q invertibel, maka diperoleh PAv = PAIv = PAQQ −1v = O . Karena β ∈ R n solusi nontrivial dari ( PAQ ) X = O maka dapat dipilih β = Q −1v , sehingga diperoleh v = Q β . Karena Q bukan matriks nol dan β solusi nontrivial dari ( PAQ ) X = O ,
maka v = Q β ≠ O . Karena P invertibel, dari PAv = O diperoleh Av = O . Jadi, SPLH AX = O memiliki solusi nontrivial. Oleh karena I t ( PAQ) = I t ( A) untuk setiap t ∈ , maka membuktikan AX = O memiliki solusi nontrivial cukup dengan menunjukkan ( PAQ ) X = O memiliki solusi nontrivial. Hal ini dapat dilakukan dengan mengganti matriks A dengan PAQ . Tanpa mengurangi keumuman, diasumsikan Δ (i1 ,L , ir ; j1 ,L , jr ) = Δ (1,L , r ;1,L , r ) . Jika
dipilih
Δ = Δ (1,L , r ;1,L , r )
maka
diperoleh
⎡C *⎤ A=⎢ ⎥ ⎣ * *⎦
dengan
⎡ a11 L a1r ⎤ C = ⎢⎢ M M ⎥⎥ dan det(C ) = Δ , sehingga diperoleh aΔ ≠ 0 . Dibentuk ⎢⎣ ar1 L arr ⎥⎦
Seminar Nasional Matematika dan Pendidikan Matematika Yogyakarta, 3 Desember 2011 MA ‐ 4
PROSIDING
⎡ a11 L a1r ⎢ M C'= ⎢ ⎢ ar1 L arr ⎢ ⎣⎢ a( r +1)1 L a( r +1) r
ISBN : 978 – 979 – 16353 – 6 – 3
a1r +1 ⎤ M ⎥⎥ ∈ M ( r +1)( r +1) ( R) . ar ( r +1) ⎥ ⎥ a( r +1)( r +1) ⎦⎥
Dibentuk d j = Cof ( r +1) j (C ') , untuk setiap j = 1, 2,L , r + 1 . Menggunakan ekspansi r +1
Laplace, diperoleh
∑a j =1
Dipilih v = ( ad1
( r +1) j
d j = det(C ') ∈ I r +1 ( A) .
ad 2 L ad r +1
0 L 0)T ∈ R n . Karena ad r +1 = aΔ ≠ 0 , maka
v ≠ 0 . Diklaim v merupakan solusi dari AX = O . Berarti Av = O jika dan hanya r +1
jika
∑ a (ad ) = 0 j =1
ij
j
untuk setiap i = 1,L , m . Dalam hal ini, terdapat dua kasus.
Pertama, jika 1 ≤ i ≤ r maka diperoleh
j =1
i ≥ r +1
maka diperoleh
⎛ r +1
r +1
∑ a (ad ) = a ⎜ ∑ a d ij
j
⎝
j =1
ij
j
⎞ ⎟ = 0 . Kedua, jika ⎠
⎛ ⎡ a11 L a1r +1 ⎤ ⎞ ⎜⎢ ⎟ r +1 M M ⎥⎥ ⎟ ⎜ ⎢ ∈ aI r +1 ( A) = {0} . aij (ad j ) = a det ∑ ⎜ ⎢ ar1 L ar ( r +1) ⎥ ⎟ j =1 ⎜⎢ ⎟ ⎜ ⎢ ai1 L ai ( r +1) ⎥⎥ ⎟ ⎦⎠ ⎝⎣
Oleh karena itu, diperoleh Av = O . Jadi, AX = O memiliki solusi nontrivial.
Terdapat banyak teorema-teorema menarik yang merupakan akibat dari Teorema McCoy. Salah satunya akibat berikut ini. Akibat 2.2. Jika jumlah persamaan kurang dari jumlah variabel maka sistem persamaan
linear homogen memiliki solusi nontrivial.
Berikut diberikan algoritma untuk menentukan solusi nontrivial dari SPLH
AX = O atas R . Algoritma ini dikonstruksi dari Teorema McCoy. Algoritma. (Menentukan Solusi Nontrivial dari SPLH AX = O )
1.
Tentukan r = rk ( A) . Jika r ≥ n , maka SPLH tidak mempunyai solusi nontrivial, [berhenti]. Jika r < n , maka SPLH mempunyai solusi, masuk ke langkah 2.
Seminar Nasional Matematika dan Pendidikan Matematika Yogyakarta, 3 Desember 2011 MA ‐ 5
PROSIDING
2.
ISBN : 978 – 979 – 16353 – 6 – 3
Jika m < n , tambahkan baris-baris nol pada A sehingga diperoleh matriks ⎡ A⎤ A ' = ⎢ ⎥ berukuran m ' x n , dengan m ' ≥ n . ⎣O ⎦
3.
Tentukan a ≠ 0 ∈ AnnR ( I r +1 ( A ')) .
4.
Jika r = 0 , maka v = (a a L a )T ∈ R n merupakan solusi nontrivial dari
AX = O . Jika 1 ≤ r < n , masuk ke langkah 5. 5.
Tentukan
Δ (i1 ,L , ir ; j1 ,L , jr )
minor
dari
A'
sedemikian
hingga
aΔ(i1 ,L , ir ; j1 ,L , jr ) ≠ 0 . 6.
Tentukan P ∈ GL ( m ', R ) dan Q ∈ GL ( n, R ) sedemikian hingga ⎡C *⎤ A '' = PA ' Q = ⎢ ⎥ ⎣ * *⎦ ai1 j1
L ai1 jr
dengan det(C ) = M M = Δ (i1 ,L , ir ; j1 ,L , jr ). air j1 L air jr 7.
Tentukan
⎡ ai1 j1 L ai1 jr ⎢ ⎢ M C'= ⎢ a L air jr ⎢ ir j1 ⎢⎣ air +1 j1 L air +1 jr
8.
Tentukan d j = Cof ( r +1) j (C ') , j = 1, 2,L , r + 1 .
9.
Dibentuk v ' = ( ad1
ad 2 L ad r +1
ai1 jr +1 ⎤ ⎥ M ⎥ . air jr +1 ⎥ ⎥ air +1 jr +1 ⎥⎦
0 L 0)T ≠ O ∈ R n .
10. Tentukan v = Qv ' , yang merupakan solusi dari SPLH AX = O . Selanjutnya, akan dibahas mengenai sistem persamaan linear AX = B . Pertama akan dibahas syarat perlu suatu sistem persamaan linear AX = B memiliki solusi untuk setiap A ∈ M nxn ( R ) dan B ∈ R n . Dalam sistem persamaan linear atas lapangan, jika diketahui SPL AX = B mempunyai solusi, maka rank ( A | B ) = rank ( B ) . Sama halnya dengan sistem persamaan linear
atas
R.
Oleh
karena
definisi
rank
matriks
atas
R
adalah
Seminar Nasional Matematika dan Pendidikan Matematika Yogyakarta, 3 Desember 2011 MA ‐ 6
PROSIDING
ISBN : 978 – 979 – 16353 – 6 – 3
max{t ∈ Z | AnnR ( I t ( A)) = {0}} maka syarat perlu SPL AX = B memiliki solusi adalah I t ( A | B ) = I t ( A) untuk setiap t ∈Z . Hal ini dipaparkan dalam teorema berikut. Teorema 2.3. (Syarat Perlu) Diberikan A ∈ M n x n ( R ) . Jika AX = B mempunyai solusi
maka I t ( A | B ) = I t ( A) untuk setiap t ∈ Z .
Selanjutnya, akan diberikan suatu teorema yang merupakan syarat cukup suatu sistem persamaan linear AX = B memiliki solusi untuk setiap A ∈ M nxn ( R ) dan B ∈ R n . Namun, sebelumnya telah diketahui bahwa z ∈ R merupakan elemen regular di R jika bukan merupakan elemen pembagi nol dari R . Dengan demikian apabila Z ( R ) merupakan himpunan semua elemen-elemen pembagi nol dari R maka R \ Z ( R ) merupakan himpunan elemen-elemen regular dalam R . Teorema 2.4. (Syarat Cukup) Diberikan matriks A = ⎡⎣ aij ⎤⎦ ∈ M mxn ( R ) dengan m ≤ n ,
rk ( A) = m , dan matriks B ∈ R m . Jika terdapat ideal I di R dan elemen regular z ∈ R sedemikian sehingga I I m ( A | B ) * ⊆ Rz ⊆ I I m ( A) , dengan I m ( A | B ) * merupakan ideal di R yang dibangun oleh himpunan
{Δ (1,.., m; j ,.., j 1
m −1
, n + 1|1 ≤ j1 < .. < jm−1 ≤ n )} ,
maka sistem persamaan linear AX = B memiliki solusi. Bukti. Karena diketahui rk ( A) = m maka AnnR ( I m ( A) ) = {0} , sehingga diperoleh
I m ( A) ≠ 0 . Akibatnya terdapat minimal minor mxm dari A yang tidak nol, katakan Δ = Δ (1,.., m; j1 ,.., jm ) dengan Δ (1,.., m; j1 ,.., jm ) ≠ 0 . Diperhatikan submatriks mxm ⎡ a1 j1 L a1 jm ⎤ ⎢ ⎥ dari A yakni A = ⎢ M M ⎥ . Diperoleh det ( A ) = Δ (1,.., m; j1 ,.., jm ) ≠ 0 dan ⎢ amj L amj ⎥ m ⎦ ⎣ 1
⎡ b1 ⎤ ⎡ b1 ⎤ ⎡ b1 ⎤ ⎢ ⎥ ⎢ ⎥ Δ ⎢ M ⎥ = det ( A ) ⎢ M ⎥ = Aadj ( A ) ⎢⎢ M ⎥⎥ . ⎢⎣bm ⎥⎦ ⎢⎣bm ⎥⎦ ⎢⎣bm ⎥⎦
...(i)
Di sisi lain diketahui bahwa:
Seminar Nasional Matematika dan Pendidikan Matematika Yogyakarta, 3 Desember 2011 MA ‐ 7
PROSIDING
⎡ b1 ⎤ ⎡ cof11 ( A ) ⎢ adj ( A ) ⎢⎢ M ⎥⎥ = ⎢ M ⎢ ⎢⎣bm ⎥⎦ cof1m ( A ) ⎣⎢
ISBN : 978 – 979 – 16353 – 6 – 3
⎡ m ⎤ cof j1 ( A ) b j ⎥ L cof m1 ( A ) ⎤ ⎡ b1 ⎤ ⎢ ∑ j =1 ⎥ ⎥⎢ ⎥ ⎢ ⎥ M M ⎥⎢ M ⎥ = ⎢ ⎥ ⎥ ⎢b ⎥ ⎢ m L cof mm ( A ) ⎦⎥ ⎣ m ⎦ ⎢ ⎥ cof A b jm ( ) j ⎢⎣ ∑ ⎥⎦ j =1
...(ii)
Misalnya, dipilih ( c1 ,..., cm ) ∈ R m dengan: T
⎡ a1 j1 L a1 ji−1 ⎢ ci = ∑ b j cof ji ( A ) det ⎢ M M j =1 ⎢ amj L amj i −1 ⎣ 1 m
b1
a1 ji+1
M bm
M amji+1
L a1 jm ⎤ ⎥ M ⎥ ∈ Im ( A | B ) * L amjm ⎥⎦
untuk setiap nilai i = 1, 2,..., m . Dari Persamaan (i) dan (ii) diperoleh: ⎡ b1 ⎤ ⎡ a1 j1 L a1 jm ⎤ ⎡ c1 ⎤ ⎢ ⎥ M ⎥ ⎢⎢ M ⎥⎥ Δ ⎢⎢ M ⎥⎥ = ⎢ M ⎣⎢bm ⎦⎥ ⎢⎣ amj1 L amjm ⎥⎦ ⎣⎢ cm ⎦⎥ m
sehingga diperoleh Δbi = ∑ aiju cu untuk setiap nilai i = 1, 2,..., m . u =1
Selanjutnya, didefinisikan y1 , y2 ,..., yn sebagai berikut:
⎧ 0 , jika v ∈ {1,..., n} − { j1 ,..., jm } yv = ⎨ ⎩ci , jika v = ji untuk setiap i = 1, 2,..m Karena ci ∈ I m ( A | B ) * untuk setiap i = 1, 2,..., m ,maka diperoleh yv ∈ I m ( A | B ) * untuk setiap v = 1, 2,..., n . Selain itu diperoleh: n
∑a v =1
iv
yv = aij1 y j1 + ... + aijm y jm = aij1 c1 + ... + aijm cm =Δbi
untuk setiap nilai i = 1, 2,..., m . Dengan demikian untuk setiap i = 1, 2,..., m diperoleh: n
Δbi = ∑ aiv yv , dengan y1 , y2 ,..., yn ∈ I m ( A | B ) * . v =1
Misalnya,minor-minor mxm tak nol dari A adalah Δ1 ,..., Δ p maka untuk setiap k = 1, 2,..., p
terdapat
{ ykv ∈ R | v = 1, 2,..., n} ⊆ I m ( A | B ) *
sedemikian
sehingga
n
Δ k bi = ∑ aiv ykv , untuk i = 1, 2,..., m . Karena diketahui I I m ( A | B ) * ⊆ Rz ⊆ I I m ( A) v =1
Seminar Nasional Matematika dan Pendidikan Matematika Yogyakarta, 3 Desember 2011 MA ‐ 8
PROSIDING
ISBN : 978 – 979 – 16353 – 6 – 3
p
maka z ∈ I I m ( A) . Oleh karena Δ1 ,..., Δ p membangun I m ( A) maka z = ∑ qk Δ k k =1
dengan q1 ,..., q p ∈ I . Dengan demikian diperoleh: p ⎛ n ⎞ p a q y q a y = ∑∑ ∑ iv k kv k ⎜ ∑ iv kv ⎟ = ∑ qk Δ k bi = zbi k =1 v =1 k =1 ⎝ v =1 ⎠ k =1 p
n
⎛ p ⎞ a ∑ iv ⎜ ∑ qk ykv ⎟ = zbi untuk v =1 ⎝ k =1 ⎠ n
untuk setiap i = 1, 2,..., m . Oleh karena itu , diperoleh
setiap i = 1, 2,..., m . Oleh karena qk ∈ I dan ykv ∈ I m ( A | B ) * untuk setiap k = 1, 2,..., p dan v = 1, 2,..., n maka diperoleh
p
∑q k =1
k
ykv ∈I I m ( A | B ) * untuk v = 1, 2,..., n . Oleh karena
I I m ( A | B ) * ⊆ Rz maka untuk v = 1, 2,..., n diperoleh n
Akibatnya diperoleh
∑a v =1
p
∑q k =1
k
ykv = rv z untuk suatu rv ∈ R .
⎛ n ⎞ r z = zbi untuk i = 1, 2,..., m . Atau, z ⎜ ∑ aiv rv ⎟ = zbi untuk ⎝ v =1 ⎠
iv v
setiap i = 1, 2,..., m . Oleh karena z merupakan elemen regular di R maka
n
∑a v =1
r = bi
iv v
untuk setiap i = 1, 2,..., m . Jadi diperoleh bahwa ξ = ( r1 , r2 ,..., rn ) ∈ R n merupakan solusi T
dari sistem persamaan linear AX = B . Selanjutnya, apabila I m ( A) = R maka rk ( A) = m . Untuk setiap B ∈ R m memenuhi RI m ( A | B ) * ⊆ R1 ⊆ RI m ( A) . Oleh karena 1 merupakan elemen regular di R , maka berdasarkan Teorema 2.4 diperoleh bahwa sistem persamaan linear AX = B memiliki solusi. Dengan demikian, diperoleh akibat sebagai berikut ini. Akibat 2.5. Jika diberikan matriks A ∈ M mxn ( R ) dengan I m ( A) = R maka untuk setiap
B ∈ R m sistem persamaan linear AX = B memiliki solusi.
Selanjutnya, berikut diberikan suatu algoritma untuk menentukan solusi dari SPL AX = B atas R . Algoritma ini dikonstruksi dari Teorema 2.3 dan Teorema 2.4.
Seminar Nasional Matematika dan Pendidikan Matematika Yogyakarta, 3 Desember 2011 MA ‐ 9
PROSIDING
ISBN : 978 – 979 – 16353 – 6 – 3
Algoritma (menentukan solusi dari SPL AX = B , dengan A ∈ M m x n ( R ) dan B ∈ R m )
1. Tentukan I t ( A | B) dan I t ( A) , untuk setiap t ∈ Z . Jika I t ( A | B) ≠ I t ( A) untuk suatu
t ∈ Z , maka SPL AX = B tidak mempunyai solusi. [proses berhenti] Jika I t ( A | B) = I t ( A) untuk setiap t ∈Z , maka masuk ke langkah 2.
m > n , maka ubah SPL
2. Jika
AX = B
A' X ' = B
menjadi SPL
dengan
A ' = [ A | Om x n ' ] dan X ' = ( x1 ,L , xn , xn +1 ,L , xn ' )T , n ' ≥ m .
3. Tentukan rk ( A) , ideal I dari R , dan elemen regular z dari R sedemikian hingga I I m ( A | B)* ⊆ Rz ⊆ I I m ( A) .
4. Tentukan semua minor m x m dari A yang tak nol, katakan Δ1 , Δ 2 ,L , Δ p . 5. Untuk k = 1, 2,L , p dan i = 1, 2,..., m didefinisikan: m
cki = ∑ b j Cof ji ( A( k ) ) j =1
dengan
A( k )
⎡ a1 j1 ( k ) L a1 jm ( k ) ⎤ ⎢ ⎥ M ⎥ dan det( A ( k ) ) = Δ k . =⎢ M ⎢a (k ) L a (k ) ⎥ m jm ⎣ m j1 ⎦
(k ) (k ) ⎪⎧0 , jika l ∈ {1,L , n} − { j1 ,L , jm } 6. Tentukan ykl = ⎨ . (k ) ⎪⎩cki , jika l = ji p
7. Tentukan q1 ,L , q p ∈ I sedemikian hingga z = ∑ qk Δ k . k =1
8. Untuk l = 1,L , n , tentukan rl sedemikian hingga
p
∑q k =1
k
ykl = rl z .
9. Diperoleh v = ( r1 , r2 ,L , rn )T yang merupakan solusi dari AX = B .
Terakhir pada makalah ini akan diberikan Aturan Cramer yang ternyata masih dapat digunakan untuk mencari ketunggalan dari solusi sistem persamaan linear atas ring R . Teorema 2.6. (Aturan Cramer) Jika diberikan matriks
A ∈ M nxn ( R ) dengan
det ( A) ∈ U ( R ) maka untuk setiap B ∈ R n sistem persamaan linear AX = B memiliki
Seminar Nasional Matematika dan Pendidikan Matematika Yogyakarta, 3 Desember 2011 MA ‐ 10
PROSIDING
solusi tunggal v = ( y1 , y2 ,..., yn ) dengan y j = T
ISBN : 978 – 979 – 16353 – 6 – 3
Aj A
, dimana A j merupakan determinan
dari matriks A dengan mengganti kolom ke- j dari matriks A dengan B , untuk nilai j = 1, 2,..., n
Bukti. Diketahui v = ( y1 , y2 ,..., yn )
dengan y j =
T
Aj A
untuk setiap
j = 1, 2,..., n .
Menggunakan Ekspansi Laplace diperoleh: ⎡ a11 L a1 j −1 b1 ⎢ det ( A ) y j = det ⎢ M M M ⎢ an1 L anj −1 bn ⎣
a1 j +1 L a1n ⎤ n ⎥ M M ⎥ = ∑ bi cof ij ( A ) i =1 anj +1 L ann ⎥⎦
Oleh karena itu, diperoleh: ⎡ n ⎤ cof i1 ( A ) bi ⎥ ∑ ⎢ y ⎡ cof ( A ) L cof n1 ( A ) ⎤ ⎡ b1 ⎤ ⎡ 1⎤ ⎢ i =1 ⎥ ⎢ 11 ⎥⎢ ⎥ ⎢ ⎥ det ( A ) ⎢ M ⎥ = ⎢ M M M ⎥=⎢ ⎥ ⎢ M ⎥ = adj ( A ) B ⎢ ⎥ n ⎢ ⎥⎢ ⎥ ⎢⎣ yn ⎥⎦ ⎢ ∑ cof in ( A ) bi ⎥ ⎣ cof1n ( A ) L cof nn ( A ) ⎦ ⎣bn ⎦ ⎢⎣ i =1 ⎥⎦ Karena diketahui bahwa det ( A) I n = adj ( A) A maka diperoleh adj ( A) [ Av ] = adj ( A) B . Oleh karena adj ( A ) merupakan matriks invertibel (dengan inversnya adalah
( adj ( A) )
−1
= ( det ( A) )
−1
( A) ),
maka
v = ( y1 , y2 ,..., yn ) , dengan y j = T
Aj A
diperoleh
Av = B .
Jadi
terbukti
bahwa
untuk setiap j = 1, 2,..., n , merupakan solusi dari
AX = B . Selanjutnya, andaikan v ' juga merupakan solusi dari AX = B , maka
diperoleh
Av ' = Av = B .
Akibatnya
diperoleh
A ( v '− v ) = 0 .
Oleh
karena
det ( A) ∈ U ( R ) maka matriks A invertibel, sehingga diperoleh v '− v = 0 . Akibatnya v merupakan solusi tunggal dari AX = B . Berdasarkan Cramer diperoleh bahwa ketunggalan dari solusi SPL AX = B atas R dapat ditentukan apabila A merupakan matriks persegi yang invertibel. Dengan
demikian, Aturan Cramer hanya dapat digunakan untuk kasus khusus matriks A merupakan matriks persegi yang invertibel.
Seminar Nasional Matematika dan Pendidikan Matematika Yogyakarta, 3 Desember 2011 MA ‐ 11
PROSIDING
ISBN : 978 – 979 – 16353 – 6 – 3
3. KESIMPULAN
Dari keseluruhan pembahasan makalah ini dapat disimpulkan: 1. Kekonsistenan SPLH atas ring komutatif dijamin oleh Teorema McCoy yang menyatakan bahwa SPL AX = 0 , dengan A ∈ M mxn ( R ) , memiliki solusi nontrivial jika dan hanya jika rk ( A) < n . Lebih lanjut, jika jumlah persamaan kurang dari jumlah variabel maka sistem persamaan linear homogen memiliki solusi nontrivial. 2. Syarat perlu agar SPL AX = B memiliki solusi adalah I t ( A | B ) = It ( A) untuk setiap
t ∈ . Sedangkan, syarat cukup agar SPL AX = B memiliki solusi adalah apabila terdapat ideal I di R dan elemen regular z ∈ R sedemikian sehingga memenuhi
I I m ( A | B ) * ⊆ Rz ⊆ I I m ( A) . Lebih lanjut, jika I m ( A) = R maka untuk setiap B ∈ R m diperoleh SPL AX = B memiliki solusi. 3. Jika matriks A invertibel maka berdasarkan Aturan Cramer sistem persamaan linear atas ring komutatif AX = B memiliki solusi tunggal untuk setiap B ∈ R n .
4. DAFTAR PUSTAKA
[1] Brown, W.C., 1993, Matrices Over Commutative Rings, Marcel Dekker Inc., New York [2] McCoy, N.H., 1948, Rings and Ideals, George Banta Company Inc., Winconsin
Seminar Nasional Matematika dan Pendidikan Matematika Yogyakarta, 3 Desember 2011 MA ‐ 12