# WORKSHEET#13
#
--------------------------------------------------------------------------------
# RESULTANTS OF POLYNOMIALS
--------------------------------------------------------------------------------
#
> F:=x^4-x-1;G:=x^3+3*x+1;
4
F := x - x - 1
3
G := x + 3 x + 1
--------------------------------------------------------------------------------
> resultant(F,G,x);
-59
--------------------------------------------------------------------------------
# Recall that the resultant of 2 polynomials
# F(x)=ax^m+lower order terms, G(x)=bx^n+lower order terms
# is defined by
# resultant(F,G,x)=(a^n)*(b^m)*product(r[i]-s[j]),
# where the roots of F(x) are r[1],...,r[m], the roots of G(x) are s[1],...,s[n], and the product is
# taken over all possible differences r[i]-s[j]. Thus there are mn terms in the product.
--------------------------------------------------------------------------------
> r:=fsolve(F,x,complex); s:=fsolve(G,x,complex);
r := -.7244919590, - .2481260628 - 1.033982061 I,
- .2481260628 + 1.033982061 I, 1.220744085
s := -.3221853546, .1610926773 - 1.754380960 I, .1610926773 + 1.754380960 I
--------------------------------------------------------------------------------
# Now we compute the product of all possible differences r[i]-s[j].
--------------------------------------------------------------------------------
#
> P:=1: for i from 1 to 4 do for j from 1 to 3 do P:=P*(r[i]-s[j]) od:od:
--------------------------------------------------------------------------------
> P;
-8
- 59.00000010 + .985708112*10 I
--------------------------------------------------------------------------------
# This gives the same answer to within numerical error. There are other ways of looking at
# the resultant. It will be convenient to change F and G into functions rather than
# expressions.
--------------------------------------------------------------------------------
> F:=x->x^4-x-1;G:=x->x^3+3*x+1;
4
F := x -> x - x - 1
3
G := x -> x + 3 x + 1
--------------------------------------------------------------------------------
> P:=1.: for i from 1 to 4 do P:=P*G(r[i]) od:
--------------------------------------------------------------------------------
> P;
-8
- 59.00000003 + .6253945832*10 I
--------------------------------------------------------------------------------
# To within numerical error this is the same answer. Another way to compute the
# resultant is as follows.
--------------------------------------------------------------------------------
> product(G(t),t=rootof(F(x)));
Error, (in product)
second argument must be a name or name=a..b or name=RootOf
--------------------------------------------------------------------------------
> product(G(t),t=Rootof(F(x)));
Error, (in product)
second argument must be a name or name=a..b or name=RootOf
--------------------------------------------------------------------------------
> ?product
--------------------------------------------------------------------------------
> product(G(t),t=RootOf(F(x)));
-59
--------------------------------------------------------------------------------
#
> product(F(t),t=RootOf(G(x)));
-59
--------------------------------------------------------------------------------
#
# Maple is very case sensitive! We have obtained the same answer, to within numerical
# error, in several different ways. You should be able to verify this. In general for
# polynomials
#
# F(x)=ax^m+lower order terms, G(x)=bx^n+lower order terms
# we have
# resultant(F,G,x)=(a^n)(b^m)*product(G(r[i]))=
# (-1)^{mn}*(a^n)(b^m)*product(F(s[j])
# where the roots of F(x) are r[1],...,r[m], the roots of G(x) are s[1],...,s[n].
--------------------------------------------------------------------------------
> resultant(x^3+3*x+1,x^5-x^2-1,x);
-339
--------------------------------------------------------------------------------
> resultant(x^5-x^2-1,x^3+3*x+1,x);
339
--------------------------------------------------------------------------------
# What is crucial is that the resultant can be computed from the coefficients of the
# polynomials, we do not need to know the roots. Observe also that the resultant is 0 if, and
# only if, the polynomials have a common root.
#
# The same considerations apply to polynomials in several variables. The definition of the
# resultant of 2 polynomials f(x,y) and g(x,y) is given in terms of the roots.
--------------------------------------------------------------------------------
> f:=x^4-x*y^2-y^5-3;g:=x^2*y^3+x*y^2-y^3-3;
4 2 5
f := x - x y - y - 3
2 3 2 3
g := x y + x y - y - 3
--------------------------------------------------------------------------------
# Now there are 2 possible resultants because we can think of f(x,y) and g(x,y) as
# polynomials in x with coefficients which are polynomials in y, or the other way around.
--------------------------------------------------------------------------------
> h:=resultant(f,g,x);
22 18 17 16 15 14 13 12 11 10
h := y - y + 4 y - y - 4 y - 12 y - 10 y - 8 y - 19 y - 30 y
9 8 7 3
- 24 y - 6 y - 63 y + 108 y + 81
--------------------------------------------------------------------------------
> k:=resultant(f,g,y);
22 20 18 17 16 15 14 13 12
k := - x + 5 x - x + x - 35 x - 3 x + 73 x - 10 x + 16 x
11 10 9 8 7 6 5 4
+ 35 x - 336 x + 12 x + 432 x - 231 x + 387 x + 207 x - 1053 x
3 2
+ 612 x + 540 x - 648 x + 216
--------------------------------------------------------------------------------
# The resultant has eliminated the x variable in the first case and y in the second.
--------------------------------------------------------------------------------
> f1:=subs(y=2,f);g1:=subs(y=2,g);
4
f1 := x - 4 x - 35
2
g1 := 8 x + 4 x - 11
--------------------------------------------------------------------------------
> resultant(f1,g1,x);
3857969
--------------------------------------------------------------------------------
> subs(y=2,h);
3857969
--------------------------------------------------------------------------------
# If h(d)=0 for some value of d then resultant(f(x,d),g(x,d),x)=0 and so the polynomials
# f(x,d) and g(x,d) have a common root c. In other words we have found a solution (c,d) of
# the simultaneous equations f(x,y)=0, g(x,y)=0. Actually there is a subtle point here. The
# resultant involves the leading coefficients so that if they vanish we might not have a
# common root.
#
# There is an important formula for the resultant, called Sylvester's formula, which
# determines the resultant in terms of the coefficients of the polynomials.
--------------------------------------------------------------------------------
> i:='i':A:=sum(a[i]*x^(5-i),i=0..5);
5 4 3 2
A := a[0] x + a[1] x + a[2] x + a[3] x + a[4] x + a[5]
--------------------------------------------------------------------------------
> j:='j':B:=sum(b[j]*x^(4-j),j=0..4);
4 3 2
B := b[0] x + b[1] x + b[2] x + b[3] x + b[4]
--------------------------------------------------------------------------------
> with(linalg);
Warning: new definition for norm
Warning: new definition for trace
[BlockDiagonal, GramSchmidt, JordanBlock, Wronskian, add, addcol, addrow, adj,
adjoint, angle, augment, backsub, band, basis, bezout, blockmatrix,
charmat, charpoly, col, coldim, colspace, colspan, companion, concat, cond,
copyinto, crossprod, curl, definite, delcols, delrows, det, diag, diverge,
dotprod, eigenvals, eigenvects, entermatrix, equal, exponential, extend,
ffgausselim, fibonacci, frobenius, gausselim, gaussjord, genmatrix, grad,
hadamard, hermite, hessian, hilbert, htranspose, ihermite, indexfunc,
innerprod, intbasis, inverse, ismith, iszero, jacobian, jordan, kernel,
laplacian, leastsqrs, linsolve, matrix, minor, minpoly, mulcol, mulrow,
multiply, norm, normalize, nullspace, orthog, permanent, pivot, potential,
randmatrix, randvector, rank, ratform, row, rowdim, rowspace, rowspan,
rref, scalarmul, singularvals, smith, stack, submatrix, subvector,
sumbasis, swapcol, swaprow, sylvester, toeplitz, trace, transpose,
vandermonde, vecpotent, vectdim, vector]
--------------------------------------------------------------------------------
> sylvester(A,B,x);
[ a[0] a[1] a[2] a[3] a[4] a[5] 0 0 0 ]
[ ]
[ 0 a[0] a[1] a[2] a[3] a[4] a[5] 0 0 ]
[ ]
[ 0 0 a[0] a[1] a[2] a[3] a[4] a[5] 0 ]
[ ]
[ 0 0 0 a[0] a[1] a[2] a[3] a[4] a[5] ]
[ ]
[ b[0] b[1] b[2] b[3] b[4] 0 0 0 0 ]
[ ]
[ 0 b[0] b[1] b[2] b[3] b[4] 0 0 0 ]
[ ]
[ 0 0 b[0] b[1] b[2] b[3] b[4] 0 0 ]
[ ]
[ 0 0 0 b[0] b[1] b[2] b[3] b[4] 0 ]
[ ]
[ 0 0 0 0 b[0] b[1] b[2] b[3] b[4] ]
--------------------------------------------------------------------------------
> F(x);G(x);
4
x - x - 1
3
x + 3 x + 1
--------------------------------------------------------------------------------
> sylvester(F(x),G(x));
Error, (in sylvester) sylvester uses a 3rd argument, x (of type
name), which is missing
--------------------------------------------------------------------------------
> sylvester(F(x),G(x),x);
[ 1 0 0 -1 -1 0 0 ]
[ ]
[ 0 1 0 0 -1 -1 0 ]
[ ]
[ 0 0 1 0 0 -1 -1 ]
[ ]
[ 1 0 3 1 0 0 0 ]
[ ]
[ 0 1 0 3 1 0 0 ]
[ ]
[ 0 0 1 0 3 1 0 ]
[ ]
[ 0 0 0 1 0 3 1 ]
--------------------------------------------------------------------------------
> det(");
-59
--------------------------------------------------------------------------------
# The point here is that the resultant is the determinant of the Sylvester matrix.
--------------------------------------------------------------------------------
> ?sylvester
--------------------------------------------------------------------------------
> f:=x^4-x*y^2-y^5-3;g:=x^2*y^3+x*y^2-y^3-3;
4 2 5
f := x - x y - y - 3
2 3 2 3
g := x y + x y - y - 3
--------------------------------------------------------------------------------
> solve({f,g},{x,y});
{y = %1,
2319213 23317959 115447417 11 38401727 6 13203201 4
x = - -------- - -------- %1 + --------- %1 + --------- %1 - -------- %1
14395816 14395816 388687032 129562344 14395816
2139235 3 768785 18 77605 17 1694893 16
- -------- %1 - -------- %1 - -------- %1 + -------- %1
14395816 43187448 16195293 97171758
21443449 15 20806297 14 32242807 13 44473225 12
- --------- %1 + --------- %1 + --------- %1 + --------- %1
388687032 388687032 388687032 129562344
40317707 10 89821199 9 5660803 8 12167002 7 48723071 5
+ -------- %1 + --------- %1 + ------- %1 + -------- %1 + -------- %1
97171758 194343516 7197908 16195293 43187448
7037085 2 88657 21 661913 19 8244433 20
- -------- %1 - --------- %1 - --------- %1 - --------- %1
14395816 129562344 129562344 388687032
}
22 18 17 16 15 14 13 12
%1 := RootOf(_Z - _Z + 4 _Z - _Z - 4 _Z - 12 _Z - 10 _Z - 8 _Z
11 10 9 8 7 3
- 19 _Z - 30 _Z - 24 _Z - 6 _Z - 63 _Z + 108 _Z + 81)
--------------------------------------------------------------------------------
# The simultaneous solutions of f(x,y)=0 and g(x,y)=0 are given above; y is the root of a
# certain polynomial of degree 22 and x is determined as a function of y.
--------------------------------------------------------------------------------
> h:='h':
> h:=resultant(f,g,x);
22 18 17 16 15 14 13 12 11 10
h := y - y + 4 y - y - 4 y - 12 y - 10 y - 8 y - 19 y - 30 y
9 8 7 3
- 24 y - 6 y - 63 y + 108 y + 81
--------------------------------------------------------------------------------
