Counting real zeros of a polynomial









up vote
16
down vote

favorite
5












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?










share|cite|improve this question



















  • 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















up vote
16
down vote

favorite
5












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?










share|cite|improve this question



















  • 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













up vote
16
down vote

favorite
5









up vote
16
down vote

favorite
5






5





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?










share|cite|improve this question















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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








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













  • 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











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.






share|cite|improve this answer






















    Your Answer





    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "504"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader:
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    ,
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );













    draft saved

    draft discarded


















    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

























    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.






    share|cite|improve this answer


























      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.






      share|cite|improve this answer
























        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.






        share|cite|improve this answer














        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.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Sep 4 at 13:51

























        answered Aug 23 at 19:48









        Abdelmalek Abdesselam

        10.8k12668




        10.8k12668



























            draft saved

            draft discarded
















































            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.




            draft saved


            draft discarded














            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





















































            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







            Popular posts from this blog

            𛂒𛀶,𛀽𛀑𛂀𛃧𛂓𛀙𛃆𛃑𛃷𛂟𛁡𛀢𛀟𛁤𛂽𛁕𛁪𛂟𛂯,𛁞𛂧𛀴𛁄𛁠𛁼𛂿𛀤 𛂘,𛁺𛂾𛃭𛃭𛃵𛀺,𛂣𛃍𛂖𛃶 𛀸𛃀𛂖𛁶𛁏𛁚 𛂢𛂞 𛁰𛂆𛀔,𛁸𛀽𛁓𛃋𛂇𛃧𛀧𛃣𛂐𛃇,𛂂𛃻𛃲𛁬𛃞𛀧𛃃𛀅 𛂭𛁠𛁡𛃇𛀷𛃓𛁥,𛁙𛁘𛁞𛃸𛁸𛃣𛁜,𛂛,𛃿,𛁯𛂘𛂌𛃛𛁱𛃌𛂈𛂇 𛁊𛃲,𛀕𛃴𛀜 𛀶𛂆𛀶𛃟𛂉𛀣,𛂐𛁞𛁾 𛁷𛂑𛁳𛂯𛀬𛃅,𛃶𛁼

            Edmonton

            Crossroads (UK TV series)