Recurrences with separated characteristic parameters
If a constant-coefficient recurrence has characteristic polynomial $\prod_i(T-a_i)-x\prod_j(T-b_j)$ with $a_i\ge0\ge b_j$, then its solutions from suitable initial rows are Pólya frequency polynomials and consecutive terms interlace. The criterion can be read off from the recurrence alone.
Results
Let $h\ge1$, $m\ge0$, $a\in\mathbb R^{h+m}$, $b\in\mathbb R^m$, and let $S$ be the shift $(SP)_n=P_{n+1}$. Consider the recurrence $$ \prod_{i=1}^{h+m}(S-a_i)\,P\;=\;x\prod_{j=1}^{m}(S-b_j)\,P. $$ Let $M=M(a,b)$ be the $(h+m)\times(h+m)$ matrix over $\mathbb R[x]$ whose first $h-1$ rows are bidiagonal (diagonal entry $a_i$, entry $1$ above it), and whose remaining rows have $x$ in column $0$, diagonal entry $a_i$, and entry $a_j-b_{j-h}$ in each column $j>i$, with $b_{j-h}$ read as $0$ for $j<h$. Then $$ \det(T-M)=\prod_i(T-a_i)-x\prod_j(T-b_j), $$ so every coordinate of $M^nv$ solves the recurrence. Conversely, if $(P_{s+n})_{n\ge0}$ solves it and $P_{s+r}=(M^rv)_i$ for $0\le r<h+m$, then $P_{s+n}=(M^nv)_i$ for all $n\ge0$.
Theorem. Assume $a_i\ge0\ge b_j$ for all $i,j$, or $a_i\ge\rho\ge b_j$ with $M$ built from $a_i-\rho$ and $b_j-\rho$. Then $M$ maps interlacing sequences of nonnegative real-rooted polynomials, zero entries allowed, to such sequences. If the seed $v$ is such a sequence, then every coordinate of every $M^nv$ is a Pólya frequency polynomial or zero, and $$ (M^nv)_i\ll(M^{n+1}v)_i\qquad\text{for all }n\ge0\text{ and all }i. $$
Proof
The determinant formula and the Cayley–Hamilton theorem give the recurrence. Under the sign conditions, $M$ has nonnegative polynomial coefficients and satisfies Brändén's criterion on the matrix interlacing page.
References
The preservation criterion is [Bra15, Thm. 7.8.5]; see the matrix interlacing page.
- [Bra15, Thm. 7.8.5] 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
The companion-type polynomial matrix of a separated-characteristic recurrence
def separatedCharacteristicFinMatrix {h m : ℕ}
(a : Fin (h + m) → ℝ) (b : Fin m → ℝ) :
Matrix (Fin (h + m)) (Fin (h + m)) ℝ[X] := fun i j ↦
if _hi : (i : ℕ) + 1 < h then
(if j = i then C (a i) else 0) +
if (j : ℕ) = i + 1 then 1 else 0
else
(if (j : ℕ) = 0 then X else 0) +
(if j = i then C (a i) else 0) +
if i < j then C (a j - separatedCharacteristicTailCoeff b j) else 0
Iterated rows of the matrix from a seed vector
def separatedCharacteristicRows {h m : ℕ}
(a : Fin (h + m) → ℝ) (b : Fin m → ℝ)
(seed : Fin (h + m) → ℝ[X]) : ℕ → Fin (h + m) → ℝ[X]
| 0 => seed
| n + 1 => (separatedCharacteristicFinMatrix a b).mulVec
(separatedCharacteristicRows a b seed n)
⊢ Theorems
The matrix preserves interlacing sequences when a_i ≥ 0 and b_j ≤ 0RealRooted original
theorem PreservesInterlacingSeq0.separatedCharacteristicMatrix {h m : ℕ}
{a : Fin (h + m) → ℝ} {b : Fin m → ℝ}
(ha : ∀ i, 0 ≤ a i) (hb : ∀ j, b j ≤ 0) :
PreservesInterlacingSeq0 (h + m) (RealRooted.separatedCharacteristicMatrix a b)
The shifted form: a_i ≥ ρ and b_j ≤ ρRealRooted original
theorem PreservesInterlacingSeq0.separatedCharacteristicMatrix_shift
{h m : ℕ} {a : Fin (h + m) → ℝ} {b : Fin m → ℝ} {ρ : ℝ}
(ha : ∀ i, ρ ≤ a i) (hb : ∀ j, b j ≤ ρ) :
PreservesInterlacingSeq0 (h + m)
(RealRooted.separatedCharacteristicMatrix (fun i ↦ a i - ρ) (fun j ↦ b j - ρ))
Every coordinate of every iterate of an ordered PF seed is a PF polynomialRealRooted original
theorem separatedCharacteristicRows_isPFPolynomial {h m : ℕ}
{a : Fin (h + m) → ℝ} {b : Fin m → ℝ}
(ha : ∀ i, 0 ≤ a i) (hb : ∀ j, b j ≤ 0)
{seed : Fin (h + m) → ℝ[X]}
(hseed : IsInterlacingSeq0NonnegRealRooted (List.ofFn seed))
(n : ℕ) (i : Fin (h + m)) :
IsPFPolynomial (separatedCharacteristicRows a b seed n i)
Each coordinate interlaces the same coordinate after one stepMain resultRealRooted original
theorem separatedCharacteristicRows_interl_succ {h m : ℕ}
{a : Fin (h + m) → ℝ} {b : Fin m → ℝ}
(ha : ∀ i, 0 ≤ a i) (hb : ∀ j, b j ≤ 0)
{seed : Fin (h + m) → ℝ[X]}
(hseed : IsInterlacingSeq0NonnegRealRooted (List.ofFn seed))
(n : ℕ) (i : Fin (h + m)) :
Interl (separatedCharacteristicRows a b seed n i)
(separatedCharacteristicRows a b seed (n + 1) i)
Iterates of an interlacing seed remain interlacing sequencesRealRooted original
theorem separatedCharacteristicRows_interlacing {h m : ℕ}
{a : Fin (h + m) → ℝ} {b : Fin m → ℝ}
(ha : ∀ i, 0 ≤ a i) (hb : ∀ j, b j ≤ 0)
{seed : Fin (h + m) → ℝ[X]}
(hseed : IsInterlacingSeq0NonnegRealRooted (List.ofFn seed)) (n : ℕ) :
IsInterlacingSeq0NonnegRealRooted
(List.ofFn (separatedCharacteristicRows a b seed n))
The characteristic polynomial is ∏(T - a_i) - X ∏(T - b_j)RealRooted original
theorem separatedCharacteristicFinMatrix_charpoly {h m : ℕ} (hh : 0 < h)
(a : Fin (h + m) → ℝ) (b : Fin m → ℝ) :
(separatedCharacteristicFinMatrix a b).charpoly =
∏ i, (X - C (C (a i))) -
C (X : ℝ[X]) * ∏ j, (X - C (C (b j)))
A scalar solution with matching initial rows is a coordinate of the matrix orbitRealRooted original
theorem eq_separatedCharacteristicRows_coordinate_from {h m : ℕ}
(a : Fin (h + m) → ℝ) (b : Fin m → ℝ)
(seed : Fin (h + m) → ℝ[X]) (i : Fin (h + m))
(P : ℕ → ℝ[X]) (start : ℕ)
(hP : (LinearRecurrence.ofMatrix
(separatedCharacteristicFinMatrix a b)).IsSolution
(fun n ↦ P (start + n)))
(hinitial : ∀ r < h + m,
P (start + r) = separatedCharacteristicRows a b seed r i) :
∀ n, P (start + n) = separatedCharacteristicRows a b seed n i
Lean source RealRooted/Challenges/Matrices/SeparatedCharacteristicRecurrence.lean at revision d6670742. Formalized 2026-11-01.