prove: deg(gcd(p,q))=nullity(sylvester(p,q)) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Computation - 科学计算

prove: deg(gcd(p,q))=nullity(sylvester(p,q))

prove: deg(gcd(p,q))=nullity(sylvester(p,q))# Computation - 科学计算

g*i2003-05-15 07:05

1 楼

i want to show that, for two univariate polynomials p, q
deg(gcd(p,q))=nullity(sylvester(p,q))
here sylvester(p,q) is the sylvester matrix of the coefficients
of p and q.
thanks.

y*t2003-05-15 07:05

2 楼

assume deg(p)=m, deg(q)=n, deg(gcd(p,q))=d, let g=gcd(p,q)
let polynomial r has deg n-1 and s has deg m-1
the solution rp+sq=0 provides a null vector of the sylvester matrix A
(the coefficients of r and s)
in fact any deg d-1 polynomial f will provide a solution
r=fq/g, s=fp/g, thus the nullity of A is at least d
conversely, if (r,s) is a null vector, then rp should
be a multiple of lcm(p,q)=pq/g so that q/g | r thus the nullity
of A is at most d. done

【在 g***i 的大作中提到】

: i want to show that, for two univariate polynomials p, q
: deg(gcd(p,q))=nullity(sylvester(p,q))
: here sylvester(p,q) is the sylvester matrix of the coefficients
: of p and q.
: thanks.

g*i2003-05-15 07:05

3 楼

thanks a lot. this helps greatly.

here one of them has "-", right?
so if i understand correctly,
here it means deg(r) is in [n-d,n-1], i.e. it had d choices.

【在 y**t 的大作中提到】

: assume deg(p)=m, deg(q)=n, deg(gcd(p,q))=d, let g=gcd(p,q)
: let polynomial r has deg n-1 and s has deg m-1
: the solution rp+sq=0 provides a null vector of the sylvester matrix A
: (the coefficients of r and s)
: in fact any deg d-1 polynomial f will provide a solution
: r=fq/g, s=fp/g, thus the nullity of A is at least d
: conversely, if (r,s) is a null vector, then rp should
: be a multiple of lcm(p,q)=pq/g so that q/g | r thus the nullity
: of A is at most d. done

y*t2003-05-15 07:05

4 楼

you are right

【在 g***i 的大作中提到】

: thanks a lot. this helps greatly.
:
: here one of them has "-", right?
: so if i understand correctly,
: here it means deg(r) is in [n-d,n-1], i.e. it had d choices.

g*i2003-05-15 07:05

5 楼

I have considered to use Gaussian elimination on the syl matrix.
Say, if the syl matrix is in the form that each row are the
coefficients of the polynomials, then apply GE to the rows.
The last nonzero row has the coefficients of the gcd.
Thus I tried to prove the reduced matrix has nonzero diagonal
entry in the last nonzero row. But I can't find a way to
prove this:( Any idea?

【在 y**t 的大作中提到】

: you are right