A TP2 constant matrix preserves interlacing sequences with nonnegative coefficientsRealRooted original
theorem IsTP2.map_interlacingSeq
{m n : ℕ} {A : Matrix (Fin m) (Fin n) ℝ}
(hA : A.IsTP2) (fs : List ℝ[X])
(hfs_len : fs.length = n) (hfs : IsInterlacingSeqNonneg fs) :
IsInterlacingSeqNonneg ((tnnMatrixAction A fs).filter (· ≠ 0))
The affine step (A + b X J) f preserves ordered interlacingRealRooted original
theorem _root_.Matrix.IsTP2.interlacingSeqNonneg_cons_tp2AffineStep
{A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ} (hA : A.IsTP2)
(hcol : ∀ ⦃i k j : Fin (n + 1)⦄, i ≤ k → A k j ≤ A i j) {b : ℝ} (hb : 0 ≤ b)
{f : Fin (n + 1) → ℝ[X]} (hf : IsInterlacingSeqNonneg (List.ofFn f))
(hne : ∀ i, tp2AffineStep A b f i ≠ 0) :
IsInterlacingSeqNonneg (f 0 :: List.ofFn (tp2AffineStep A b f))
The rows are the coefficients of the inverse of det (I + z A) - t zRealRooted original
theorem hessenbergDenominator_mul_mk_hessenbergRow
(A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ) :
hessenbergDenominator A * PowerSeries.mk (hessenbergRow A) = 1
P_k(t) = (-1)^k f_{k,1}(-t)RealRooted original
theorem hessenbergRow_eq (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ)
(hrow : ∀ ⦃i j : Fin (n + 1)⦄, i ≤ j → A i j = A j j) (k : ℕ) :
hessenbergRow A k = C ((-1 : ℝ) ^ k) * (hessenbergVector A k 0).comp (-X)
Every stage of the vector recursion is an interlacing sequenceRealRooted original
theorem isInterlacingSeqNonneg_hessenbergVector {A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ}
(hA : A.IsTP2) (hcol : ∀ ⦃i k j : Fin (n + 1)⦄, i ≤ k → A k j ≤ A i j) (k : ℕ) :
IsInterlacingSeqNonneg (List.ofFn (hessenbergVector A k))
The rows are monic, have nonnegative real roots and interlaceMain resultRealRooted original
theorem hessenbergRow_certificate {A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ}
(hA : A.IsTP2) (hcol : ∀ ⦃i k j : Fin (n + 1)⦄, i ≤ k → A k j ≤ A i j)
(hrow : ∀ ⦃i j : Fin (n + 1)⦄, i ≤ j → A i j = A j j) (k : ℕ) :
(hessenbergRow A k).Monic ∧ (hessenbergRow A k).natDegree = k ∧
IsRealRootedIn (Set.Ici 0) (hessenbergRow A k) ∧
Interlaces (hessenbergRow A k) (hessenbergRow A (k + 1))
The rows of [[1, 1], [0, 1]] begin 1, t - 2, (t - 1)(t - 3)RealRooted original
theorem hessenbergRow_exampleTwo :
hessenbergRow hessenbergExampleTwo 0 = 1 ∧ hessenbergRow hessenbergExampleTwo 1 = X - 2 ∧
hessenbergRow hessenbergExampleTwo 2 = (X - 1) * (X - 3)
det B = B_dd prod (B_ii - B_{i+1,i}) for a matrix with constant upper-triangular columnsRealRooted original
theorem det_eq_last_mul_prod_of_forall_le {B : Matrix (Fin (n + 1)) (Fin (n + 1)) R}
(hB : ∀ ⦃i j : Fin (n + 1)⦄, i ≤ j → B i j = B j j) :
B.det = B (Fin.last n) (Fin.last n) *
∏ i : Fin n, (B i.castSucc i.castSucc - B i.succ i.castSucc)
det (A + r J) = det A for d >= 2RealRooted original
theorem det_add_smul_runJ_eq {A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ} (hn : n ≠ 0)
(hrow : ∀ ⦃i j : Fin (n + 1)⦄, i ≤ j → A i j = A j j) (r : ℝ) :
(A + r • runJ n ℝ).det = A.det
The vector recursion evaluated at r is (A + r J)^k 1RealRooted original
theorem eval_hessenbergVector (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ) (r : ℝ) (k : ℕ) :
(fun i => (hessenbergVector A k i).eval r) = (A + r • runJ n ℝ) ^ k *ᵥ fun _ => 1
A simple root of f_{k,1} is not a root of f_{k+1,1}RealRooted original
theorem not_isRoot_hessenbergVector_succ_zero (hA : A.IsTP2)
(hcol : ∀ ⦃i k j : Fin (n + 1)⦄, i ≤ k → A k j ≤ A i j)
(hrow : ∀ ⦃i j : Fin (n + 1)⦄, i ≤ j → A i j = A j j) (hn : n ≠ 0) (hdet : 0 < A.det)
(k : ℕ) (hsimple : HasSimpleRoots (hessenbergVector A k 0)) {r : ℝ}
(hr : (hessenbergVector A k 0).IsRoot r) : ¬ (hessenbergVector A (k + 1) 0).IsRoot r
Every f_{k,1} has simple rootsRealRooted original
theorem hasSimpleRoots_hessenbergVector_zero (hA : A.IsTP2)
(hcol : ∀ ⦃i k j : Fin (n + 1)⦄, i ≤ k → A k j ≤ A i j)
(hrow : ∀ ⦃i j : Fin (n + 1)⦄, i ≤ j → A i j = A j j) (hn : n ≠ 0) (hdet : 0 < A.det)
(k : ℕ) : HasSimpleRoots (hessenbergVector A k 0)
For d >= 2 and det A > 0: simple positive roots, no common roots of consecutive rowsRealRooted original
theorem hessenbergRow_strict (hA : A.IsTP2)
(hcol : ∀ ⦃i k j : Fin (n + 1)⦄, i ≤ k → A k j ≤ A i j)
(hrow : ∀ ⦃i j : Fin (n + 1)⦄, i ≤ j → A i j = A j j) (hn : n ≠ 0) (hdet : 0 < A.det)
(k : ℕ) :
HasSimpleRoots (hessenbergRow A k) ∧ (∀ r, (hessenbergRow A k).IsRoot r → 0 < r) ∧
∀ r, ¬ ((hessenbergRow A k).IsRoot r ∧ (hessenbergRow A (k + 1)).IsRoot r)
The rows of [[1, 1], [0, 1]] are strictly interlacingRealRooted original
theorem hessenbergRow_exampleTwo_strict (k : ℕ) :
HasSimpleRoots (hessenbergRow hessenbergExampleTwo k) ∧
(∀ r, (hessenbergRow hessenbergExampleTwo k).IsRoot r → 0 < r) ∧
∀ r, ¬ ((hessenbergRow hessenbergExampleTwo k).IsRoot r ∧
(hessenbergRow hessenbergExampleTwo (k + 1)).IsRoot r)
Transfer identity: Z_N = e_1^T (J + z A) ... (J + z A) 1RealRooted original
theorem siteWeightedRuns_runKernel (A : Matrix (Fin (n + 1)) (Fin (n + 1)) R) {N : ℕ}
(z : Fin N → R) : siteWeightedRuns (runKernel A) z = runVector A N z 0
For the kernel u = 1 the run sum is the product of (1 + z_i)RealRooted original
theorem siteWeightedRuns_one_by_one {R : Type*} [CommSemiring R] {N : ℕ} (z : Fin N → R) :
siteWeightedRuns (fun _ : ℕ => (1 : R)) z = ∏ i, (1 + z i)
The transfer vector is the reflection of the affine vector for the matrices a_k ARealRooted original
theorem runVector_eq_reflect_affineVector (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ)
(a : ℕ → ℝ) (N : ℕ) (j : Fin (n + 1)) :
runVector (A.map C) N (fun i : Fin N => C (a i) * X) j =
reflect N (affineVector (fun k => a k • A) N j)
B_N is real-rooted with all roots negativeRealRooted original
theorem isRealRootedIn_Iio_siteWeightedRunPolynomial (hA : A.IsTP2)
(hcol : ∀ ⦃i i' j : Fin (n + 1)⦄, i ≤ i' → A i' j ≤ A i j) (ha : ∀ k, 0 ≤ a k)
(hu : ∀ k, u k = runKernel A k) (N : ℕ) :
IsRealRootedIn (Set.Iio 0) (siteWeightedRunPolynomial u a N)
Consecutive B_N, B_{N+1} interlaceRealRooted original
theorem strictInterl_siteWeightedRunPolynomial (hA : A.IsTP2)
(hcol : ∀ ⦃i i' j : Fin (n + 1)⦄, i ≤ i' → A i' j ≤ A i j) (ha : ∀ k, 0 ≤ a k)
(hu : ∀ k, u k = runKernel A k) (N : ℕ) :
StrictInterl (siteWeightedRunPolynomial u a N) (siteWeightedRunPolynomial u a (N + 1))
B_N(0) = 1, nonnegative coefficients, negative real roots, B_N interlaces B_{N+1}RealRooted original
theorem siteWeightedRunPolynomial_certificate (hA : A.IsTP2)
(hcol : ∀ ⦃i i' j : Fin (n + 1)⦄, i ≤ i' → A i' j ≤ A i j) (ha : ∀ k, 0 ≤ a k)
(hu : ∀ k, u k = runKernel A k) (N : ℕ) :
(siteWeightedRunPolynomial u a N).coeff 0 = 1 ∧
(siteWeightedRunPolynomial u a N).natDegree ≤ N ∧
HasNonnegCoeffs (siteWeightedRunPolynomial u a N) ∧
IsRealRootedIn (Set.Iio 0) (siteWeightedRunPolynomial u a N) ∧
StrictInterl (siteWeightedRunPolynomial u a N) (siteWeightedRunPolynomial u a (N + 1))
Cauchy-Binet for the Wronskian of two linear combinationsRealRooted original
theorem le_eval_wronskian_sum_sum {m : ℕ} (a b : Fin m → ℝ) (h : Fin m → ℝ[X]) (x : ℝ)
(hnn : ∀ k ℓ, k < ℓ → 0 ≤ (a k * b ℓ - a ℓ * b k) * (wronskian (h k) (h ℓ)).eval x)
{k₀ ℓ₀ : Fin m} (hk : k₀ < ℓ₀) :
(a k₀ * b ℓ₀ - a ℓ₀ * b k₀) * (wronskian (h k₀) (h ℓ₀)).eval x ≤
(wronskian (∑ k, C (a k) * h k) (∑ k, C (b k) * h k)).eval x
The Wronskian of the Hessenberg step dominates each 2 x 2 minor termRealRooted original
theorem le_eval_wronskian_hessenbergVector_succ {A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ}
(hA : A.IsTP2) (hcol : ∀ ⦃i k j : Fin (n + 1)⦄, i ≤ k → A k j ≤ A i j) (k : ℕ)
{i j a b : Fin (n + 1)} (hij : i < j) (hab : a < b) (x : ℝ) :
(A i a * A j b - A i b * A j a) *
(wronskian (hessenbergVector A k a) (hessenbergVector A k b)).eval x ≤
(wronskian (hessenbergVector A (k + 1) i) (hessenbergVector A (k + 1) j)).eval x
The block matrix is TP2 with decreasing columnsRealRooted original
lemma parityBlock_isTP2 (hA : A.IsTP2)
(hcol : ∀ ⦃i k j : Fin (n + 1)⦄, i ≤ k → A k j ≤ A i j) : (parityBlock A).IsTP2
det (I + X B) = det (I + X A)^2 for the block matrix BRealRooted original
theorem hessenbergDet_parityBlock (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ) :
hessenbergDet (n := n + 1 + n) (parityBlock A) = hessenbergDet A ^ 2
The first coordinate of the second block has series G(z) times the first coordinate seriesRealRooted original
theorem hessenbergSeries_parityBlock_natAdd_zero (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ)
(hrow : ∀ ⦃i j : Fin (n + 1)⦄, i ≤ j → A i j = A j j) :
hessenbergSeries (n := n + 1 + n) (parityBlock A) (parityIndex n) =
hessenbergCoeffs (hessenbergDet A) * hessenbergSeries (n := n + 1 + n) (parityBlock A) 0
Even rows: P_{2m}(t) = V_m(t^2)RealRooted original
theorem parityRow_zero_two_mul (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ) (m : ℕ) :
parityRow A 0 (2 * m) = Polynomial.expand ℝ 2 (PowerSeries.coeff m (parityV A))
Odd rows: P_{2m+1}(t) = t U_m(t^2)RealRooted original
theorem parityRow_zero_two_mul_add_one (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ) (m : ℕ) :
parityRow A 0 (2 * m + 1) =
X * Polynomial.expand ℝ 2 (hessenbergRow (n := n + 1 + n) (parityBlock A) m)
The shift: P_n^gamma(t) = P_n^0(t - gamma)RealRooted original
theorem parityRow_eq_comp (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ) (γ : ℝ) (k : ℕ) :
parityRow A γ k = (parityRow A 0 k).comp (X - C γ)
The Wronskian of the two first coordinates is bounded below by c_0^{2m} sRealRooted original
theorem le_eval_wronskian_parityBlock (m : ℕ) (x : ℝ) :
A 0 0 ^ (2 * m) * ∑ j, A 0 j ≤
(wronskian (hessenbergVector (n := n + 1 + n) (parityBlock A) (m + 1) 0)
(hessenbergVector (n := n + 1 + n) (parityBlock A) (m + 1) (parityIndex n))).eval x
f_{m,1} and f_{m+1,q+1} have no common rootRealRooted original
theorem not_isRoot_parityVector_zero_succ_index (m : ℕ) (r : ℝ)
(hr0 : (parityVector A m 0).IsRoot r) :
¬ (parityVector A (m + 1) (parityIndex n)).IsRoot r
Parity rows are monic, real-rooted with simple roots, strictly interlacingRealRooted original
theorem parityRow_certificate_of_natDegree_ne_zero :
∀ {n : ℕ} {A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ}, A.IsTP2 →
(∀ ⦃i k j : Fin (n + 1)⦄, i ≤ k → A k j ≤ A i j) →
(∀ ⦃i j : Fin (n + 1)⦄, i ≤ j → A i j = A j j) →
(hessenbergDet A).natDegree ≠ 0 → ∀ (γ : ℝ) (k : ℕ),
(parityRow A γ k).Monic ∧ (parityRow A γ k).natDegree = k ∧ (parityRow A γ k).Splits ∧
HasSimpleRoots (parityRow A γ k) ∧
Interlaces (parityRow A γ k) (parityRow A γ (k + 1)) ∧
IsCoprime (parityRow A γ k) (parityRow A γ (k + 1))
A 4 × 4 matrix satisfying the hypotheses whose G is not real-rootedRealRooted original
theorem parityRow_certificate_seed (γ : ℝ) (k : ℕ) :
(parityRow parityExampleSeed γ k).Monic ∧ (parityRow parityExampleSeed γ k).natDegree = k ∧
(parityRow parityExampleSeed γ k).Splits ∧ HasSimpleRoots (parityRow parityExampleSeed γ k) ∧
Interlaces (parityRow parityExampleSeed γ k) (parityRow parityExampleSeed γ (k + 1)) ∧
IsCoprime (parityRow parityExampleSeed γ k) (parityRow parityExampleSeed γ (k + 1))