Real stability
Real stability is the multivariate generalization of real-rootedness. A multiaffine real polynomial is real stable if and only if it is Rayleigh; determinantal pencils are real stable; real stability is preserved by homogenization, specialization and inversion; and it gives hyperbolicity, matroid supports, Lorentzian polynomials and the root bound for mixed characteristic polynomials.
Results
A polynomial $P\in\mathbb C[z_1,\dotsc,z_n]$ is stable if $P(z)\ne0$ whenever $\operatorname{Im}z_i>0$ for all $i$; in particular $P\ne0$. A polynomial with real coefficients is real stable if it is stable as a complex polynomial. It is multiaffine if it has degree at most one in each variable, and Rayleigh if $$ \partial_iP\,\partial_jP-P\,\partial_i\partial_jP\ge0 $$ at every $x\in\mathbb R^n$ and for all $i,j$. A real polynomial $P$ is hyperbolic in the direction $e\in\mathbb R^n$ if $P(e)\ne0$ and $t\mapsto P(x+te)$ is real-rooted for every $x\in\mathbb R^n$.
Theorem (Brändén) [Bra07]. A multiaffine $P\in\mathbb R[z_1,\dotsc,z_n]$ is real stable if and only if $P\ne0$ and $P$ is Rayleigh.
Corollary (Borcea–Brändén–Liggett) [BBL08]. Let $\mu$ be a weight function on the subsets of $\{1,\dotsc,n\}$ whose generating polynomial $\sum_S\mu(S)\prod_{i\in S}z_i$ is real stable. Then for $i\ne j$, $$ \mu(\Omega)\,\mu(i,j\in S)\le\mu(i\in S)\,\mu(j\in S). $$ For a probability measure this is pairwise negative correlation; it is the Rayleigh inequality at the all-ones point.
Theorem (Borcea–Brändén) [BB08]. Let $A$ be a Hermitian $m\times m$ matrix and $B_1,\dotsc,B_n$ positive semidefinite $m\times m$ matrices. Then $\det(A+z_1B_1+\dotsb+z_nB_n)$ is stable or identically zero. If all matrices are real and the determinant is not identically zero, it is real stable.
Corollary (Choe–Oxley–Sokal–Wagner) [COSW04]. If a finite graph $G$ has a spanning tree, its spanning-tree polynomial $\sum_T\prod_{e\in T}z_e$ is real stable. By Kirchhoff's weighted matrix-tree theorem it equals the determinant of the reduced Laplacian $\sum_ez_eb_eb_e^{T}$, a pencil of positive semidefinite rank-one matrices.
Theorem (hyperbolicity). A homogeneous $P\in\mathbb R[z_1,\dotsc,z_n]$ is real stable if and only if it is hyperbolic in every direction $e$ with all $e_i>0$. If a homogeneous $P$ is hyperbolic in the direction $e$, then it is hyperbolic in every direction $u$ joined to $e$ by a path in $\{x:P(x)\ne0\}$.
Theorem (Gårding) [Gar59]. If a homogeneous $P$ is hyperbolic in the direction $e$, its hyperbolicity cone, the path component of $e$ in $\{x:P(x)\ne0\}$, is convex.
Theorem (homogenization). Let $P\ne0$ be real stable with nonnegative coefficients and total degree $d$. Then $z_0^dP(z_1/z_0,\dotsc,z_n/z_0)$ and the top homogeneous component of $P$ are real stable. The homogenization in any degree at least $d$ is also real stable.
Theorem (top component). If $P$ is real stable, then its top homogeneous component is real stable, and the homogenization $z_0^dP(z_1/z_0,\dotsc,z_n/z_0)$, with $d$ the total degree of $P$, is hyperbolic in the direction $(0,b)$ for every $b\in\mathbb R^n$ with all $b_i>0$. In particular the top component does not vanish at such $b$.
Theorem (same-phase stability). If $P$ is real stable, then for every $w\in\mathbb R^n$ with all $w_i\ge0$ the polynomial $P(w_1t,\dotsc,w_nt)$ is real-rooted.
Theorem (line restrictions). $P$ is real stable if and only if, for all $a\in\mathbb R^n$ and $b\in\mathbb R_{>0}^n$, the restriction $t\mapsto P(a+tb)$ is nonzero and real-rooted.
Theorem (inversion). Let $P$ be a stable polynomial in a variable $z_0$ and further variables, of degree at most $d$ in $z_0$. Then $z_0^dP(-1/z_0,\dotsc)$ is stable, and real stable if $P$ is. For one variable: if $p$ has no zeros in the open upper half-plane and $\deg p\le d$, then $z^dp(-1/z)$ has none.
Theorem (specialization). Let $P$ be stable and $c$ real. Then $P$ with the variable $z_i$ replaced by $c$ is stable or identically zero. The same holds for repeated specialization of several variables at real values, and for setting a finite block of variables to zero.
Theorem (differentiation). Let $P$ be stable in $z_0,z_1,\dotsc,z_n$, of degree at most $m\ge1$ in $z_0$, and suppose the coefficient of $z_0^m$ is a nonzero constant. Then $\partial P/\partial z_0$ is stable.
Theorem (common-rotation criterion). Call a complex polynomial $Q$ common-rotation stable if $Q(z)\ne0$ whenever some single $c$ with $\operatorname{Im}c>0$ satisfies $\operatorname{Im}(cz_i)>0$ for all $i$. A homogeneous polynomial $P$ in $z_0,z_1,\dotsc,z_n$ is stable if and only if $P(1,z_1,\dotsc,z_n)$ is common-rotation stable; for a homogeneous real polynomial the same holds for real stability. The ordinary homogenization of $p$ in any degree at least $\deg p$ is stable if and only if $p$ is common-rotation stable.
Theorem (affine extensions). Let $P$ and $Q$ be multiaffine polynomials not involving $z_k$. Write $W_i(Q,P)=Q\,\partial_iP-P\,\partial_iQ$ for the coordinate Wronskian, $R_{ij}(F)=\partial_iF\,\partial_jF-F\,\partial_i\partial_jF$ for the Rayleigh difference, and $M_{ij}=\partial_iP\,\partial_jQ+\partial_iQ\,\partial_jP -P\,\partial_i\partial_jQ-Q\,\partial_i\partial_jP$. Then $P+z_kQ$ is Rayleigh if and only if
- $P$ and $Q$ are Rayleigh,
- $W_i(Q,P)(x)\ge0$ for all $i$ and $x\in\mathbb R^n$, and
- $M_{ij}^2-4R_{ij}(Q)R_{ij}(P)\le0$ at every $x\in\mathbb R^n$, for all $i,j\ne k$.
The Wronskians satisfy the Plücker relation $W_i(P,A)\,W_i(Q,B)=W_i(P,Q)\,W_i(A,B)+W_i(P,B)\,W_i(Q,A)$. If $P\in\mathbb C[z_1,\dotsc,z_n]$ is multiaffine and stable, so is $z\mapsto\prod_iz_i\,P(-1/z_1,\dotsc,-1/z_n)$. If $P$ is Rayleigh, $a\in\mathbb R^n$ and $b\in\mathbb R^n$ has nonnegative entries, then $p(t)=P(a+tb)$ satisfies $p'(t)^2-p(t)\,p''(t)\ge0$ for all real $t$.
Theorem (Brändén) [Bra07]. The support of a real stable polynomial is a jump system: for support points $\alpha,\beta$ and a unit step $s=\pm e_i$ from $\alpha$ towards $\beta$, either $\alpha+s$ is in the support, or some further unit step $t$ towards $\beta$ has $\alpha+s+t$ in the support.
Corollary (Brändén). If $P$ is homogeneous, multiaffine and real stable, its support is the set of bases of a matroid: $B$ is a basis exactly when its indicator vector lies in the support of $P$.
Theorem (Brändén–Huh) [BH20]. A homogeneous real stable polynomial with nonnegative coefficients is Lorentzian.
Theorem (mixed characteristic polynomials). For real positive semidefinite matrices $A_i$, the mixed characteristic polynomial $$ \mu[A](x)=\prod_i(1-\partial_{z_i})\det\Bigl(xI+\sum_iz_iA_i\Bigr)\Big|_{z=0} $$ is nonzero and real-rooted.
Theorem (Marcus–Spielman–Srivastava) [MSS15]. Let $A_1,\dotsc,A_m$ be real positive semidefinite $n\times n$ matrices with $\sum_iA_i=I$ and $\operatorname{tr}A_i\le\varepsilon$, where $\varepsilon>0$. Then every root of $\mu[A]$ is at most $(1+\sqrt\varepsilon)^2$. This is the root bound behind the solution of the Kadison–Singer problem.
Theorem (MSS, Thm. 4.1) [MSS15, Thm. 4.1]. The expected characteristic polynomial of a sum of independent random rank-one matrices equals the mixed characteristic polynomial of their second-moment matrices.
Proof
For determinantal pencils, if $v\ne0$ lies in the kernel of $M=A+\sum_iz_iB_i$ with all $\operatorname{Im}z_i>0$, then $\operatorname{Im}(v^*Mv)=\sum_i\operatorname{Im}(z_i)\,v^*B_iv=0$ forces $B_iv=0$ and $Av=0$, so the pencil is singular everywhere. Inversion uses that $z\mapsto-1/z$ maps the open upper half-plane to itself. For $P+z_kQ$ and $i,j\ne k$, the Rayleigh difference is a quadratic in $z_k$ with coefficients $R_{ij}(P)$, $M_{ij}$ and $R_{ij}(Q)$, and for $i=k$ it equals $W_j(Q,P)$. The root bound for $\mu[A]$ follows the barrier argument of Marcus, Spielman and Srivastava, with the Helton–Vinnikov step replaced by an elementary Pick-function lemma.
References
- [Gar59]
- [COSW04]
- [Bra07]
- [BB08]
- [BBL08]
- [MSS15]
- [BH20]
- Stable polynomials and the Rayleigh property on symmetricfunctions.com
- [COSW04] Homogeneous multivariate polynomials with the half-plane property. Advances in Applied Mathematics, 32(1-2), 88-187, 2004.
BibTeX
@article{ChoeOxleySokalWagner2004, doi = {10.1016/s0196-8858(03)00078-2}, url2 = {https://doi.org/10.1016/s0196-8858(03)00078-2}, year = {2004}, month = jan, publisher = {Elsevier {BV}}, volume = {32}, number = {1-2}, pages = {88--187}, author = {Young-Bin Choe and James G. Oxley and Alan D. Sokal and David G. Wagner}, title = {Homogeneous multivariate polynomials with the half-plane property}, journal = {Advances in Applied Mathematics} } - [Bra07] Polynomials with the half-plane property and matroid theory. Advances in Mathematics, 216(1), 302-320, 2007.
BibTeX
@article{Branden2007, title={Polynomials with the half-plane property and matroid theory}, author={Br{\"{a}}nd{\'{e}}n, Petter}, journal={Advances in Mathematics}, volume={216}, number={1}, pages={302--320}, year={2007}, doi={10.1016/j.aim.2007.05.011}, publisher={Elsevier} } - [BB08] Applications of stable polynomials to mixed determinants: Johnson’s conjectures, unimodality, and symmetrized Fischer products. Duke Mathematical Journal, 143(2), 205-223, 2008.
BibTeX
@article{BorceaBranden2008MixedDeterminants, doi = {10.1215/00127094-2008-018}, url2 = {https://doi.org/10.1215/00127094-2008-018}, year = {2008}, month = jun, publisher = {Duke University Press}, volume = {143}, number = {2}, pages = {205--223}, author = {Julius Borcea and Petter Br{\"{a}}nd{\'{e}}n}, title = {Applications of stable polynomials to mixed determinants: {J}ohnson's conjectures, unimodality, and symmetrized {F}ischer products}, journal = {Duke Mathematical Journal} } - [BBL08] Negative dependence and the geometry of polynomials. Journal of the American Mathematical Society, 22(2), 521-567, 2008.
BibTeX
@article{BorceaBrandenLiggett2008, title = {Negative dependence and the geometry of polynomials}, volume = {22}, ISSN = {1088-6834}, url = {http://dx.doi.org/10.1090/S0894-0347-08-00618-8}, DOI = {10.1090/s0894-0347-08-00618-8}, number = {2}, journal = {Journal of the American Mathematical Society}, publisher = {American Mathematical Society (AMS)}, author = {Borcea, Julius and Br{\"{a}}nd{\'{e}}n, Petter and Liggett, Thomas}, year = {2008}, month = sep, pages = {521–567} } - [MSS15] Interlacing families II: Mixed characteristic polynomials and the Kadison--Singer problem. Annals of Mathematics, 182(1), 327-350, 2015.
BibTeX
@article{MarcusSpielmanSrivastava2015II, author = {Adam Marcus and Daniel A. Spielman and Nikhil Srivastava}, title = {Interlacing families {II}: Mixed characteristic polynomials and the {K}adison--{S}inger problem}, year = {2015}, journal = {Annals of Mathematics}, volume = {182}, number = {1}, pages = {327--350}, doi = {10.4007/annals.2015.182.1.8}, url = {https://doi.org/10.4007/annals.2015.182.1.8}, eprint = {1306.3969} } - [BH20] Lorentzian polynomials. Annals of Mathematics, 192(3), 2020.
BibTeX
@article{BrandenHuh2020, title = {Lorentzian polynomials}, volume = {192}, ISSN = {0003-486X}, url = {http://dx.doi.org/10.4007/annals.2020.192.3.4}, DOI = {10.4007/annals.2020.192.3.4}, number = {3}, journal = {Annals of Mathematics}, publisher = {Annals of Mathematics}, author = {Br{\"{a}}nd{\'{e}}n, Petter and Huh, June}, year = {2020}, month = nov } - [Gar59] An Inequality for Hyperbolic Polynomials. Indiana University Mathematics Journal, 8(6), 957-965, 1959.
BibTeX
@article{Garding1959, author = {Gårding, Lars}, title = {An {I}nequality for {H}yperbolic {P}olynomials}, year = {1959}, journal = {Indiana University Mathematics Journal}, volume = {8}, number = {6}, pages = {957--965}, doi = {10.1512/iumj.1959.8.58061}, url = {https://doi.org/10.1512/iumj.1959.8.58061} }