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

  1. every entry $G_{ij}$ has nonnegative coefficients, and
  2. 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.

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.

  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 polynomial matrix acting on a sequence

    RealRooted.matPolyActionsource
    def matPolyAction (G : List (List ℝ[X])) (fs : List ℝ[X]) : List ℝ[X] :=
      G.map (fun row => (row.zipWith (· * ·) fs).sum)
  • Zero-aware nonnegative real-rooted interlacing sequence

    RealRooted.IsInterlacingSeq0NonnegRealRootedsource
    def IsInterlacingSeq0NonnegRealRooted (fs : List ℝ[X]) : Prop :=
      IsInterlacingSeq0Nonneg fs ∧
        ∀ f ∈ fs, f ≠ 0 → (f ≠ 0 ∧ f.Splits)
  • The matrix preserves zero-aware interlacing sequences

    RealRooted.PreservesInterlacingSeq0source
    def PreservesInterlacingSeq0 (n : ℕ) (G : List (List ℝ[X])) : Prop :=
      ∀ fs : List ℝ[X], fs.length = n → IsInterlacingSeq0NonnegRealRooted fs →
        IsInterlacingSeq0NonnegRealRooted (matPolyAction G fs)
  • 2 × 2 interlacing condition, allowing zeros

    RealRooted.Has2x2InterlacingProperty0source
    def Has2x2InterlacingProperty0 (a b c d : ℝ[X]) : Prop :=
      ∀ (s t : ℝ), 0 < s → 0 < t →
        Interl ((C s * X + C t) * b + d) ((C s * X + C t) * a + c)
  • 2 × 2 interlacing condition

    RealRooted.Has2x2InterlacingPropertysource
    def Has2x2InterlacingProperty (a b c d : ℝ[X]) : Prop :=
      ∀ (s t : ℝ), 0 < s → 0 < t →
        StrictInterl ((C s * X + C t) * b + d) ((C s * X + C t) * a + c)
  • Interlacing sequence of real-rooted polynomials with nonnegative coefficients

    RealRooted.IsInterlacingSeqNonnegsource
    def IsInterlacingSeqNonneg (fs : List ℝ[X]) : Prop :=
      (∀ f ∈ fs, (f ≠ 0 ∧ f.Splits) ∧ HasNonnegCoeffs f) ∧
      IsInterlacingSeq fs

Theorems

  • A matrix preserves interlacing sequences exactly when its 2 × 2 submatrices doMain result

    RealRooted.PreservesInterlacingSeq0.iff_nonneg_and_2x2sourcestatement on symmetricfunctions.com
    theorem PreservesInterlacingSeq0.iff_nonneg_and_2x2 {n : ℕ} (G : List (List ℝ[X]))
        (hG_rect : ∀ row ∈ G, row.length = n) :
        PreservesInterlacingSeq0 n G ↔
          (∀ row ∈ G, ∀ p ∈ row, HasNonnegCoeffs p) ∧
          ∀ (i₁ i₂ : Fin G.length) (j₁ j₂ : Fin n), i₁ ≤ i₂ → j₁ ≤ j₂ →
            Has2x2InterlacingProperty0
              ((G.get i₁).get ⟨j₁, by simp_all⟩)
              ((G.get i₁).get ⟨j₂, by simp_all⟩)
              ((G.get i₂).get ⟨j₁, by simp_all⟩)
              ((G.get i₂).get ⟨j₂, by simp_all⟩)
  • Strict form: the strict condition preserves strict interlacing sequences

    RealRooted.IsInterlacingSeqNonneg.matPolyAction_of_2x2source
    theorem IsInterlacingSeqNonneg.matPolyAction_of_2x2 {n : ℕ} (hn : n ≠ 0) (G : List (List ℝ[X]))
        (hG_rect : ∀ row ∈ G, row.length = n)
        (hG_nonneg : ∀ row ∈ G, ∀ p ∈ row, HasNonnegCoeffs p)
        (hG_affine : ∀ (i₁ i₂ : Fin G.length) (j₁ j₂ : Fin n),
          i₁ ≤ i₂ → j₁ ≤ j₂ →
          Has2x2InterlacingProperty
            ((G.get i₁).get ⟨j₁, by simp_all⟩)
            ((G.get i₁).get ⟨j₂, by simp_all⟩)
            ((G.get i₂).get ⟨j₁, by simp_all⟩)
            ((G.get i₂).get ⟨j₂, by simp_all⟩))
        (fs : List ℝ[X]) (hfs_len : fs.length = n) (hfs : IsInterlacingSeqNonneg fs) :
        IsInterlacingSeqNonneg (matPolyAction G fs)
  • Strict input, zero-aware output

    RealRooted.IsInterlacingSeq0Nonneg.matPolyAction_of_2x2source
    theorem IsInterlacingSeq0Nonneg.matPolyAction_of_2x2
        (G : List (List ℝ[X]))
        (hG_rect : ∀ row ∈ G, row.length = n)
        (hG_nonneg : ∀ row ∈ G, ∀ p ∈ row, HasNonnegCoeffs p)
        (hG_affine : ∀ (i₁ i₂ : Fin G.length) (j₁ j₂ : Fin n),
          i₁ ≤ i₂ → j₁ ≤ j₂ →
          Has2x2InterlacingProperty0
            ((G.get i₁).get ⟨j₁, by simp_all⟩)
            ((G.get i₁).get ⟨j₂, by simp_all⟩)
            ((G.get i₂).get ⟨j₁, by simp_all⟩)
            ((G.get i₂).get ⟨j₂, by simp_all⟩))
        (fs : List ℝ[X]) (hfs_len : fs.length = n)
        (hfs : IsInterlacingSeqNonneg fs) :
        IsInterlacingSeq0Nonneg (matPolyAction G fs)
  • Products of interlacing-preserving matrices preserve interlacing

    RealRooted.PreservesInterlacingSeq0.matPolyMulsource
    theorem PreservesInterlacingSeq0.matPolyMul (n : ℕ) (H G : List (List ℝ[X]))
        (hH_rect : ∀ row ∈ H, row.length = G.length)
        (hG_rect : ∀ row ∈ G, row.length = n)
        (hG : PreservesInterlacingSeq0 n G)
        (hH : PreservesInterlacingSeq0 G.length H) :
        PreservesInterlacingSeq0 n (matPolyMul n H G)
  • A sequence is interlacing exactly when it is pairwise interlacing

    RealRooted.isInterlacingSeq_iff_pairwisesource
    lemma isInterlacingSeq_iff_pairwise {fs : List ℝ[X]} :
        IsInterlacingSeq fs ↔ fs.Pairwise StrictInterl
  • The zero-aware version is pairwise weak interlacing

    RealRooted.isInterlacingSeq0_iff_pairwisesource
    lemma isInterlacingSeq0_iff_pairwise {fs : List ℝ[X]} :
        IsInterlacingSeq0 fs ↔ fs.Pairwise Interl
  • The reversed product-sum of two interlacing nonnegative sequences is real-rooted

    RealRooted.isRealRooted_zipWith_mul_sum_reverse_of_interlacingSeqNonnegsource
    theorem isRealRooted_zipWith_mul_sum_reverse_of_interlacingSeqNonneg
        {fs gs : List ℝ[X]}
        (hne : fs ≠ [])
        (hlen : fs.length = gs.length)
        (hfs : IsInterlacingSeqNonneg fs)
        (hgs : IsInterlacingSeqNonneg gs) :
        (((fs.zipWith (· * ·) gs.reverse).sum) ≠ 0 ∧
          ((fs.zipWith (· * ·) gs.reverse).sum).Splits)
  • The reversed product-sum theorem allowing zero terms in both sequences

    RealRooted.zipWith_mul_sum_reverse_isRealRootedsource
    theorem zipWith_mul_sum_reverse_isRealRooted
        {fs gs : List ℝ[X]}
        (hfs : IsInterlacingSeq0Nonneg fs)
        (hfs_real : ∀ f ∈ fs, f ≠ 0 → (f ≠ 0 ∧ f.Splits))
        (hgs : IsInterlacingSeq0Nonneg gs)
        (hgs_real : ∀ g ∈ gs, g ≠ 0 → (g ≠ 0 ∧ g.Splits))
        (hsum_ne : (fs.zipWith (· * ·) gs.reverse).sum ≠ 0) :
        (((fs.zipWith (· * ·) gs.reverse).sum) ≠ 0 ∧
          ((fs.zipWith (· * ·) gs.reverse).sum).Splits)

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