# What do we know about checking real-stability of multivariate complex polynomials?

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 ?

• 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..

• You might want to check out the Routh-Hurwitz stability criterion. May 21 '15 at 3:07
• @Hsien-ChihChang張顯之 it's simpler than that in the single variable case. a univariate real polynomial is stable if and only if it's real rooted, which can be tested with Sturm's theorem en.wikipedia.org/wiki/Sturm%27s_theorem May 21 '15 at 8:27

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}$...