Matrices preserving interlacing sequences
A matrix of polynomials with nonnegative coefficients maps interlacing sequences to interlacing sequences if and only if every ordered $2\times2$ submatrix satisfies an affine interlacing condition.
Results
Let $G=(G_{ij})$ be an $m\times n$ matrix of real polynomials. It acts on a sequence $F=(f_1,\dots,f_n)$ by $(GF)_i=\sum_jG_{ij}f_j$. For polynomials $f,g$ we write $f\ll g$ if either one of them is zero, or both are nonzero, real-rooted and interlace weakly, as in the zero-aware convention of Conventions. Let $\mathcal F_n^{0}$ be the set of sequences $(f_1,\dots,f_n)$ of polynomials with nonnegative coefficients such that every nonzero $f_i$ is real-rooted and $f_i\ll f_j$ whenever $i<j$.
Theorem (matrix criterion). The matrix $G$ maps $\mathcal F_n^{0}$ into $\mathcal F_m^{0}$ if and only if
- every entry $G_{ij}$ has nonnegative coefficients, and
- for all rows $i_1\le i_2$ and columns $j_1\le j_2$, the submatrix $\begin{pmatrix}a&b\\c&d\end{pmatrix}= \begin{pmatrix}G_{i_1j_1}&G_{i_1j_2}\\G_{i_2j_1}&G_{i_2j_2}\end{pmatrix}$ satisfies $$ (sx+t)\,b+d\ \ll\ (sx+t)\,a+c\qquad\text{for all }s,t>0. $$
Repeated indices $i_1=i_2$ or $j_1=j_2$ are allowed in condition 2.
Theorem (strict input). Call $(f_1,\dots,f_n)$ strict if every $f_i$ is nonzero and real-rooted with nonnegative coefficients, and $f_i\ll f_j$ for $i<j$. Let $n\ge1$ and let $G$ satisfy condition 1.
- If condition 2 holds with both sides of $\ll$ nonzero, then $G$ maps strict sequences to strict sequences.
- Under condition 2 as stated, $G$ maps a strict sequence to a sequence $(g_1,\dots,g_m)$ of polynomials with nonnegative coefficients and $g_i\ll g_j$ for $i<j$, where some $g_i$ may vanish.
Proposition (products). If an $m\times k$ matrix $H$ and a $k\times n$ matrix $G$ both map $\mathcal F^0$ into itself, so does $HG$.
Theorem (product-sum). [Bra15, §7.8] Let $(f_1,\dots,f_n)$ and $(g_1,\dots,g_n)$, $n\ge1$, be interlacing sequences of real-rooted polynomials with nonnegative coefficients. Then $$ \sum_{i=1}^nf_i\,g_{n+1-i} $$ is nonzero and real-rooted. If instead the terms of each sequence interlace weakly, every nonzero term is real-rooted and the sum is nonzero, then the sum is real-rooted.
Proof
For the product-sum theorem, the products $f_ig_{n+1-i}$ have pairwise common interleavers, and by the Chudnovsky–Seymour theorem on common interleavers this gives a common interleaver of the whole family.
References
Matrices preserving interlacing are treated in [Fis06, Ch. 3]. The exact nonnegative polynomial characterization is [Bra15, Thm. 7.8.5]. See the matrix criterion on symmetricfunctions.com.
- [Fis06] Polynomials, roots, and interlacing. arXiv e-prints, 2006.
BibTeX
@article{Fisk2006x, Author = {Steve Fisk}, Title = {Polynomials, roots, and interlacing}, Year = {2006}, Eprint = {arXiv:math/0612833}, journal = {arXiv e-prints} } - [Bra15] Unimodality, Log-Concavity, Real-Rootedness and Beyond. Handbook of enumerative combinatorics, 437-483, 2015.
BibTeX
@incollection{Branden2015, doi = {10.1201/b18255-10}, year = {2015}, month = mar, publisher = {Chapman and Hall/{CRC}}, pages = {437--483}, author = {Petter Br{\"{a}}nd{\'{e}}n}, title = {Unimodality, Log-Concavity, Real-Rootedness and Beyond}, booktitle = {Handbook of Enumerative Combinatorics} }