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.

  1. [Fis06] Steve Fisk. 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}
    }
  2. [Bra15] Petter Brändén. 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}
    }

Definitions

  • A 2 × 2 matrix with entries in {0, 1, x}

    RealRooted.Atomic2x2Matrixsource
    structure Atomic2x2Matrix where
      /-- The top-left entry. -/
      a : AtomicMatrixEntry
      /-- The top-right entry. -/
      b : AtomicMatrixEntry
      /-- The bottom-left entry. -/
      c : AtomicMatrixEntry
      /-- The bottom-right entry. -/
      d : AtomicMatrixEntry
      deriving DecidableEq, Repr
  • The matrix preserves interlacing pairs

    RealRooted.Atomic2x2Matrix.PreservesInterlacingsource
    def PreservesInterlacing (M : Atomic2x2Matrix) : Prop :=
      ∀ (fs : List ℝ[X]), fs.length = 2 →
        IsInterlacingSeq0NonnegRealRooted fs →
        IsInterlacingSeq0NonnegRealRooted (matPolyAction M.eval fs)
  • No zero row and two distinct rows

    RealRooted.Atomic2x2Matrix.IsNondegeneratesource
    def IsNondegenerate (M : Atomic2x2Matrix) : Prop :=
      M.isNondegenerate = true
  • The 18 listed matrices

    RealRooted.Atomic2x2Matrix.nondegeneratePreservingMatricessource
    def nondegeneratePreservingMatrices : Finset Atomic2x2Matrix :=
      nondegeneratePreservingMatricesList.toFinset

Theorems

  • A nondegenerate matrix preserves interlacing exactly when it is one of the 18Main result

    RealRooted.Atomic2x2Matrix.isNondegenerate_and_interlacing_iff_memsourcestatement on symmetricfunctions.com
    theorem Atomic2x2Matrix.isNondegenerate_and_interlacing_iff_mem (M : Atomic2x2Matrix) :
        M.IsNondegenerate ∧ M.PreservesInterlacing ↔ M ∈ nondegeneratePreservingMatrices
  • Exactly 18 nondegenerate matrices preserve interlacing

    RealRooted.Atomic2x2Matrix.ncard_isNondegenerate_and_preservesInterlacingsource
    theorem ncard_isNondegenerate_and_preservesInterlacing :
        {M : Atomic2x2Matrix | M.IsNondegenerate ∧ M.PreservesInterlacing}.ncard = 18
  • There are 81 matrices

    RealRooted.Atomic2x2Matrix.cardsource
    theorem card : Fintype.card Atomic2x2Matrix = 81
  • 56 of them are nondegenerate

    RealRooted.Atomic2x2Matrix.ncard_isNondegeneratesource
    theorem ncard_isNondegenerate :
        {M : Atomic2x2Matrix | M.IsNondegenerate}.ncard = 56
  • 40 of them preserve interlacing

    RealRooted.Atomic2x2Matrix.ncard_preservesInterlacingsource
    theorem ncard_preservesInterlacing :
        {M : Atomic2x2Matrix | M.PreservesInterlacing}.ncard = 40

Lean source RealRooted/Challenges/Matrices/SmallInterlacingMatrices.lean at revision d6670742. Formalized 2026-10-06.