8
$\begingroup$

Given a polynomial $p : \mathbb{C}^n \rightarrow \mathbb{C}$ it is to be called "real-stable" if (1) all its coefficients are real and (2) if it has no roots such that all the coordinates of the root have a positive imaginary part.

[..clearly if $n=1$ then the polynomial being real-stable is the same as the polynomial being real-rooted..]

Q1 Do we know of any method to check for real stability of a polynomial?

Q2 Even if not a general solution but can one at least be able to check this property on some specific polynomial via some commands on SAGE or Mathematica ?

Q3 Is any hardness result known about this when thought of as a decision question?

  • If necessary feel free to assume that the polynomial is homogeneous. May be if thinking about the associated projective variety helps...

  • May be you can just choose some specific value of $n$ or the degree of the polynomial if you think that the questions are answerable easier for those values. (like $n=1$ and degree $\leq 5$ are the trivial cases)

  • A generic example of a real-stable polynomial is $p(z,t_1,..,t_n) = det(zI + \sum_{i=1}^{n} t_i B_i)$ where $B_i$ are positive-semi-definite matrices. Now we know that real-stability of a polynomial is preserved under operations like acting by differential operators like $(1+ a \frac{\partial }{\partial x})$ (where $x$ is one of the domain variables of the polynomial and $a \in \mathbb{R}$) or setting any of the variables to a real-number or taking a product of two real-stable polynomials. Now one obvious way to try to decide if a polynomial is real-stable or not is to see if it can be obtained via doing any combination of these real-stability preserving operations on some other polynomial which is known to be real-stable.

But I am wondering if any direct method (algorithm) exists..

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
6
$\begingroup$

Here is at least some upper bound: treat the polynomial $\mathbb{C}^n \to \mathbb{C}$ as $\mathbb{R}^{2n} \to \mathbb{R}^2$, and then ask in the first order theory of the reals if $p(x)=0$ implies that the imaginary part of each coordinate of $x$ is nonpositive. This can be solved in $\mathsf{PSPACE}$ (e.g. http://en.wikipedia.org/wiki/Existential_theory_of_the_reals).

Of course, the existential theory of the reals is $\mathsf{NP}$-hard, so taking this route in general won't get you below $\mathsf{NP}$...

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the insights. But is there even a brute-force way of checking this property? $\endgroup$
    – Student
    May 26, 2015 at 8:15
  • 1
    $\begingroup$ This essentially is the brute force way. $\endgroup$
    – Joshua Grochow
    May 26, 2015 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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