<p>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. <a href="http://en.wikipedia.org/wiki/Existential_theory_of_the_reals">http://en.wikipedia.org/wiki/Existential_theory_of_the_reals</a>). </p>

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

CC BY-SA 3.0
2015-05-26T08:15:22.630Z
Thanks for the insights. But is there even a brute-force way of checking this property?
Student
CC BY-SA 3.0
2015-05-26T16:49:00.737Z
This essentially *is* the brute force way.
Joshua Grochow
CC BY-SA 3.0
2015-05-24T19:39:39.450Z
2015-05-24T19:39:39.450Z
Joshua Grochow
<p>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. </p>

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

<p><strong>Q1</strong> Do we know of any method to check for real stability of a polynomial? </p>

<p><strong>Q2</strong> 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 ? </p>

<p><strong>Q3</strong> Is any hardness result known about this when thought of as a decision question?  </p>

<hr>

<ul>
<li><p>If necessary feel free to assume that the polynomial is homogeneous.  May be if thinking about the associated projective variety helps...</p></li>
<li><p>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) </p></li>
<li><p>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. </p></li>
</ul>

<p>But I am wondering if any direct method (algorithm) exists..</p>

CC BY-SA 3.0
2015-05-21T03:07:23.527Z
You might want to check out the [Routh-Hurwitz stability criterion](http://en.wikipedia.org/wiki/Routh%E2%80%93Hurwitz_stability_criterion).
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2015-05-21T08:27:25.260Z
@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 http://en.wikipedia.org/wiki/Sturm%27s_theorem
Sasho Nikolov
<cc.complexity-theory><np-hardness><polynomials><np-complete>
What do we know about checking real-stability of multivariate complex polynomials?
Student
# What do we know about checking real-stability of multivariate complex polynomials?

(Asked by: username_0 on 2015-05-20)

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

**Tags:** cc.complexity-theory, np-hardness, polynomials, np-complete

> **Comments:**
> **username_1**: You might want to check out the [Routh-Hurwitz stability criterion](http://en.wikipedia.org/wiki/Routh%E2%80%93Hurwitz_stability_criterion).  
> **username_2**: @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 http://en.wikipedia.org/wiki/Sturm%27s_theorem  

---

## 1 answers

### Answer by username_3 on 2015-05-24. Score: 6

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

> **Comments:**
> **username_0**: Thanks for the insights. But is there even a brute-force way of checking this property?  
> **username_3**: This essentially *is* the brute force way.  

---

