Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a multivariate polynomial $p(x_1,\ldots,x_n)$ and I wish to check if it is positive semidefinite over $R^n$. I can always choose any direction $\vec{v}$ and check that the univariate polynomial $q(x) = p( x\vec{v})$ is positive semidefinite. Imagine sampling $\vec{v}$ and testing. Univariate polynomials are easy to test for p.s.d. If I get lucky and a direction fails the univariate test, I can conclude that $p$ is not positive semidefinite.

Question is whether there is any known result in this space that will allow me to conclude that the polynomial is positive semidefinite after testing finitely many directions?

My motivation: I am looking for a randomized algorithm for positive semidefiniteness testing much like the identity testing algorithm that is based on Schwarz Zippel Lemma.

thanks, Sriram

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.