Operators preserving interlacing
Every linear operator that maps nonzero real-rooted polynomials to zero or to real-rooted polynomials preserves interlacing up to orientation. The operators $\theta=x\,d/dx$, $N-\theta$ and the reverse-Hermite transform preserve it with its orientation.
Results
A polynomial is PF if it has nonnegative coefficients and is zero or has only real, nonpositive roots. On this page $f\ll g$ also holds when $f$ or $g$ is zero, as in the zero-aware convention.
Theorem (real-rootedness preservers). Let $T$ be a real-linear operator on $\mathbb R[x]$ such that $Tp$ is zero or real-rooted for every nonzero real-rooted $p$. If $f\ll g$ with $f$ and $g$ nonzero, then $Tf\ll Tg$ or $Tg\ll Tf$.
Theorem (concrete operators).
- For all polynomials $p\ll q$, we have $\theta p\ll\theta q$.
- For PF polynomials $p\ll q$ of degree at most $N$, we have $(N-\theta)p\ll(N-\theta)q$, where $(N-\theta)p=Np-xp'$.
- For nonzero PF polynomials $p\ll q$ of degree at most $D$, the reciprocals reverse the order: $x^Dq(1/x)\ll x^Dp(1/x)$.
Theorem (reverse-Hermite transform). Let $B_0=1$, $B_1=x$ and $B_{n+2}=x\bigl(B_{n+1}+(n+1)B_n\bigr)$, and let $R$ be the linear map with $R(x^n)=B_n$. Then $R$ maps PF polynomials to PF polynomials, and $p\ll q$ implies $Rp\ll Rq$ for PF $p,q$.
Theorem (from simple roots to PF; Brändén). Let $T$ be a real-linear operator, and suppose $Tq$ is PF for every $q$ with positive leading coefficient and simple, negative roots. Then $Tp$ is PF for every PF polynomial $p$. The same holds degree by degree: if this is assumed only for $q$ of degree at most $d$, then $Tp$ is PF for every PF polynomial $p$ of degree at most $d$.
Corollary (Euler bidiagonal step). If $a,b\ge0$, $ab>0$ and $p$ is PF, then $xp+(\theta+a)(\theta+b)p$ is PF.
Proof
For the transfer from simple roots to PF, a PF polynomial $p$ of degree $d$ is the coefficientwise limit as $\varepsilon\to0^+$ of $(1+\varepsilon D)^dp$, $D=d/dx$. These polynomials have degree $d$, positive leading coefficient and simple negative roots, and the PF cone is closed under coefficientwise limits of bounded degree.
References
- [Bra04, Thm. 8 in the arXiv version], for real-rootedness preservers
- [Bra06, Cor. 3.5], for the transfer from simple roots to PF
- Operators preserving interlacing on symmetricfunctions.com
- [Bra04] On Operators on Polynomials Preserving Real-Rootedness and the Neggers-Stanley Conjecture. Journal of Algebraic Combinatorics, 20(2), 119-130, 2004.
BibTeX
@article{Branden2004operators, title = {On Operators on Polynomials Preserving Real-Rootedness and the {N}eggers-{S}tanley Conjecture}, volume = {20}, ISSN = {0925-9899}, url2 = {http://dx.doi.org/10.1023/B:JACO.0000047295.93525.df}, DOI = {10.1023/b:jaco.0000047295.93525.df}, number = {2}, journal = {Journal of Algebraic Combinatorics}, publisher = {Springer Science and Business Media LLC}, author = {Petter Br{\"{a}}nd{\'{e}}n}, year = {2004}, month = sep, pages = {119–130} } - [Bra06] On linear transformations preserving the Pólya frequency property. Transactions of the American Mathematical Society, 358(8), 3697-3716, 2006.
BibTeX
@article{Branden2006, title = {On linear transformations preserving the {P}{\'{o}}lya frequency property}, volume = {358}, ISSN = {1088-6850}, url = {http://dx.doi.org/10.1090/S0002-9947-06-03856-6}, DOI = {10.1090/s0002-9947-06-03856-6}, number = {8}, journal = {Transactions of the American Mathematical Society}, publisher = {American Mathematical Society (AMS)}, author = {Br{\"a}nd{\'e}n, Petter}, year = {2006}, month = feb, pages = {3697--3716} }