{VERSION 3 0 "SGI MIPS UNIX" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "" -1 256 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 256 11 "Resultants." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 70 "Lets assume that f and g are polynomials in x and have no common root." }}{PARA 0 "" 0 " " {TEXT -1 27 "Let s and t be polynomials." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 58 "Then: s*f is divisible by g o nly when s is divible by g." }}{PARA 0 "" 0 "" {TEXT -1 59 "And: t*g is divisible by f only when t is divisible by f." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 11 "Now assume:" }}{PARA 0 " " 0 "" {TEXT -1 29 "degree(s,x) < degree(g,x) and" }}{PARA 0 "" 0 "" {TEXT -1 26 "degree(t.x) < degree(f,x)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "So then: s*f is divisible by g only \+ when s=0." }}{PARA 0 "" 0 "" {TEXT -1 47 "And : t*g is divisible \+ by f only when t=0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 56 "Hence, with these degree conditions on s and t, we have :" }}{PARA 0 "" 0 "" {TEXT -1 42 " (*) s*f + t*g = 0 if and only if \+ s=t=0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 129 "It is easy to see that (*) will be false when gcd(f,g) is not con stant. Because then just take s := g/gcd(f,g), t := -f/gcd(f,g)." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 "Let n=deg ree(f,x)" }}{PARA 0 "" 0 "" {TEXT -1 18 "and m=degree(g,x)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 119 "Let V_n be the vector space of all polynomials in x of degree less than n. The dimen sion of this vector space equals n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 68 "Now (s,t) -> s*f + t*g is a linear map \+ L from V_m * V_n to V_(n+m)." }}{PARA 0 "" 0 "" {TEXT -1 286 "We have \+ seen that: kernel(L) = 0 if and only if f and g have no common factor. Now the transpose of the matrix of this map is called the Sylvester m atrix. So, the determinant of the Sylvester matrix is 0 if and only if kernel(L)<>0, which happens if and only f and g have a common root." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 94 "Now the resultant of f and g is defined as the determinant of the Sylvester m atrix of f and g." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "restar t; with(linalg):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "f:=add( a.i*x^i,i=0..3); g:=add(b.i*x^i,i=0..3);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "sylvester(f,g,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "det(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 " resultant(f,g,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "f:=17* x^5+x^2+x+1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "g:=x^3+2*x^ 2+b1*x+9;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "sylvester(f,g, x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "det(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "R:=resultant(f,g,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "f:=(x-a/(a-1))*(x-1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "g :=(x-1/(1-a))*x;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "f:=nume r(f);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "g:=numer(g);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "factor(resultant(f,g,x));" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "solve(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "subs(a=0,[f,g]); # Two common roots." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "subs(a=-1,[f,g]); # Common r oot x=1/2" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "subs(a=1,[f,g] ); # Common root x=infinity" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "W hat happened in this example is the following:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 382 "f has a root 1/(a-1) and g has a root 1/(1-a) which both become infinity when a=1. So for a=1 \+ the polynomials f and g have a common root x=infinity, and therefore a =1 is a root of the resultant. At a=1 the polynomials f and g are 1-x \+ and x, and don't have a non-trivial gcd. Having a common root infinity should be interpreted as that for a=1 both degrees of f and g have de creased." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 30 "Lets look again at: s*f+t*g=0." }}{PARA 0 "" 0 "" {TEXT -1 15 "n:= degree(f,x);" }}{PARA 0 "" 0 "" {TEXT -1 15 "m:=degree(g,x);" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 75 "and we're looki ng for polynomials s,t of degree " 0 "" {MPLTEXT 1 0 15 "f:=randpoly(x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "g:=randpoly(x);" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 48 "readlib(ifactors): ifactors(resultant(f,g,x));" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "v:=%[2];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "v:=[seq(i[1],i=v)];" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "for p in v do Gcd(f,g) mod p od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 78 "For any other prime number, the polynomia ls f and g will have no common root.." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "f:=-80* x^5+x^3+x+1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "g:=15*x^7+x ^6+x+9;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "resultant(f,g,x) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "v:=ifactors(%);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "v:=[seq(i[1],i=v[2])];" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "for p in v do Gcd(f,g) mod \+ p od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 141 "As we see, the resultan t is 0 modulo 5, and there is a common root (infinity), but no common \+ factor. For all prime numbers that do not divide" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 32 "igcd( lcoeff(f,x), lcoeff (g,x) )" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 81 "we have that Gcd(f,g) mod p is 1 if and only if p does not divide the resultant." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 102 "When p divides igcd( lcoeff(f,x), lcoeff(g,x) ) then we \+ can not be sure if Gcd(f,g) mod p is 1 or not." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 25 "Elimination by resultant." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "Xt := -2*t/(1+t^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 " Yt := (1-t^2)/(1+t^2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "p lot( [Xt, Yt, t=-100..100] );" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 288 "We have two rational functions Xt and Yt in Q(t). Here Q(t) stands fo r all rational functions in t with rational numbers as coefficients. F rom the picture we can clearly see that Xt and Yt are algebraically de pendent. This means that there exist a polynomial P in two variables s uch that:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 13 "P(Xt,Yt) = 0." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 104 "In our example we can easily see in the picture that thi s polynomial is (when we use variables x and y):" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 19 "P(x,y) = x^2+y^2-1." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 107 "How coul d we have computed that? Well, when we substitute x=Xt and y=Yt then t he x^2+y^2-1 should become 0." }}{PARA 0 "" 0 "" {TEXT -1 205 "Another way to say that is when: x-Xt and y-Yt have a common root t=some numb er then x^2+y^2-1 = 0. So we're searching for some expression x^2+y^2- 1 that vanishes whenever x-Xt and y-Yt have a common root." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "Xt;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "Yt;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "x-Xt; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "y-Yt;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "resultant(%,%%,t);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 122 "The sylvester matrix is defined for polynomials in \+ t, not for rational functions. But that's easy to handle, because when :" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 46 "x-Xt and y-Yt have a common root, then so do:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "numer(x-Xt), numer(y-Yt) (num er=numerator)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "numer(x-X t);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "numer(y-Yt);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "resultant(%,%%,t);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "P:=sort(primpart(%));" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "Another example. Lets look at the \+ curve:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 119 "\{ ( t^3+t-3/t , (t+1)/t^3) \} where t runs through the set of \+ all real numbers and infinity. What is the curve we get:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Xt := t^2+t-1/t;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "Yt := (t+1)/t^3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "P:=resultant( numer(x-Xt), numer(y-Yt), t);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "57" 0 } {VIEWOPTS 1 1 0 1 1 1803 }