Operator matrices preserving ordered PF vectors

A matrix of linear operators on polynomials preserves ordered Pólya frequency vectors if and only if every $2\times2$ submatrix does. For entries among $1$, $\theta=x\,d/dx$ and $x$, exactly thirteen $2\times2$ blocks do, which decides which operator recurrences of this kind have interlacing PF rows.

Results

A polynomial is PF if it has nonnegative coefficients and is zero or has only real, nonpositive roots. On this page $f\ll g$ also holds when $f$ or $g$ is zero, as in the zero-aware convention. A vector $(f_1,\dotsc,f_n)$ is an ordered PF vector if every $f_i$ is PF and $f_i\ll f_k$ for $i<k$.

An $m\times n$ operator matrix $M=(M_{ij})$ has real-linear operators on $\mathbb R[x]$ as entries and acts by $(Mf)_i=\sum_j M_{ij}f_j$. It preserves ordered PF vectors if $Mf$ is an ordered PF vector whenever $f$ is. A block $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ preserves ordered PF pairs if, for all PF $f\ll g$, the polynomials $af+bg$ and $cf+dg$ are PF and $af+bg\ll cf+dg$.

Theorem (local to global). Let $m,n\ge2$. Then $M$ preserves ordered PF vectors if and only if every $2\times2$ submatrix on rows $i<k$ and columns $j<l$, adjacent or not, preserves ordered PF pairs. A $2\times2$ matrix preserves ordered PF vectors if and only if its four entries form a block preserving ordered PF pairs, and products of matrices that preserve ordered PF vectors preserve them.

Theorem (blocks over $\{1,\theta,x\}$). Let the entries be the identity $1$, the operator $\theta$ and multiplication by $x$. A $2\times2$ block over this alphabet preserves ordered PF pairs if and only if it is one of the following thirteen, written as (top row)/(bottom row):

Hence an $m\times n$ matrix over $\{1,\theta,x\}$ with $m,n\ge2$ preserves ordered PF vectors if and only if every $2\times2$ submatrix is one of the thirteen blocks. A one-row matrix does if and only if its entries weakly decrease from left to right in the order $1<\theta<x$, and a one-column matrix if and only if its entries weakly increase from top to bottom. For $m,n\ge2$, a matrix over $\{1,\theta\}$ does exactly when its entries equal to $1$ form an upper-right rectangle, possibly empty ($mn+1$ matrices), and a matrix over $\{\theta,x\}$ does exactly when all rows are equal, with $x$ columns followed by $\theta$ columns, or all columns are equal, with $\theta$ rows followed by $x$ rows ($m+n$ matrices).

Proposition. For PF polynomials $p$ and $q$:

Corollary (Euler-derivative lag recurrence). Let $P_{n+2}=\theta P_{n+1}+x\,\theta P_n$. The matrix $$ \begin{pmatrix}x\theta&\theta\\ x(\theta^2+\theta)&x\theta+\theta^2\end{pmatrix} $$ sends $(P_n,P_{n+1})$ to $(P_{n+2},P_{n+3})$ and preserves ordered PF vectors. Among the nine transitions between the lag factors $1$, $\theta$ and $x$, exactly the two alternating identity/Euler transitions preserve ordered PF vectors. If $P_0=1$ and $P_1=x$, then every $P_n$ is real-rooted.

For couplings of two first-order blocks $a+b\theta+cx+e\,x(N-\theta)$, a scalar criterion on the negative ray with a weight $w\ge0$ reduces to explicit inequalities. For the pair $(\theta,\,x(N-\theta))$ it holds exactly when $N^2\le4w$, and for the reversed pair, with $N\ge1$, exactly when $(N-1)^2\le4w$.

References

Definitions

  • Ordered PF vector

    RealRooted.OperatorMatrix.IsOrderedPFsource
    def IsOrderedPF {n : ℕ} (f : Fin n → ℝ[X]) : Prop :=
      (∀ i, IsPFPolynomial (f i)) ∧ ∀ i k, i < k → Interl (f i) (f k)
  • An operator matrix preserves ordered PF vectors

    RealRooted.OperatorMatrix.PreservesOrderedPFsource
    def PreservesOrderedPF {m n : ℕ} (M : Fin m → Fin n → ℝ[X] →ₗ[ℝ] ℝ[X]) : Prop :=
      ∀ f, IsOrderedPF f → IsOrderedPF (apply M f)
  • A two-by-two operator block preserves ordered PF pairs

    RealRooted.OperatorMatrix.PreservesOrderedPFPairsource
    def PreservesOrderedPFPair
        (a b c d : ℝ[X] →ₗ[ℝ] ℝ[X]) : Prop :=
      ∀ f g, IsPFPolynomial f → IsPFPolynomial g → Interl f g →
        IsPFPolynomial (a f + b g) ∧ IsPFPolynomial (c f + d g) ∧
          Interl (a f + b g) (c f + d g)
  • The alphabet {1, θ, X}

    RealRooted.OperatorMatrix.Lettersource
    inductive Letter where
      | one
      | theta
      | x
      deriving DecidableEq, Repr
  • The thirteen allowed two-by-two blocks over {1, θ, X}

    RealRooted.OperatorMatrix.Letter.IsAllowedBlocksource
    def Letter.IsAllowedBlock : Letter → Letter → Letter → Letter → Prop
      | .one, .one, .one, .one => True
      | .one, .one, .theta, .theta => True
      | .one, .one, .x, .one => True
      | .one, .one, .x, .x => True
      | .theta, .one, .theta, .one => True
      | .theta, .one, .theta, .theta => True
      | .theta, .one, .x, .theta => True
      | .theta, .theta, .theta, .theta => True
      | .theta, .theta, .x, .x => True
      | .x, .one, .x, .one => True
      | .x, .one, .x, .x => True
      | .x, .theta, .x, .theta => True
      | .x, .x, .x, .x => True
      | _, _, _, _ => False
  • The scalar ray predicate for a coupling of two first-order operator blocks

    RealRooted.OperatorMatrix.CouplingRayCriterionsource
    def CouplingRayCriterion (J S : ℝ → ℝ) (w : ℝ) : Prop :=
      ∀ t, 0 < t →
        (0 ≤ S t ∨ (S t) ^ 2 ≤ 4 * w * t * J t) ∧
          (S t ≤ J t ∨ (J t - S t) ^ 2 ≤ 4 * w * t * J t)

Theorems

  • Local-to-global: ordered-PF preservation reduces to two-by-two blocksRealRooted original

    RealRooted.OperatorMatrix.PreservesOrderedPF.iff_forall_blocks_of_two_lesource
    theorem PreservesOrderedPF.iff_forall_blocks_of_two_le {m n : ℕ}
        (M : Fin m → Fin n → ℝ[X] →ₗ[ℝ] ℝ[X]) (hm : 2 ≤ m) (hn : 2 ≤ n) :
        PreservesOrderedPF M ↔
          ∀ i k j l, i < k → j < l → PreservesBlock M i k j l
  • A two-by-two block over {1, θ, X} preserves ordered PF pairs iff it is one of thirteenRealRooted original

    RealRooted.OperatorMatrix.PreservesOrderedPFPair.iff_isAllowedBlocksource
    theorem PreservesOrderedPFPair.iff_isAllowedBlock (a b c d : Letter) :
        PreservesOrderedPFPair a.linearMap b.linearMap c.linearMap d.linearMap ↔
          a.IsAllowedBlock b c d
  • Classification of ordered-PF preserving matrices over {1, θ, X}Main resultRealRooted original

    RealRooted.OperatorMatrix.PreservesOrderedPF.letters_iffsource
    theorem PreservesOrderedPF.letters_iff {m n : ℕ} (L : Fin m → Fin n → Letter)
        (hm : 2 ≤ m) (hn : 2 ≤ n) :
        PreservesOrderedPF (fun i j => (L i j).linearMap) ↔
          ∀ i k j l, i < k → j < l → (L i j).IsAllowedBlock (L i l) (L k j) (L k l)
  • Mixed differential lemma: p' + q' ≪ q + X p' for PF p ≪ qRealRooted original

    RealRooted.interl_derivative_add_derivative_add_X_mul_derivativesource
    theorem interl_derivative_add_derivative_add_X_mul_derivative {p q : ℝ[X]}
        (hp : IsPFPolynomial p) (hq : IsPFPolynomial q) (hpq : Interl p q) :
        Interl (p.derivative + q.derivative) (q + X * p.derivative)
  • X-duality: p ≪ q if and only if q ≪ X p for PF p and qRealRooted original

    RealRooted.interl_iff_interl_X_mulsource
    theorem interl_iff_interl_X_mul {p q : ℝ[X]}
        (hp : IsPFPolynomial p) (hq : IsPFPolynomial q) :
        Interl p q ↔ Interl q (X * p)
  • p ≪ q gives p + q ≪ X p + q for PF p and qRealRooted original

    RealRooted.interl_add_X_mul_add_of_interlsource
    theorem interl_add_X_mul_add_of_interl {p q : ℝ[X]}
        (hp : IsPFPolynomial p) (hq : IsPFPolynomial q) (hpq : Interl p q) :
        Interl (p + q) (X * p + q)
  • A two-by-two operator matrix preserves ordered PF vectors iff its block doesRealRooted original

    RealRooted.OperatorMatrix.PreservesOrderedPF.two_two_iffsource
    theorem PreservesOrderedPF.two_two_iff
        (M : Matrix (Fin 2) (Fin 2) (Module.End ℝ ℝ[X])) :
        PreservesOrderedPF M ↔ PreservesOrderedPFPair (M 0 0) (M 0 1) (M 1 0) (M 1 1)
  • Products of ordered-PF preserving matrices preserve ordered PF vectorsRealRooted original

    RealRooted.OperatorMatrix.PreservesOrderedPF.mulsource
    protected theorem PreservesOrderedPF.mul {m n r : ℕ}
        {A : Matrix (Fin m) (Fin n) (Module.End ℝ ℝ[X])}
        {B : Matrix (Fin n) (Fin r) (Module.End ℝ ℝ[X])}
        (hA : PreservesOrderedPF A) (hB : PreservesOrderedPF B) :
        PreservesOrderedPF (A * B)
  • Boards over {1, θ}: the 1 entries form an upper-right rectangleRealRooted original

    RealRooted.OperatorMatrix.PreservesOrderedPF.one_theta_iff_upperRightRectanglesource
    theorem PreservesOrderedPF.one_theta_iff_upperRightRectangle
        {m n : ℕ} (L : Fin m → Fin n → Letter)
        (hm : 2 ≤ m) (hn : 2 ≤ n) (halpha : IsOneThetaMatrix L) :
        PreservesOrderedPF (fun i j ↦ (L i j).linearMap) ↔
          OnesFormUpperRightRectangle L
  • Boards over {θ, X}: a row cut or a column cutRealRooted original

    RealRooted.OperatorMatrix.PreservesOrderedPF.theta_x_iff_rowCut_or_columnCutsource
    theorem PreservesOrderedPF.theta_x_iff_rowCut_or_columnCut
        {m n : ℕ} (L : Fin m → Fin n → Letter)
        (hm : 2 ≤ m) (hn : 2 ≤ n) (halpha : IsThetaXMatrix L) :
        PreservesOrderedPF (fun i j ↦ (L i j).linearMap) ↔
          XsFormLeftColumns L ∨ XsFormBottomRows L
  • One-row matrices over {1, θ, X}: entries weakly decrease from left to rightRealRooted original

    RealRooted.OperatorMatrix.PreservesOrderedPF.one_row_letters_iffsource
    theorem PreservesOrderedPF.one_row_letters_iff {n : ℕ}
        (L : Fin 1 → Fin n → Letter) :
        PreservesOrderedPF (fun i j => (L i j).linearMap) ↔
          IsWeaklyDecreasingLetterRow L
  • One-column matrices over {1, θ, X}: entries weakly increase from top to bottomRealRooted original

    RealRooted.OperatorMatrix.PreservesOrderedPF.one_column_letters_iffsource
    theorem PreservesOrderedPF.one_column_letters_iff {m : ℕ}
        (L : Fin m → Fin 1 → Letter) :
        PreservesOrderedPF (fun i j => (L i j).linearMap) ↔
          IsWeaklyIncreasingLetterColumn L
  • There are exactly m n + 1 boards over {1, θ}RealRooted original

    RealRooted.OperatorMatrix.card_oneThetaRectangleBoardssource
    theorem card_oneThetaRectangleBoards (m n : ℕ) :
        (oneThetaRectangleBoards m n).card = m * n + 1
  • There are exactly m + n boards over {θ, X}RealRooted original

    RealRooted.OperatorMatrix.card_thetaXCutBoardssource
    theorem card_thetaXCutBoards {m n : ℕ} (hm : 2 ≤ m) (hn : 2 ≤ n) :
        (thetaXCutBoards m n).card = m + n
  • The matrix of P(n+2) = θP(n+1) + Xθ P(n) preserves ordered PF vectorsRealRooted original

    RealRooted.OperatorMatrix.PreservesOrderedPF.eulerDerivativeLag_twoStepsource
    theorem _root_.RealRooted.OperatorMatrix.PreservesOrderedPF.eulerDerivativeLag_twoStep
        : PreservesOrderedPF twoStep
  • Exactly the two alternating identity/Euler transitions preserve ordered PF vectorsRealRooted original

    RealRooted.OperatorMatrix.PreservesOrderedPF.eulerDerivativeLag_transition_iffsource
    theorem _root_.RealRooted.OperatorMatrix.PreservesOrderedPF.eulerDerivativeLag_transition_iff
        (source target : FactorLabel) :
        PreservesOrderedPF (transition source target) ↔
          (source = .euler ∧ target = .identity) ∨
            (source = .identity ∧ target = .euler)
  • Every row of P(n+2) = θP(n+1) + Xθ P(n) with P(0) = 1, P(1) = X splitsRealRooted original

    RealRooted.OperatorMatrix.EulerDerivativeLag.splits_of_recurrence_one_Xsource
    theorem splits_of_recurrence_one_X (P : ℕ → ℝ[X])
        (hrec : ∀ k, P (k + 2) = RealRooted.theta (P (k + 1)) + X * RealRooted.theta (P k))
        (hzero : P 0 = 1) (hone : P 1 = X) (n : ℕ) : (P n).Splits
  • The ray criterion is equivalent to -2√(wtJ) ≤ S ≤ J + 2√(wtJ) for all t > 0RealRooted original

    RealRooted.OperatorMatrix.couplingRayCriterion_iff_sqrt_boundssource
    theorem couplingRayCriterion_iff_sqrt_bounds (J S : ℝ → ℝ) (w : ℝ)
        (hrad : ∀ t, 0 < t → 0 ≤ w * t * J t) :
        CouplingRayCriterion J S w ↔
          ∀ t, 0 < t →
            -2 * Real.sqrt (w * t * J t) ≤ S t ∧
              S t ≤ J t + 2 * Real.sqrt (w * t * J t)
  • For quadratic data on the boundary of the parameter cone the ray quantifier is eliminatedRealRooted original

    RealRooted.OperatorMatrix.couplingRayCriterion_quadratic_iff_of_boundarysource
    theorem couplingRayCriterion_quadratic_iff_of_boundary
        {j₀ j₁ j₂ s₀ s₁ s₂ w : ℝ}
        (hw : 0 ≤ w) (hj₀ : 0 ≤ j₀) (hj₂ : 0 ≤ j₂)
        (hs₀ : 0 ≤ s₀) (hs₀j : s₀ ≤ j₀) (hs₂ : 0 ≤ s₂) (hs₂j : s₂ ≤ j₂)
        (hboundary : j₀ * j₂ = 0) :
        CouplingRayCriterion
            (fun t ↦ j₀ + j₁ * t + j₂ * t ^ 2)
            (fun t ↦ s₀ + s₁ * t + s₂ * t ^ 2) w ↔
          (0 ≤ s₁ ∨ s₁ ^ 2 ≤ 4 * w * j₁) ∧
            (s₁ ≤ j₁ ∨ (j₁ - s₁) ^ 2 ≤ 4 * w * j₁)
  • Raising the degree cap does not change the criterion for proportional blocksRealRooted original

    RealRooted.OperatorMatrix.couplingRayCriterion_cap_add_of_proportionalsource
    theorem couplingRayCriterion_cap_add_of_proportional (N d : ℕ)
        (p₁ p₂ : CouplingDiagonal) (w : ℝ)
        (hprop : p₂.b * p₁.e = p₁.b * p₂.e) :
        CouplingRayCriterion (couplingJ p₁ p₂) (couplingS (N + d) p₁ p₂) w ↔
          CouplingRayCriterion (couplingJ p₁ p₂) (couplingS N p₁ p₂) w
  • The (θ, polar) coupling holds exactly when N² ≤ 4wRealRooted original

    RealRooted.OperatorMatrix.rayCriterion_theta_polar_iffsource
    theorem rayCriterion_theta_polar_iff (N : ℕ) (w : ℝ) (hw : 0 ≤ w) :
        CouplingRayCriterion (fun t ↦ t) (fun t ↦ -(N : ℝ) * t) w ↔
          (N : ℝ) ^ 2 ≤ 4 * w

Lean source RealRooted/Challenges/Preservers/OperatorMatrices.lean at revision d6670742. Formalized 2026-11-03.