Small matrices preserving interlacing sequences
Of the $3^4=81$ matrices with entries in $\{0,1,x\}$, exactly 18 nondegenerate ones preserve interlacing of pairs.
Results
A matrix $M=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ with entries in $\{0,1,x\}$ acts on pairs by $$ M\cdot(f_1,f_2)=(af_1+bf_2,\ cf_1+df_2). $$ We say $M$ preserves interlacing if, whenever $f_1,f_2$ have nonnegative coefficients, every nonzero one of them is real-rooted, and $f_1\ll f_2$ (either polynomial may be zero), the image pair has the same three properties. We call $M$ nondegenerate if neither row is $(0,0)$ and the two rows are distinct. Exactly 56 of the 81 matrices are nondegenerate.
Theorem. Exactly 40 of the 81 matrices preserve interlacing. A nondegenerate matrix preserves interlacing if and only if it is one of the following 18 matrices, written as lists of rows: $$ \begin{gathered} [[0, 1], [0, x]],\ [[0, 1], [x, 0]],\ [[1, 0], [0, 1]],\ [[1, 0], [x, 0]],\ [[x, 0], [0, x]],\ [[0, 1], [x, 1]], \\ [[0, 1], [x, x]],\ [[1, 0], [1, 1]],\ [[1, 0], [x, 1]],\ [[1, 1], [0, 1]],\ [[1, 1], [x, 0]],\ [[x, 0], [x, x]], \\ [[x, 1], [0, x]],\ [[x, 1], [x, 0]],\ [[x, x], [0, x]],\ [[1, 1], [x, 1]],\ [[1, 1], [x, x]],\ [[x, 1], [x, x]]. \end{gathered} $$
Proof
By the matrix criterion of Brändén [Bra15, Thm. 7.8.5], a nonnegative polynomial matrix preserves interlacing sequences exactly when each ordered $2\times2$ submatrix, repeated indices allowed, satisfies an affine interlacing condition. For entries in $\{0,1,x\}$ this leaves a finite table of admissible matrices. For a matrix outside it, an explicit sparse pair is mapped to a pair that does not interlace.
References
[Fis06, Ch. 3]; [Bra15, Thm. 7.8.5]. See the table 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} }