Jurnal Pengajaran MIPA, Vol. 3 No. 1 Juni 2002

APLIKASI MATRIKS HANKEL PADA PERHITUNGAN RESULTAN DUA POLINOMIAL Oleh: R. Rosnawati Jurusan Pendidikan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Yogyakarta

ABSTRACT Let F be a field, f and g in F[x], with degre f is n and degre g is m. Computing resultant two polynomials with Hankel matrics give a size of matrics less than Sylvester method, that is maximum n or m. Keyword : resultan, Hankel matrics, Sylvester method

Pendahuluan Permasalahan dalam kehidupan sehari-hari seperti kisi kerja dapat disusun dalam bentuk model matematika yang pada akhirnya akan menghasilkan persamaan matriks

AX  XB  C

(1)

dengan matriks A berukuran m m dan matriks B berukuran n  n atas field F (Ma, E.C., 1966 : 490). Pentingnya penyelesaiaan persamaan (1) menimbulkan motivasi bagi para peneliti untuk mencari metode penyelesaiannya. Apabila kedua ruas pada persamaan (1) dikalikan dengan adj (I  A) dan dengan adj (I  B) , akan diperoleh :

  n   m  n 1  m1  m1   n 1 X  a i i   B j j     b i i   A j j X    A i i C  B j j   i 0  jo  j0  i 0   j0   i 0   dengan a i adalah koefisien-koefisien dari polinomial I  A ,

(2)

b j adalah

koefisien-koefisien dari polinomial I  B , Ai adalah koefisien-koefisien dari matriks polinomial adj (I  A) ,

B j adalah koefisien-koefisien dari matriks

Jurnal Pengajaran MIPA, Vol. 3 No. 1 Juni 2002

71

polinomial adj (I  B) . Selanjutnya dengan menyamakan koefisien-koefisien i ruas kanan dan ruas kiri dari persamaan (2) diperoleh:

  r   r  r  X   ai Br i     b j Ar  j  X  C k    Ar ki CBk   i 0   j 0  k 0  

(3)

untuk r  0,1,, m  n  1 . Persamaan (3) dapat dinyatakan dalam bentuk matriks partisi sebagai berikut :

M  I  A , I  B   I  m

 XB0   C 0   XB   C  1    1            XBn 1        A0 X           C m  n  2   A X   0    m1  

(4)

dengan M matriks Sylvester (Hartwig, 1972:104-110). Matriks Sylvester, M, adalah matriks bujursangkar yang mempunyai ordo jumlah dari derajat polinomial I  A dan polinomial I  B dengan elemenelemennya berasal dari koefisien-koefisien polinomial I  A dan polinomial

I  B . Agar persamaan (1) dapat diselesaikan dengan bantuan matriks Sylvester, determinan matriks Sylvester haruslah tidak nol. Determinan dari matriks Sylvester ini dikenal dengan resultan dari polinomial I  A dan polinomial I  B . Berikut ini akan dibahas mengenai pengertian resultan dua polinomial serta ide dasar pengertian resultan dua polinomial. Definisi resultan pertamakali diberikan oleh Sylvester yang dikenal dengan metode Sylvester sebagai berikut : Definisi 1 (Van der Waerden, 1953 : 84) Misalkan F adalah suatu field, f dan g adalah dua polinomial dalam F [x] yang berturut-turut berderajat n dan m; dengan n  m  1.

f ( x )  a n x n  a n 1 x n 1  a n 2 x n 2    a 0 , a n  0 g( x )  b m x m  a m1 x m 1  a m2 x m2    b 0 , b m  0

  

(5)

Resultan f dan g didefinisikan sebagai berikut :

72


a 0 0  0   Re s(f , g)  det  0  b 0 0   0 

a1 a0 0  0 b1 b0  0

a2 a1 a0  0 b2 b1  0

 an  an    a1  a0  b m 1    b2 b 0 b1

0 an  a2 a1 bm  b3 b2

0



 a3 a2 0 bm  

     b m 1

      an   0    0 b m  0 0 

matriks yang berukuran (n+m) x (n+m) di atas disebut dengan matriks Sylvester. Ide dasar pengertian resultan dua polinomial adalah sebagai berikut : Misalkan F adalah field, f dan g seperti dalam (5), akan diselidiki syarat perlu dan cukup agar dua polinomial tersebut mempunyai pembagi yang tidak konstan. Misalkan f dan g seperti dalam (5), terdapat pembagi dari f dan g jika dan hanya jika terdapat h(x) dan k (x) di dalam F [x] sehingga :

h( x ) f ( x )  k ( x ) g ( x )

(6)

dengan derajat k ( x)  n  1 ; derajat h( x)  m  1 Misalkan:

h ( x )  c m 1 x m 1  c m  2 x m 2    c1  c 0 k ( x )  d n 1 x n 1  d n 2 x n  2    d 1  d 0 Persamaan (6) dapat dinyatakan dalam bentuk sistem persamaan linear berikut :

c m 1 a n c m 1 a n 1  c m  2 a n c m 1 a n  2  c m  2 a n 1  c m 3 a n  c0 a0

 d n 1bm  d n 1bm1  d n  2 bm  d n 1bm  2  d n  2 bm1  d n 3bm   b0 d 0


      

(7)

73

yang terdiri atas

n+m persamaan linear dengan variabel-variabel ci dan dj, i  0,1,2,, m  1 , j  0,1,2, , n  1. Polinomial f dan g memiliki pembagi jika dan hanya jika sistem (7) memiliki penyelesaian yang tidak nol. Apabila sistem (7) disusun dalam bentuk matriks maka diperoleh :

 an a  n 1 a n  2     a0   0     0

0 an a n 1  a1 a0  0

 0  0  0    a n 1  a n2    a0

 bm  bm 1  bm  2   b0 0  0

0  bm  bm 1   b1  b0  0

 0   c m 1  0  0  c m  2  0  0     0          c0        bm 1   d n 1  0       bm  2  d n  2           0        b0   d 0  0

(8)

Menunjukkan bahwa sistem persamaan (8) mempunyai penyelesaian non-trivial ekuivalen dengan menyatakan determinan matriks bujur sangkar dalam persamaan (8) adalah nol. Selanjutnya determinan dari matriks bujursangkar pada persamaan (8) disebut dengan Resultan dari f dan g, ditulis dengan Re s( f , g ) . Menurut Van der Waerden (1953:83-85), Sylvester mendefinisikan Re s( f , g ) dengan mengubah matriks bujursangkar pada persamaan (8) melalui operasi baris elementer dan operasi transpose. Dari definisi Re s( f , g ) , yang diberikan Sylvester, ukuran matriks yang berkaitan dengan Re s( f , g ) adalah n  m  n  m , sehingga dalam perhitungan Re s( f , g ) sangatlah tidak menyenangkan. Begitu pula apabila dihitung dengan bantuan komputer, tidak efisien. Dengan bantuan matriks Hankel ukuran matriks yang digunakan untuk menghitung resultan dua polinomial menjadi lebih kecil, yaitu mak(n,m) x mak(n,m). Dari Definisi 1 dan mengingat koefisien dari polinomial dapat dihubungkan dengan elemen-elemen dari matriks M nxn (F ) , dapat ditunjukkan adanya relasi

Pn ( F )  M nxn ( F ) . Beberapa metode untuk menghitung resultan tersebut menimbulkan relasi yang memenuhi definisi f-map (Orzech, 1983), yang akan dijelaskan berikut ini.

74


f-MAP Misalkan F adalah suatu field, Pn himpunan polinomial di dalam F [x] dengan derajat kurang atau sama dengan n-1 dan Mn(F) adalah himpunan matriks berukuran nxn atas F. Definisi 2 (Griffiths,1981) Diberikan polinomial f berderajat n di dalam F[x]. Fungsi  : Pn  M n disebut f-map apabila memenuhi : 1.  (1) matriks invertible 2.  ( g  c)   ( g )  c (1) , g  Pn , c  F 3. jika f dan g memiliki faktor non-trivial, maka  (g ) matriks tidak invertible Berikut ini adalah beberapa sifat dari f-map yang akan digunakan pada pembuktian selanjutnya. Misalkan f(x) dan g(x) seperti dalam (5) dengan m  n 1 dan f(x) memiliki akar-akar yang berbeda 1, 2, …, n, serta g(x) memiliki akar-akar yang berbeda 1, 2 , …,m, yakni :

f ( x )  a n ( x  1 )( x   2 ) ( x   n )   g( x )  b m ( x  1 )( x   2 ) ( x   m )  Didefinisikan : F  f ( 1 ) f (  2 )  f (  m ) ,

(9)

G  g (1 ) g ( 2 )  g ( n )

Hubungan antara F dan G tertuang dalam lemma berikut: Lemma 3

G   bmn ( i   j ) ij

(1) nm bmn F  a nm G Bukti : Dari persamaan (9) diperoleh :

g (1 )  bm (1  1 )(1   2 )(1   m ) g ( 2 )  bm ( 2  1 )( 2   2 ) ( 2   m )




75

g ( n )  bm ( n  1 )( n   2 )( n   m ) , sehingga diperoleh

G   bmn ( i   j ) ij

Secara analog untuk F, diperoleh :

(1) nm bmn F  a nm G Proposisi 4 Jika f memiliki n akar yang berbeda, maka untuk setiap f-map  : Pn  M n , berlaku: det ( g )  det 1G = det  1 1

mn

bmn F anm

Bukti: Karena  merupakan f-map, berarti  (1) 1 ada. Jika  1 akar f, maka sebarang polinomial g(x) – g( i) memiliki akar  i. Apabila f(x) dan g(x) seperti dalam (5), maka diperoleh :



 



g ( x)  g ( i )  bm x m  bm 1 x m 1  b1 x  bm im  bm 1 im 1  b1 i . Karena f(x) dan g(x) – g( i) memiliki akar non-trivial maka :

det  g ( x)  g ( i )   0 , det  ( g ( x))  g ( i ) (1)  0 ,

   det  (1) (1)  ( g ( x))  g ( ) I   0 , det  (1)  det  (1)  ( g ( x))  g ( ) I   0 , det  (1) (1) 1  ( g ( x))  g ( i ) (1)  0 , 1

i

n

1

i

n

Karena det (1)  0, diperoleh :





det  (1) 1 ( g ( x))  g ( i ) I n  0 , dan

detW  g ( i ) I n   0 , dengan W   (1) 1 ( g ( x)) . Dari persamaan di atas g( i) merupakan nilai eigen W.

76


Karena diasumsikan terdapat n akar f yang berbeda berarti terdapat g( i), i= 1, 2, …, n, yang merupakan nilai eigen W, sehingga nilai determinan W adalah :

det(W )  g (1 ) g ( 2 )  g ( n ) . Di sisi lain, W   (1) 1 ( g ( x)) , sehingga nilai determinan W adalah :

  = det  (1) det  ( g )  , sehingga

det W   det  (1) 1 ( g ) 1

det  ( g )  

det W  det  (1) 1





= det  (1)  det W   det  (1) g (1 ) g ( 2 )  g ( n )  = det (1)G . Dengan Lemma 3 diperoleh :

det g  = det  1 1

mn

bmn F  anm

Kaitan antara akar-akar polinomial dengan resultan tertuang dalam teorema berikut, dimana pembuktian secara lengkap terdapat dalam Prasolov (1994:188189). Teorema 5 Diberikan polinomial f dan g seperti pada (9), yang memiliki akar-akar berturut-turut i dan j, maka Res(f,g) = anm  g  i   bmn f  j

  

Matriks Hankel Pada bagian ini akan dibahas mengenai pengertian matriks Hankel dan teorema yang berkenaan dengan matriks Hankel, yang akan digunakan pada pembuktian selanjutnya, serta kaitan antara matriks Hankel dengan f-map


77

Definisi 6

s0 s 1 Misalkan s0 , s1 , s 2 , s3 , , barisan bilangan. Matriks  s2  

s1 s2 s3 

s2 s3 s4 

    

yang berkoresponden dengan Hankel form disebut matriks Hankel Teorema 7 Untuk setiap sq, q=r, r+1, r+2, … terdapat 1, 2 , …, r, sehingga r

s q   g s q  g g 1

jika dan hanya jika matriks tak berhingga [H]  si  k 0



memiliki rank berhingga r. Berikut akan dibahas hubungan antara matriks Hankel dengan fungsi rasional. Misalkan F adalah suatu field, f dan g adalah dua polinomial dalam F [x] yang berturut-turut berderajat n dan m; dengan m
f ( x)  a n x n  a n 1 x n 1  a n 2 x n2    a0 , a n  0 g ( x)  bm x m  a m1 x m1  a m2 x m2    b0 Diberikan R( x) 

  

(10)

g ( x) . Apabila R(x) dinyatakan sebagai polinomial pangkat f ( x)

negatif dalam x maka diperoleh :

R( x) 

s0 s1 s 2    . x x2 x3

Dengan mengalikan kedua sisi dengan f(x) diperoleh hubungan sebagai berikut

a x n

n

s s s   a n 1 x n 1    a0   0  12  23    bn 1 x n 1  bn 2 x n 2    b0 x  x x 

Dalam sistem persamaan dapat dinyatakan sebagai berikut :

78


a n s 0  bn 1

      

a n s1  a n 1 s 0  bn  2 a n s 2  a n 1 s1  a n  2 s 0  bn 3  a n s n 1  a n 1 s n  2    a 2 s1  a 1 s9  b0 untuk setiap q  n

an sq  an 1sq 1    a1sq  n 1  a0 sq  n  0 Lebih jauh untuk setiap q  n

sq  1sq 1 2 sq  2     n sq  n , dengan  i 

 ai an

atau r

s q   g s q  g g 1

Apabila barisan s0 , s1 , s 2 , s3 ,

dibentuk matriks Hankel, maka berdasarkan

Teorema 1 matriks Hankel tak berhingga H   si  k 0 memiliki rank berhingga  n yaitu : 

 s0 s  1 [H] =  s 2     s n 1

s1 s2 s3  sn

s2 s3 s4  s n 1

s n 1  s n  s n 1      s 2 n  2    

Diketahui f dan g seperti dalam (9)

g ( x) s0 s1 s2     f ( x) x x 2 x 3 Didefinisikan pemetaan  f (.) : Pn  M n dengan definisi :


79

 s0 s  1  f ( g )   s2     s n 1

s1 s2 s3  sn

s2 s3 s4  s n 1

s n 1  s n  s n 1      s 2 n 2    

Akan ditunjukkan  f memenuhi definisi f-map sebagai berikut Bukti : 1.

r r r 1 1   0  12  23   n n 1 f ( x) an x  an1 x    a1 x  a0 x x x 0    f 1   0 1  an



0

0 

1 an

 an 1 an2

det( f (1))   1 2.

 g ( x)  c   f ( x)

=

  an2     *  

1 an  an 1

  n ( n 1) 2

n

 1    0  an 

g ( x) c  f ( x) f ( x)  1  g ( x)   c f ( x)  f ( x)  r r  s0 s1 s 2  r   2  3    c 0  12  23   x x  x x  x x 

=

Jadi  f g  c    f g   c f 1 3.

80

g ( x) s0 s1 s2     f ( x) x x 2 x 3


 s0 s  1  f ( g )   s2     s n 1

s1 s2 s3  sn

s2 s3 s4  s n 1

s n 1  s n  s n 1      s 2 n 2    

Berdasarkan Teorema 1 rank  f g  adalah  n Diketahui f dan g memiliki akar y m , akan ditunjukkan rank  f g  adalah

 n 1 g ( x)  bm ( x  y1 )( x  y 2 )( x  y m1 )( x  y m ) f ( x)  an ( x  x1 )( x  x2 ) ( x  xn1 )( x  y m )

g ( x) bm ( x  y1 )( x  y 2 )( x  y m1 )( x  y m )  f ( x) an ( x  x1 )( x  x2 ) ( x  xn1 )( x  y m ) diperoleh :

g ( x) bm ( x  y1 )( x  y 2 )( x  y m1 )  f ( x) an ( x  x1 )( x  x2 )( x  xn1 ) Berdasar Teorema 1 rank  f g  adalah  n  1, yang berarti banyaknya baris (kolom) yang bebas linier tidak lebih dari n-1, sehingga nilai adalah 0. Dengan kata lain  f g  adalah matriks tidak invertible.

det  f g  

Resultan Dua Polinomial Dan Matriks Hankel Matriks Hankel [H] adalah matriks representasi dari pemetaan  f g  yang memenuhi definisi f-map. Dengan melihat definisi dan sifat dari f-map kita dapat memanfaatkan matriks Hankel ini untuk menghitung resultan dua polinomial. Hubungan antara resultan dua polinomial dengan matriks Hankel tertuang dalam proposisi berikut Teorema 8 Re s f , g    1

n ( n 1) 2

a nn m det f ( g ) 

Bukti :


81

Karena  f g  merupakan f-map, berarti proposisi 4 berlaku, serta dengan memanfaatkan Teorema 5 maka diperoleh :

det  f ( g )   det  f (1) G 

det  f ( g )   1

n ( n 1) 2

=  1

n ( n 1) 2

=  1

n ( n 1) 2

=  1

Re s f , g    1

n

 1   G  an   Re s( f , g )  anm 

 1   an

  

n ( n 1) 2

n ( n 1) 2

n

 1   an

nm

Re s f , g 

an( nm) Re s( f , g )

a nn m det  f ( g ) 



Contoh 1 : (Brown, 1996) Diketahui F=R, f ( x)  2 x 3  5 x 2  x  2 dan g ( x)  x 2  3x  2 . Akan dicari resultan polinomial f(x) dan g(x) sebagai berikut. (a) Dengan menggunakan definisi resultan atau metode Sylvester :

2 2  5 1 0 2  5 1  Re s f , g   det 1  3 2 0  0 1  3 2 0 0 1 3

0 2 0  0 2

Re s f , g   0 (b) Dengan menggunakan metode matriks Hankel :

s s s s s g x  x 2  3x  2  3  0  12  23  34  45 2 f x  2 x  5 x  x  2 x x x x x

82


2s0  1 2 s1  5s 0  3 2 s 2  5s1  s 0  2 2 s3  5s 2  s1  2 s 0  0 2 s 4  5s3  s 2  2 s1  0 Diperoleh

s0 

1 2

s1 

1 4

 12  f g   H    41  18

s2  1 4 1 8 1 16

1 8 1 8 1 16 1 32

s3 

1 16

:

s4 

1 32

   

detH   0 Re s( f , g )   1

n ( n 1) 2

2 n  m detH   2 5 detH  = 2 5  0  0

Contoh 2 : Diketahui F=R, f ( x)  x 4  3x 3  2 x 2  3x  4 dan g ( x)  x 3  2 x 2  2 x  1 . Akan dicari resultan polinomial f(x) dan g(x) sebagai berikut : (a) Dengan menggunakan definisi resultan atau metode Sylvester :

3 4 0 0 1  3 2 0 1  3 2 3  4 0   0 0 1 3 2 3  4   Re s f , g   det 1  2 2  1 0 0 0  = -13 0 1  2 2  1 0 0   1  2 2 1 0  0 0 0 0 0 1  2 2  1  (b) Dengan menggunakan metode matriks Hankel

s s s s s s s g x  2 x 3  5x 2  4 x  3  4  0  12  23  34  45  56  67 3 2 f x  5x  6 x  7 x  6 x  8 x x x x x x x Diperoleh :


83

s0  1 s1  3s 0  2 s 2  3s1  2s 0  2 s3  3s 2  2s1  3s 0  1 s 4  3s3  2s 2  3s1  4s 0  0 s5  3s 4  2s3  3s 2  4s1  0 s 6  3s5  2s 4  3s3  4s 2  0 s0=1

s1=1

s2=3

s3=3

s4=4

s5=1

s6=-2

Diperoleh matriks :

1 1 H  3  3

1 3 3 4

3 3 3 4  4 1   1  2

detH   13 Re s( f , g )   1

n ( n 1) 2

1n  m detH   detH  = -13

Kesimpulan Ukuran matrik yang digunakan dalam perhitungan resultan dua polinomial dengan menggunakan matriks Hankel lebih kecil dibanding dengan metode Sylvester yaitu maksimum dari derajat polinomial f dan g, sehingga akan mempermudah dalam proses perhitungannya. Apabila [H] adalah matriks Hankel yang

berkenaan

Re s(f , g)   1

84

n ( n 1) 2

dengan

fungsi

rasional

g f

maka

a nn m detH .


Daftar Pustaka Brown, W.C. (1993) Matrices Over Commutative Rings, Marcel Dekker Inc, New York Griffiths, H.B. (1981) Cayley’s Version of Resultan of Two Polynomials, Amer. Math. Monthy, Vol 88, pp 328-338. Hartwig, R.E. (1972) The Resultans and The Solutions AX-XB = C, SIAM. J. Appl. Math, 22:538-544 Ma, E.C. (1966) A finite Series Solutions of Matrix Equation AX_XB = C. SIAM. J. Appl. Math, 28 : 490-495. Orzech, G. (1994) Several Version of Resultant of Two Polynomial, Linear and Multilinear Algebra, Vol 16, pp 275-282. Prasolov, V.V. (1994) Problem and Theorems in Linear Algebra. American Mathematical Society, Provindence, R.I. Van der Waerden, B.L. (1953) Modern Algebra, Vol 1, Prederikck Ungar, New York.


85

Jurnal Pengajaran MIPA, Vol. 3 No. 1 Juni 2002

Recommend Documents