Suppose we have a system of linear and quadratic equations with rational coefficients and we want to find out whether this system has a real solution or not. The actual values of a solution is not important.

To be specific, let $D\in \mathbb{Q}^{m\times n}$, $Q_1,\ldots,Q_r \in \mathbb{Q}^{n\times n}$, and $c_1,\ldots c_r\in \mathbb{Q}$. Our goal is to determine whether there is an $x\in \mathbb{R}^n$ such that: $$Dx=0,$$ $$x^TQ_1x=c_1,\ldots,x^TQ_rx=c_r.$$

So my Question is this: is there a polynomial time algorithm to determine the existence of a real solution? Or better than that, is there a simple condition on the matrices $D,Q_1,\ldots,Q_r$ and the scalars $c_1,\ldots,c_r$ that is equivalent to the existence of a real solution?

Note that the existence of a complex solution can be checked by computing a groebner basis for the relevant ideal and checking that this ideal is not the entire polynomial ring (by weak Nullstellensatz). But in real case, I'm not aware of any way of algorithmically solve the problem (using real nullstellensatz for example).

(Existence of a real-valued solution to system of multivariate polynomial equations and its answer is relevant, but because of the lack of knowledge in algebraic geometry, I'm looking for a more specific answer.)


The answer is yes, in principle, and this is explained in the reference that you cite. But a "simple" criterion probably does not exist. The state of the art is described in this book Sottile, Frank Real solutions to equations from geometry. American Mathematical Society, Providence, RI, 2011.

  • $\begingroup$ Thanks for the book. Does this mean that even in this (seemingly) simple special case ("Does a linear subspace intersect a nice quadratic manifold?") there isn't a simple solution? $\endgroup$ – Ghodrati Oct 8 '15 at 16:43
  • 1
    $\begingroup$ Yes. A system of quadratic equations is not simpler that a system of arbitrary degree equations (if you do not count how many variables). Most equations in this book are in fact quadratic. $\endgroup$ – Alexandre Eremenko Oct 8 '15 at 19:34

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.