Counting real zeros of a polynomial
up vote
16
down vote
favorite
I recently came across a criteria to count the number of real zeros of a polynomial $P(x)$ with real coefficients. Unfortunately I cannot find the reference! The criteria is the following: Form the matrix M whose entry $M_i,j$ (with $0leq i,jleq deg(p)-1$) is the coefficient of $X^iY^j$ in the polynomial $$fracP(X)P'(Y)-P(Y)P'(X)X-Y.$$
Then all of the roots of $P$ are real if and only if $M$ is positive semi-definite. Moreover the roots are all distinct if $M$ is positive definite.
This is clearly a variation on Hermite's criteria which says the same thing, but instead of $M$ as above, uses a Hankel matrix $H$ whose entry $H_i,j$ (with $i$ and $j$ in the same range) is the symmetric power polynomial $p_i+j$ in the roots of the polynomial which can be generated from the coefficients of $P$ using the Newton identities.
The first criteria is much better suited for my specific application and I'd like to cite it, but as I said I can't find the reference. I expect the two matrices are similar, and though it's not immediately obvious to me how, I suspect I can reproduce it with a little effort. The more pressing issue is that I'd like to be able to cite whoever originally discovered this simpler formulation.
Does anyone know a reference for this?
ac.commutative-algebra polynomials real-algebraic-geometry elimination-theory
add a comment |
up vote
16
down vote
favorite
I recently came across a criteria to count the number of real zeros of a polynomial $P(x)$ with real coefficients. Unfortunately I cannot find the reference! The criteria is the following: Form the matrix M whose entry $M_i,j$ (with $0leq i,jleq deg(p)-1$) is the coefficient of $X^iY^j$ in the polynomial $$fracP(X)P'(Y)-P(Y)P'(X)X-Y.$$
Then all of the roots of $P$ are real if and only if $M$ is positive semi-definite. Moreover the roots are all distinct if $M$ is positive definite.
This is clearly a variation on Hermite's criteria which says the same thing, but instead of $M$ as above, uses a Hankel matrix $H$ whose entry $H_i,j$ (with $i$ and $j$ in the same range) is the symmetric power polynomial $p_i+j$ in the roots of the polynomial which can be generated from the coefficients of $P$ using the Newton identities.
The first criteria is much better suited for my specific application and I'd like to cite it, but as I said I can't find the reference. I expect the two matrices are similar, and though it's not immediately obvious to me how, I suspect I can reproduce it with a little effort. The more pressing issue is that I'd like to be able to cite whoever originally discovered this simpler formulation.
Does anyone know a reference for this?
ac.commutative-algebra polynomials real-algebraic-geometry elimination-theory
2
I removed the nt.number-theory tag as your question had nothing to do with number theory. Nice question, by the way!
– GH from MO
Aug 23 at 19:02
add a comment |
up vote
16
down vote
favorite
up vote
16
down vote
favorite
I recently came across a criteria to count the number of real zeros of a polynomial $P(x)$ with real coefficients. Unfortunately I cannot find the reference! The criteria is the following: Form the matrix M whose entry $M_i,j$ (with $0leq i,jleq deg(p)-1$) is the coefficient of $X^iY^j$ in the polynomial $$fracP(X)P'(Y)-P(Y)P'(X)X-Y.$$
Then all of the roots of $P$ are real if and only if $M$ is positive semi-definite. Moreover the roots are all distinct if $M$ is positive definite.
This is clearly a variation on Hermite's criteria which says the same thing, but instead of $M$ as above, uses a Hankel matrix $H$ whose entry $H_i,j$ (with $i$ and $j$ in the same range) is the symmetric power polynomial $p_i+j$ in the roots of the polynomial which can be generated from the coefficients of $P$ using the Newton identities.
The first criteria is much better suited for my specific application and I'd like to cite it, but as I said I can't find the reference. I expect the two matrices are similar, and though it's not immediately obvious to me how, I suspect I can reproduce it with a little effort. The more pressing issue is that I'd like to be able to cite whoever originally discovered this simpler formulation.
Does anyone know a reference for this?
ac.commutative-algebra polynomials real-algebraic-geometry elimination-theory
I recently came across a criteria to count the number of real zeros of a polynomial $P(x)$ with real coefficients. Unfortunately I cannot find the reference! The criteria is the following: Form the matrix M whose entry $M_i,j$ (with $0leq i,jleq deg(p)-1$) is the coefficient of $X^iY^j$ in the polynomial $$fracP(X)P'(Y)-P(Y)P'(X)X-Y.$$
Then all of the roots of $P$ are real if and only if $M$ is positive semi-definite. Moreover the roots are all distinct if $M$ is positive definite.
This is clearly a variation on Hermite's criteria which says the same thing, but instead of $M$ as above, uses a Hankel matrix $H$ whose entry $H_i,j$ (with $i$ and $j$ in the same range) is the symmetric power polynomial $p_i+j$ in the roots of the polynomial which can be generated from the coefficients of $P$ using the Newton identities.
The first criteria is much better suited for my specific application and I'd like to cite it, but as I said I can't find the reference. I expect the two matrices are similar, and though it's not immediately obvious to me how, I suspect I can reproduce it with a little effort. The more pressing issue is that I'd like to be able to cite whoever originally discovered this simpler formulation.
Does anyone know a reference for this?
ac.commutative-algebra polynomials real-algebraic-geometry elimination-theory
ac.commutative-algebra polynomials real-algebraic-geometry elimination-theory
edited Aug 23 at 20:38
Abdelmalek Abdesselam
10.8k12668
10.8k12668
asked Aug 23 at 18:32
Michael Griffin
47329
47329
2
I removed the nt.number-theory tag as your question had nothing to do with number theory. Nice question, by the way!
– GH from MO
Aug 23 at 19:02
add a comment |
2
I removed the nt.number-theory tag as your question had nothing to do with number theory. Nice question, by the way!
– GH from MO
Aug 23 at 19:02
2
2
I removed the nt.number-theory tag as your question had nothing to do with number theory. Nice question, by the way!
– GH from MO
Aug 23 at 19:02
I removed the nt.number-theory tag as your question had nothing to do with number theory. Nice question, by the way!
– GH from MO
Aug 23 at 19:02
add a comment |
1 Answer
1
active
oldest
votes
up vote
13
down vote
accepted
By Remark 9.21 page 340 of the book by Basu, Pollack and Roy on real algebraic geometry the matrix $H$ is the expansion of the Bezoutiant of $P$ and $P'$ in the Horner basis of $P$ instead of the basis of usual monomials which is your $M$. The Horner basis is the sequence of polynomials one actually computes when evaluating $P$ by Horner's scheme.
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
13
down vote
accepted
By Remark 9.21 page 340 of the book by Basu, Pollack and Roy on real algebraic geometry the matrix $H$ is the expansion of the Bezoutiant of $P$ and $P'$ in the Horner basis of $P$ instead of the basis of usual monomials which is your $M$. The Horner basis is the sequence of polynomials one actually computes when evaluating $P$ by Horner's scheme.
add a comment |
up vote
13
down vote
accepted
By Remark 9.21 page 340 of the book by Basu, Pollack and Roy on real algebraic geometry the matrix $H$ is the expansion of the Bezoutiant of $P$ and $P'$ in the Horner basis of $P$ instead of the basis of usual monomials which is your $M$. The Horner basis is the sequence of polynomials one actually computes when evaluating $P$ by Horner's scheme.
add a comment |
up vote
13
down vote
accepted
up vote
13
down vote
accepted
By Remark 9.21 page 340 of the book by Basu, Pollack and Roy on real algebraic geometry the matrix $H$ is the expansion of the Bezoutiant of $P$ and $P'$ in the Horner basis of $P$ instead of the basis of usual monomials which is your $M$. The Horner basis is the sequence of polynomials one actually computes when evaluating $P$ by Horner's scheme.
By Remark 9.21 page 340 of the book by Basu, Pollack and Roy on real algebraic geometry the matrix $H$ is the expansion of the Bezoutiant of $P$ and $P'$ in the Horner basis of $P$ instead of the basis of usual monomials which is your $M$. The Horner basis is the sequence of polynomials one actually computes when evaluating $P$ by Horner's scheme.
edited Sep 4 at 13:51
answered Aug 23 at 19:48
Abdelmalek Abdesselam
10.8k12668
10.8k12668
add a comment |
add a comment |
Thanks for contributing an answer to MathOverflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f308989%2fcounting-real-zeros-of-a-polynomial%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
I removed the nt.number-theory tag as your question had nothing to do with number theory. Nice question, by the way!
– GH from MO
Aug 23 at 19:02