Totally nonnegative left production matrices

If a lower-triangular matrix has totally nonnegative leading truncations, the rows of the array it generates are Pólya frequency sequences, so their generating polynomials are real-rooted with nonpositive roots. This covers Riordan arrays built from Pólya frequency series and polynomial sequences defined by suitable rational generating functions.

Results

Let $Q=(q_{n,k})_{n,k\geq0}$ and let the lower-triangular array $A=(a_{n,k})_{n,k\geq0}$ satisfy $$ a_{n,0}=q_{n,0},\qquad a_{n+1,k+1}=\sum_{j=k}^{n}q_{n+1,j+1}a_{j,k}. $$ This is the entrywise form of the left-production factorization $A=Q\,\operatorname{diag}(I_1,Q)\operatorname{diag}(I_2,Q)\cdots$.

Theorem (Chen–Fu–Ruan). Suppose $Q$ is lower triangular and every finite leading principal truncation of $Q$ is totally nonnegative. Then every row $(a_{n,k})_{k\geq0}$ is a Pólya frequency sequence, and the polynomial $\sum_{k=0}^{n}a_{n,k}x^k$ splits over $\mathbb R$ with all roots nonpositive.

Theorem (Pólya frequency Riordan arrays). Let $d(z)$ and $K(z)$ be power series with Pólya frequency coefficient sequences. The ordinary Riordan array whose $k$th column is $d(z)\bigl(z d(z)K(z)\bigr)^k$ has left production matrix $T(d)\operatorname{diag}(1,T(K))$, with $T$ the lower Toeplitz matrix. Every row polynomial of the array splits over $\mathbb R$ with only nonpositive roots. Series of the form $$ c z^r\frac{\prod_i(1+\alpha_i z)}{\prod_j(1-\beta_jz)}, \qquad c,\alpha_i,\beta_j\geq0, $$ with finitely many factors have Pólya frequency coefficients.

Theorem (recurrence criterion). Let $(P_n)$ be a polynomial sequence with $$ \bigl(D_0(z)-xL(z)\bigr)\sum_{n\geq0}P_n(x)z^n=N(z) $$ as an identity of coefficients, where $D_0(0)=1$. If $d=N/D_0$ and $K=L/(zN)$ have Pólya frequency coefficient sequences, then every $P_n$ splits over $\mathbb R$ with roots at most zero. Examples are the rows of OEIS A114123 and the polynomials $R_m(x)=\sum_j\binom{m-j}{2j}x^j$.

Total nonnegativity of the Riordan array alone does not suffice: $d=1/(1-z)$ and $h=z$ give a totally nonnegative array with row polynomial $1+x+x^2$, which does not split over $\mathbb R$.

Proof

The transpose of every finite leading Toeplitz matrix of row $n$ is a submatrix of a product of shifted block copies of the leading truncation $Q_n$. Total nonnegativity is preserved by identity-block extensions, finite products, submatrices and transposes, so the rows are Pólya frequency sequences, and the Aissen–Schoenberg–Whitney theorem gives the real roots.

References

  1. [CFR25, Theorems 1.3 and 1.4] Xi Chen, Lang Fu, & Jiajie Ruan. A unified planar network approach to total positivity of combinatorial matrices and real-rootedness of polynomials. arXiv e-prints, 2025.
    BibTeX
    @article{ChenFuRuan2025x,
      author = {Xi Chen and Lang Fu and Jiajie Ruan},
      title = {A unified planar network approach to total positivity of combinatorial matrices and real-rootedness of polynomials},
      year = {2025},
      eprint = {2512.08369},
      url = {https://arxiv.org/abs/2512.08369},
      journal = {arXiv e-prints}
    }

Definitions

  • Array generated by a left production matrix

    RealRooted.IsLeftProductionArraysource
    def IsLeftProductionArray (q a : ℕ → ℕ → ℝ) : Prop :=
      (∀ n, a n 0 = q n 0) ∧
        (∀ n k, a (n + 1) (k + 1) =
          ∑ j ∈ Finset.Icc k n, q (n + 1) (j + 1) * a j k) ∧
        LowerTriangularMatrix.IsLowerTriangular a
  • Totally nonnegative finite leading truncations

    RealRooted.HasTotallyNonnegativeLeadingTruncationssource
    def HasTotallyNonnegativeLeadingTruncations (q : ℕ → ℕ → ℝ) : Prop :=
      ∀ N, (leadingTruncation q N).IsTotallyNonneg
  • Row-generating polynomial

    RealRooted.LeftProductionMatrix.rowPolynomialsource
    def rowPolynomial (a : ℕ → ℕ → ℝ) (n : ℕ) : ℝ[X] :=
      LowerTriangularMatrix.rowPolynomial a n
  • Row polynomial of a Pólya frequency Riordan array

    RealRooted.PFRiordan.rowPolynomialsource
    def rowPolynomial (d K : ℕ → ℝ) (n : ℕ) : ℝ[X] :=
      LeftProductionMatrix.rowPolynomial (array d K) n

Theorems

  • A row Toeplitz truncation is a submatrix of a left-production productRealRooted original

    RealRooted.LeftProductionMatrix.toeplitzFin_transpose_eq_submatrix_finiteProductsource
    theorem toeplitzFin_transpose_eq_submatrix_finiteProduct
        (ha : IsLeftProductionArray q a) (n r : ℕ) :
        (toeplitzFin (a n) r).transpose =
          (finiteProduct q n r).submatrix
            (fun i : Fin (r + 1) => ⟨n + i.val, by lia⟩)
            (fun j : Fin (r + 1) => ⟨j.val, by lia⟩)
  • Rows from a totally nonnegative left production matrix are Pólya frequencyRealRooted original

    RealRooted.LeftProductionMatrix.isPolyaFreqSeq_of_isLeftProductionArraysource
    theorem isPolyaFreqSeq_of_isLeftProductionArray
        (ha : IsLeftProductionArray q a)
        (hqLower : LowerTriangularMatrix.IsLowerTriangular q)
        (hq : HasTotallyNonnegativeLeadingTruncations q) (n : ℕ) :
        IsPolyaFreqSeq (a n)
  • Row polynomials split with nonpositive rootsMain resultRealRooted original

    RealRooted.LeftProductionMatrix.rowPolynomial_splits_roots_nonpossource
    theorem rowPolynomial_splits_roots_nonpos
        (ha : IsLeftProductionArray q a)
        (hqLower : LowerTriangularMatrix.IsLowerTriangular q)
        (hq : HasTotallyNonnegativeLeadingTruncations q) (n : ℕ) :
        (rowPolynomial a n).Splits ∧
          ∀ r ∈ (rowPolynomial a n).roots, r ≤ 0
  • Riordan left production matrix factorizationRealRooted original

    RealRooted.PFRiordan.production_eq_toeplitz_mul_oneToeplitzsource
    theorem production_eq_toeplitz_mul_oneToeplitz (d K : ℕ → ℝ) :
        production d K =
          LowerTriangularMatrix.mul (lowerToeplitz d) (oneToeplitz K)
  • Rows of a Pólya frequency Riordan array split with nonpositive rootsRealRooted original

    RealRooted.PFRiordan.rowPolynomial_splits_and_roots_nonpossource
    theorem rowPolynomial_splits_and_roots_nonpos
        {d K : ℕ → ℝ} (hd : IsPolyaFreqSeq d) (hK : IsPolyaFreqSeq K)
        (n : ℕ) :
        (rowPolynomial d K n).Splits ∧
          ∀ r ∈ (rowPolynomial d K n).roots, r ≤ 0
  • Finite rational products have Pólya frequency coefficientsRealRooted original

    RealRooted.PFRiordan.rationalPFCoeff_isPolyaFreqSeqsource
    theorem rationalPFCoeff_isPolyaFreqSeq
        {c : ℝ} (hc : 0 ≤ c) (r : ℕ)
        {alphas betas : List ℝ}
        (halphas : ∀ a ∈ alphas, 0 ≤ a)
        (hbetas : ∀ b ∈ betas, 0 ≤ b) :
        IsPolyaFreqSeq (rationalPFCoeff c r alphas betas)
  • Recurrence criterion for real roots via Pólya frequency Riordan arraysRealRooted original

    RealRooted.PFRiordan.recurrence_splits_and_roots_nonpossource
    theorem recurrence_splits_and_roots_nonpos
        {P : ℕ → ℝ[X]} {D₀ L N d K : ℕ → ℝ}
        (hD₀zero : D₀ 0 = 1)
        (hrec : ∀ n,
          ∑ j ∈ Finset.range (n + 1),
              (C (D₀ j) - X * C (L j)) * P (n - j) = C (N n))
        (hdIdentity : PowerSeries.mk D₀ * PowerSeries.mk d = PowerSeries.mk N)
        (hKIdentity :
          PowerSeries.X * PowerSeries.mk N * PowerSeries.mk K =
            PowerSeries.mk L)
        (hd : IsPolyaFreqSeq d) (hK : IsPolyaFreqSeq K) (n : ℕ) :
        (P n).Splits ∧ ∀ r ∈ (P n).roots, r ≤ 0
  • A114123 rows split with nonpositive rootsRealRooted original

    RealRooted.PFRiordan.a114123Row_splits_and_roots_nonpossource
    theorem a114123Row_splits_and_roots_nonpos (n : ℕ) :
        (a114123Row n).Splits ∧
          ∀ r ∈ (a114123Row n).roots, r ≤ 0
  • Even-binomial Riordan rows split with nonpositive rootsRealRooted original

    RealRooted.PFRiordan.evenBinomialRow_splits_and_roots_nonpossource
    theorem evenBinomialRow_splits_and_roots_nonpos (m : ℕ) :
        (evenBinomialRow m).Splits ∧
          ∀ r ∈ (evenBinomialRow m).roots, r ≤ 0

Lean source RealRooted/Challenges/PolyaFrequency/LeftProductionMatrix.lean at revision d6670742. Formalized 2026-11-10.