IMPLEMENTASI BASIS GROEBNER DALAM MENENTUKAN KEANGGOTAAN IDEAL DI “CAS SINGULAR” Enik Noviani 1) I Made Sulandra 1) Hery Susanto 1)s 1)
FMIPA Universitas Negeri Malang
suatu ideal, dengan Abstrak: Misalkan ,…, ,…, 0 untuk setiap ,…, oleh , … , tidak tunggal, 1, … , . Sisa pembagian polinomial basis tergantung pada urutan , … , . Sisa pembagian tersebut akan tunggal jika , … , Groebner. Oleh karena itu, untuk menyelesaikan masalah keanggotaan ideal, apakah ? perlu dilakukan pembagian oleh basis Groebner. jika dan hanya jika sisa pembagian oleh basis Groebner dari adalah nol. Pada artikel ini disajikan algoritma yang diimplementasikan pada Sistem Aljabar Komputer Singular untuk memeriksa keanggotaan di dan menghitung koefisien dari kombinasi linearnya. Kata Kunci: polinomial, basis Groebner, algoritma pembagian, sisa pembagian
,…, adalah ring Dalam artikel ini, menyatakan lapangan (field) dan polinomial dengan operasi tambah dan kali baku. Misalkan ,…, ,…, dan himpunan ! | ,…, . Selanjutnya disebut ideal yang dibangun oleh dan adalah ideal dari ,…, dinotasikan ,…, . Berdasarkan algoritma pembagian, jika diberikan sebarang polinomial terdapat , … , , # sehingga ,…, ,…, ! # dengan syarat lp max)max * * )lp lp +, #+, dengan lp merupakan power product utama dan # disebut sisa pembagian oleh . Ternyata sisa pembagian tersebut tidak tunggal dan tergantung pada urutan pembagian oleh . Sebagai ilustrasi misalkan , , , , - . , / , dengan 02 , / 2 3 , / - 0 6 , / , 0 4 / - 2 , 3 / 02/ , 02 , 3 / , / - 2/ Berikut ini merupakan hasil pembagian oleh , , , - dengan menggunakan order degrevlex dan 6 / dengan sebarang urutan. 01 , 0 - 6 / ......(1) 7 ,/ - 0 , ,/ 3 , 2 / 8 7
/ 0
, -
7/ 0 2
- , / 3 , 2 , - / 3/ , 0 18 , , - / 3/ , 0 18 , ,
7/ 2 0 6 / 26/ 02 / , 3 0 9 02 / , 3 -
/8
01 , : , / 0 / /8 9 , : 703/ - , / 0 138 7,
9
0
3/ , 0 1 , , 3 01 ,
-
0 0
18/
6 /
0
703/ ,
: 8 ,
......(2)
6 / ......(3) ......(4) ......(5) ......(6)
Dari persamaan (1) sampai (5) belum dapat disimpulkan bahwa = , , , - , walaupun sisa pembagian tidak nol. Faktanya, dengan urutan pembagian oleh - , , , dapat disimpulkan bahwa , , , - , karena sisanya nol. 1
@
3 , ? > ,? > 01 02 / , 3 -
Untuk persamaan (6) dapat ditulis dalam bentuk perkalian matriks menjadi
@
3 , dengan > ? merupakan matriks koefisien dari . 01 02 / , 3 Basis Groebner untuk , , , - terhadap order degevlex dengan 6 / adalah A B , B, , B- , B9 , dengan B 02/ , B, 02 , 3 / , / - 2/ BB9 02/ Terlihat bahwa A memuat , , , - , yaitu A , , , - C B9 Karena B , B, , B- , B9 merupakan basis Groebner untuk , , , - dan , ,, - , maka ketika dibagi oleh A dengan suatu urutan tertentu sisanya harus nol. Jika dibagi oleh A dengan urutan B- , B , B, , B9 diperoleh 3 , B 01 B, 0 B9 0 02 / , 3 Byang jika dituliskan dalam bentuk matriks menjadi @ B 3 , B, 01 D E DB E 02 / , 3 B9 0 Sisa pembagian oleh basis Groebner adalah tunggal untuk sebarang urutan pembagian B , B, , B- , B9 (lihat lampiran). Ketika dibagi oleh basis Groebner A B , B, , B- , B9 dengan urutan B- , B , B, , B9 diperoleh koefisien dari B9 adalah nol, tetapi dengan urutan pembagian yang berbeda, koefisien dari B9 dimungkinkan tidak nol (lihat lampiran). Karena , , , - maka perlu dicari hubungan antara B9 dengan , , , - . B , B, , BPada artikel ini, akan ditentukan sifat keanggotaan dari suatu polinomial di ideal , … , . Selain itu, jika ,… akan dicari , … , sehingga ! . Untuk itu perlu disusun suatu algoritma yang akan diimplementasikan pada Sistem Aljabar Komputer Singular. Basis Groebner Dari penjelasan sebelumnya terdapat sifat yang menarik dari pembagian polinomial oleh basis Groebner A, yaitu sisa pembagiannya tunggal. Dengan demikian untuk ,…, ,…, menentukan keanggotaan polinomial terhadap suatu ideal hanya cukup dilakukan sekali proses pembagian oleh basis Groebner A dari ideal , jika sisa pembagiannya sama dengan 0 maka dan sebaliknya. Oleh karena itu, dapat dikatakan bahwa basis Groebner merupakan suatu pembangun khusus dari ideal .
dengan G • lp • lc • lt
,…,
0, dapat ditulis sebagai G ! GK HL HM HI HJ 0 0 , N , dan 6 6 ! 6 HL , dan HI , sebagai power product utama dari G , sebagai koefisien utama dari G HI , sebagai suku utama dari
Definisi Untuk setiap
HI
, G,
HJ
2
, ideal suku utama dari Q adalah himpunan yang ,…, Definisi Misalkan Q dibangun oleh suku utama dari polinomial-polinomial di Q, yaitu Lt Q lt | Q dengan, lt merupakan suku utama dari polinomial .
,…, Dari definisi ini terlihat bahwa, jika ada sebarang Q , maka dapat dibuat suatu ideal yang anggotanya merupakan kombinasi linear dari suku utama polinomialpolinomial di Q. ,…,
Teorema Basis Hilbert Misalkan ideal dari ,…, ,…, . sehingga
maka ada
,…,
anggota
,…, Dengan kata lain, untuk setiap ideal dari mempunyai pembangun hingga, dan dapat ditentukan himpunan pembangunnya tersebut.
, dengan B 0. Polinomial direduksi ke S oleh Definisi Misalkan , B, S ,…, B dalam satu langkah jika lp B membagi suku tak nol T yang berada di dan ditulis dan
U
VS
S
0
T B lt B
Terlihat bahwa proses reduksi terjadi jika ada suku tak nol T (suku utama atau bukan) di yang dapat dibagi oleh lp B . Selain itu, polinomial S yang merupakan hasil reduksi oleh B dapat ditulis sebagai kombinasi linear dari dan B. Proses reduksi dapat melibatkan lebih dari satu polinomial dan dapat dilanjutkan sampai tidak ada lagi suku tak nol di S yang dapat dibagi oleh lp , maka S yang seperti ini disebut hasil reduksi oleh yang diberikan dalam definisi berikut ini:
Definisi Misalkan , S, , … , dengan ,…, 0 untuk setiap 1, … , , , … , . Polinomial dikatakan direduksi ke S oleh jika ada barisan index dan , ,, … , W 1, … , dan barisan polinomial-polinomial S , … , SWX ,…, sehingga YMI
Y MJ
YM]^I
YM\
YM]
Z[ S Z[ S, Z[ … Z__[ SWX Z[ S
atau dapat ditulis
`
Va S
Dari rangkaian reduksi ini, terlihat bahwa S dapat ditulis sebagai kombinasi linear dari , … , , seperti yang diberikan dalam teorema berikut ini: ,…,
Teorema Misalkan
polinomial dan
,#
,…,
lp
,…,
,…,
`
0 0 dan
dengan Va #, sehingga ! #
max 7max )lp **
,…, dan A Definisi Misalkan ideal dari disebut Basis Groebner untuk , jika untuk setiap lp B membagi lp . 3
lp
+, lp # 8
,…,
, terdapat
B , … , BW 0 0 . Himpunan A 0 0 ada B A sehingga
Terlihat bahwa, jika A merupakan basis Groebner untuk ideal , maka untuk setiap 0 0 pasti dapat direduksi oleh suatu B A, namun dalami definisi ini belum menjamin keberadaan basis Groebner untuk suatu ideal . Selanjutnya akan diberikan beberapa karakteristik dari basis Groebner berkaitan dengan algoritma pembagian dan ideal suku utama. ,…, Teorema Misalkan ideal tak nol dari Pernyataan-pernyataan berikut ekivalen: (i) A adalah Basis Groebner untuk . (ii) (iii) (iv)
Lt A
s s
Lt
r
Va 0. ∑Wu S B , dan lp
dan A
max
B , … , BW b 0 0 .
*v*w )lp
S lp B +
Bukti: Lihat Adams dan Loustanou (1994 : 33) Terlihat bahwa jika dan hanya jika hasil reduksi (sisa pembagian) oleh basis Groebner A adalah nol, dan dapat dituliskan sebagai kombinasi linear dari B , … , BW . Tetapi, dari teorema ini belum dapat dipastikan apakah untuk setiap ideal pasti mempunyai basis Groebner. Metode pencarian basis Groebner diberikan oleh Algoritma Buchberger. Dalam algoritma tersebut diperlukan Q-polinomial dan algoritma pembagian.
Definisi Misalkan , g Q-polinomial dari dan
g
,…, 0 0 dan x lcm 7lp didefinisikan dengan x x 0 Q) , g + g lt lt) g +
, lp) g +8.
Dari definisi ini, terlihat bahwa Q) , g + menghilangkan suku utama dari sehingga , lp) g +8. lp 7Q) , g +8 i max 7lp
dan
g,
Selain itu Q) , g + merupakan kombinsai linear dari , g , dengan koefisien dari y zw YM
dan koefisien dari
g
adalah
y 0 . zw)Y{ +
Algoritma Buchberger : Ideal ,…, b ,…, dengan setiap 1,2, … , Output :A B , … , BW suatu Basis Groebner untuk Initialization : A c d c ef , g h| i j dengan , j 1,2, … , op While d q do Pilih sebarang f , g h d Input
d c d 0 ef , g hp r
Q) , g + Va S If S 0 then d c d Cf ,S | AcAC S Return A
A oh 4
0 untuk
,…,
adalah
pasti mempunyai himpunan pembangun hingga, ,…, Untuk setiap ideal dari dan berdasarkan algoritma Buchberger telah dijamin keberadaan dari basis Groebner A untuk sebarang ideal tak nol . Terlihat bahwa untuk setiap S 0 yang merupakan hasil reduksi Q) , g + oleh A ditambahkan ke A (A c A C S ), sehingga A pasti memuat , sehingga menjamin keberadaan dari basis Groebner A. Proses pencarian S ini pasti berhenti karena dijamin oleh teorema basis Hilbert. Misalkan terdapat S , … , S| dengan A} A}X C S} untuk setiap ~ 1, … , • dan B , … , BW dengan B A€ , sehingga A A| , … , , S , … , S| atau A untuk setiap 1,2, … , dan B a} S} untuk setiap ~ 1, … , • dan • •. Polinomial B a} merupakan sisa pembagian Q)B , Bg + oleh A}X , sehingga Q) , g +
Misalkan x B
a}
B
B
X 0 ∑}u
!
a}X
B}X
B
lcm 7lp B , lp)Bg +8, sehingga diperoleh
a}X Q)B , Bg + 0 ∑ƒu
„ zw UM
, B,
„ 0 zw)U Bg {+ } B}
ƒ Bƒ 0 ∑}ua…X
7zw U 0 „
M
8B
Dari persamaan ini terlihat bahwa B B, 1,2, … , ~ 0 1.
} B}
a}
∑gX }u a
} B}
a}X
‚
a}
ƒu
ƒ Bƒ
†0 zw)U 0 1‡ Bg „
{+
B
a}
a…X ∑}uga
dapat ditulis sebagai kombinasi linear dari
} B}
Perhatikan bahwa: 1) B a dapat ditulis sebagai kombinasi linear dari , 1,2, … , . 1,2, … , 1, karena 2) B a, dapat ditulis sebagai kombinasi linear dari B , B a tadi dapat ditulis sebagai kombinasi linear , 1,2, … , , maka jika disubtitusikan B a ke persamaan B a, akan diperoleh B a, sebagai kombinasi linear dari B , 1,2, … , . 3) B a- dapat ditulis sebagai kombinasi linear dari B , 1,2, … , 2, dari 2) diperoleh bahwa B a, dapat ditulis sebagai kombinasi linear dari B , 1,2, … , , maka jika disubtitusikan B a, ke persamaan B a- akan diperoleh B asebagai kombinasi linear dari , 1,2, … , . 4) ˆ 5) Jika proses ini dilanjutkan, maka BW juga dapat ditulis sebagai kombinasi linear dari , 1,2, … , .
1, … , • dapat dituliskan sebagai kombinasi Terlihat bahwa untuk setiap B , linear dari , 1, … , . Tetapi, yang diperoleh dari algoritma Buchberger hanya basis Groebnernya saja, sedangkan penulisan B untuk setiap 1,2, … , • sebagai kombinasi linear dari , 1, … , belum bisa ditentukan. Dengan demikian, untuk menentukan keaggotaan polinomial di dan koefisien dari kombinasi linearnya diperlukan modifikasi terhadap Algoritma Buchberger.
Misalkan B merupakan matiks koefisien dari penulisan B , sebagai kombinasi linear dari , … , . Untuk 1,2, … , , B )Gg + 0, jika j o , , j 1,2, … , dengan, Gg ‰ 1, jika j
5
1,2, … , •
Perhatikan bahwa untuk
B
a
1, maka
Q)B , Bg + 0 ‚ ƒu
ƒ Bƒ
,
apabila ditulis dalam bentuk perkalian matriks menjadi L 0L B‡ Bg Ž )Bg + 0 ‚ B Ba † • lt B lt)Bg +
Sehingga
dengan Gƒ
B
)Gƒ +, a „ ’zw U 0 , untuk ” • M X„ 0 g , untuk ” ‘ zw)U{ + •0 , •
ƒu
o j ,”
ƒ
)Bƒ +
1, … ,
untuk lainnya
Dengan cara yang sama untuk 2, 3, … , • koefisien dari kombinasi linear B juga dapat dituliskan dalam bentuk matriks. Dengan menambahkan penulisan B sebagai kombinasi linear dari , … , pada algoritma Buchberger, akan diperoleh dua hal dalam algoritma yang baru, yaitu basis Groebner dan koefisien dari kombinasi linear B . Teorema Misalkan A B , … , BW ,…, Groebner jika dan hanya jika untuk setiap adalah tunggal.
0 0 . Himpunan A merupakan basis ,…, , sisa pembagian oleh A
Bukti: Lihat Adams dan Loustanou (1994 : 34)
b 0 0, dan Ideal ,…, ,…, ,…, Misalkan dengan A B , … , BW merupakan Basis Groebner untuk . Untuk menentukan keanggotaan di hanya diperlukan sekali pembagian oleh A, karena sisa pembagian oleh A dijamin ketunggalannya.
, berdasarkan teorema, diperoleh B ! W BW dengan ,…, untuk setiap 1,2, … , • . Padahal jika dan pembangun dari , maka dapat ditulis sebagai S ! S Berdasarkan algoritma Bucberger, untuk setiap B , 1,2, … , • dapat ditulis 1,2, … , , sehingga dengan melakukan subtitusi sebagai kombinasi linear dari , balik B yang telah ditulis sebagai kombinasi linear dari , … , ke akan diperoleh penulisan sebagai kombinasi linear dari , … , . Jika
Algoritma untuk menentukan keanggotaan ideal dan koefisien kombinasi linearnya Dalam algoritma ini, selain dapat menentukan keanggotaan polinomial di ideal b dengan ,…, ,…, 0 untuk setiap 1,2, … , , untuk dapat mencari , … , 1 , … , – sehingga memenuhi ! . Hal ini dikarenakan pada algoritma yang baru dilakukan modifikasi terhadap algoritma Buchberger, yaitu dengan menambahkan suatu prosedur untuk menuliskan koefisien kombinasi linear dari B A B , … , BW (A merupakan basis Groebner untuk ideal )
6
terhadap himpunan pembangun ideal , yaitu sebagai berikut:
,…,
. Algoritma yang dimaksud adalah
: * ideal ,…, b ,…, dengan 0 untuk setiap 1,2, … , * ,…, Output : (1) = atau yang (2) dan himpunan terurut ,…, memenuhi ! Initialization : c B | 1,2, … , dengan B merupakan koefisien matriks B A c A˜ c ef , g h| Ap g
Input
Matrix Stmpš Matrikx mHš While A˜ q do • Pilih f , g h A˜ x
•
lcm 7lp
, lp) g +8
Stmp
c zw
r
Q) , g + Va S If S 0 then A cAC S
• •
Else
• r
V If •
mH –B A˜ Stmpš mHš
†zw)Y +‡
c } } c Stmp 0 mH c A˜ C f , S |ž c 0š c 0š
X„
{
œ g•
Ah 0 f , g h
A˜ c A˜ 0 f , g h
0 then ∑}u
Return(1,
„ YM |r| ∑}u
//matriks koefisien dari Q) , g + //matriks koefisien dari hasil bagi
,…,
}
}
)
Selanjutnya algoritma ini dapat dituliskan dalam Sistem aljabar computer Singular, berikut ini merupakan contoh implementasi dari ilustrasi yang diberikan di depan, yaitu menentukan keanggotan di — ,/ . Keterangan dari hasil yang dikeluarkan oleh program adalah sebagai berikut: 1. Ouput yang pertama ini digunakan untuk menentukan apakah . Jika tertulis simbol 1, hal ini menandakan bahwa , dan jika tertulis simbol 0, ini menandakan bahwa = 2. Output yang kedua ini merupakan koefisien dari kombinasi linear dari terhadap unsur pembangunnya.
7
Contoh 1:
Pada contoh ini, yang dikeluarkan dikelua oleh program adalah simbol
yangg artinya
dan
yangg artinya
.
Contoh 2:
Pada contoh ini, yang dikeluarkan dikelua oleh program adalah simbol
Kesimpulan 1. Jika merupakan mer ring polinomaial atas lapangan dan merupakan an ideal dari , dengan menggunakan Cass Singular dapat ditentukan an basis Grobner Grob untuk . merupakan Basis Groebner untuk ideal , maka untuk 2. Misalkan setiap dapat ditulis sebagai kombinasi linear dari , sehingga un untuk setiap dapat dituliskan dit sebagai kombinasi linear dari denga dengan menggunakan nakan Sistem aljabar computer Singular. Selain dapat digunakan unakan untuk memeriksa keanggotaan ideal, dengan melakukan ssedikit modifikasi algoritma ini dapat dapa digunakan untuk mencari invers di ketika inversnya ada. Pembaca yang berminat dapat juga menggunakan program gram ini untu untuk menentukan penelitian elitian tentang tentan kelipatan persekutuan terkecil (KPK). Daftar Rujukan: Adams, W. William iam and Loustaunau Lous Philippe. 1994. An Introduction to Grobner robner Bases. Amerika:: American Mathematical M Society. Adkins, William A. and Weintraub, Wein Steven H. 1992. Algebra an Approachh via M Module Theory. Amerika: Springer-Verlag. Spr Gallian, J.A. 1990. Contempo ontemporary Abstract Algebra. United State of America: Heath He and Company. L 1999. Elements of Modern Algebra. Amerika Amerika: Gilbert, Jimmie and Gilbert, Linda. Brookscole.
8
Lampiran 7 ,/- 0
, 7 ,/- 0 , 7 ,/- 0 , 7 ,/- 0 , 7 ,/- 0 , 7 ,/- 0 , 7/ 2 0 , / 7/ 2 0 , / 7/ 2 0 , / -
, , , , , ,
/
3
,
/
3
,
/
3
/
3
/ /
3 3
2 /8 B
01 B,
2 /8 B
0 B-
2 /8 B
,
2 /8 B
,
3/ 0 18 B,
3/ , 0 18 B, 03 0 13 B9 0 7/ 2 0 , / - 3/ , 0 18 B, 703/ - 0 3 - / ,
: / ,
: /9 0 9 /, : /9 0 9 /, : 703/ - , / 0
703/ -
0 138 B9
: / ,
0 B
01 B,
0
01 B,
, ,
/8 B
0 138 B-
/ 0
7
, 9
7
, 9
7
7
7
/ 0
, 9
/ 0
, 9
/ 0 / 0
, 9
, , , , ,
/
3
,
/
3
,
, ,
/
, ,
/
, , , ,
/
, ,
3 3 3
, , ,
0
03 B9 01 B, 0 B-
0
0 B-
/8 B
138 B-
0
0 B-
0 0
03 B9
703/ -
3/ , 0 18 B, //, 0 3 7/ 2 0 , 0 B- 0 : 7/ 2 0 , / - 3/ , 0 18 B, 7, / 2 0 9 / - , / , 0 3 0 B 0 02 / , 3 B3 , B 01 B, 0 B9 0 02 / , 3 B3 , B 0 B9 01 B, 0 02 / , 3 0 9 B3/ , 0 1 B, 0 B 09 B9 , 02 / 3 0 9 B3/ , 0 1 B, 09 B9 0 B 02 / , 3 B3 , / B9 0 B 01 B, 0 02 / , 3 B3 , / B9 01 B, 0 B 0 , 9 , , , , 3 / 2 / 0 3 8 B9 0 B 01 7 / 0, / 7,
: /2 0 9
03 B9 0 B-
03 B9
7, 7,
0
01 B,
03 B9
2 /8 B
,
03 B9
03 B9
0 B-
2 /8 B
,
3/ , 0 18 B, ,
01 B,
0 B-
-
8 B9 8 B9 0 0
B,
: 8B ,
03 B9
0 B
0 B-
0 B-
0
0 B
0
/
2 / 0 3 8 B9
0 B
0 B-
01 B,
/
2 / 0 3 8 B9
0 B-
0 B
01 B,
/ / /
,
2 / , 0 3 8 B9 2 / , 0 3 8 B9 ,
2 / , 0 3 8 B9
9
01 B, 01 B, 0 B-
0 B
0 B-
01 B,
0 B-
0 B0 B
0 0 0 0
0 0
