Hessenberg rows of TP2 matrices

For a TP2 matrix $A$ with weakly decreasing columns and constant upper triangles, the coefficients $P_k(t)$ of $1/(\det(I+zA)-tz)$ have nonnegative real roots and consecutive ones interlace. The same holds for run polynomials with weights from $A$ and for the parity-lifted rows of $1/(\det(I+z^2A)+\gamma z-tz)$, although $\det(I+zA)$ need not be real-rooted.

Results

A real matrix $A$ is TP2 if all its entries and all its ordered $2\times2$ minors $A_{i_1j_1}A_{i_2j_2}-A_{i_1j_2}A_{i_2j_1}$, $i_1<i_2$, $j_1<j_2$, are nonnegative. Let $A$ be a real $d\times d$ matrix such that

  1. $A$ is TP2,
  2. every column of $A$ is weakly decreasing down the rows, and
  3. $A_{ij}=A_{jj}$ whenever $i\le j$.

Put $F(z)=\det(I+zA)$ and define $P_k(t)$ by $$ \sum_{k\ge0}P_k(t)\,z^k=\frac{1}{F(z)-tz}. $$

Theorem. Every $P_k$ is monic of degree $k$ with only real nonnegative roots, and $P_k\ll P_{k+1}$. If moreover $d\ge2$ and $\det A>0$, then every $P_k$ has simple positive roots, and $P_k$ and $P_{k+1}$ have no common root.

For $d=1$ and $A=(c)$ the rows are $(t-c)^k$, so the condition $d\ge2$ cannot be dropped. For $A=\begin{pmatrix}1&1\\0&1\end{pmatrix}$ the rows begin $1,\ t-2,\ (t-1)(t-3)$.

Theorem (run polynomials). Let $A$ satisfy conditions 1 and 2, let $u_k=e_1^{\mathsf T}A^k\mathbf 1$ and let $a_1,\dots,a_N\ge0$. Put $$ B_N(t)=\sum_{S\subseteq[N]}\Bigl(\prod_{R}u_{|R|}\Bigr)\prod_{i\in S}a_it, $$ where $R$ runs over the maximal intervals of consecutive elements of $S$. Then $B_N(0)=1$, $B_N$ has nonnegative coefficients and only negative real roots, and $B_N\ll B_{N+1}$.

For $u_k=1$ this is $B_N(t)=\prod_i(1+a_it)$.

Theorem (parity rows). Let $A$ satisfy conditions 1–3, assume that $F$ is nonconstant, and for $\gamma\in\mathbb R$ define $P_n^\gamma(t)$ by $$ \sum_{n\ge0}P_n^\gamma(t)\,z^n=\frac1{F(z^2)+\gamma z-tz}. $$ Then $P_n^\gamma$ is monic of degree $n$ with simple real roots, $P_n^\gamma\ll P_{n+1}^\gamma$, and the two have no common root.

The $4\times4$ matrix with rows $(2,2,2,2)$, $(1,2,2,2)$, $(\tfrac12,1,2,2)$, $(0,\tfrac12,1,2)$ satisfies conditions 1–3, and $F(z)=1+8z+16z^2+10z^3+2z^4$ is not real-rooted.

Use

Fisk's theorem for totally nonnegative matrices on the matrix interlacing page is a special case of Brändén's theorem; see also totally nonnegative matrices.

Proof

Let $J=\mathbf 1e_1^{\mathsf T}$ and $\mathbf f_k=(A+xJ)^k\mathbf 1$. By Brändén's theorem [Bra15, Corollary 8.6], a TP2 matrix maps interlacing sequences of polynomials with nonnegative coefficients to interlacing sequences, so every $\mathbf f_k$ is one, and condition 3 with the matrix determinant lemma gives $P_k(t)=(-1)^kf_{k,1}(-t)$; strictness comes from $\det(A+rJ)=\det A\ne0$ for every real $r$. The run polynomials are reversals of first coordinates of $(a_NA+xJ)\cdots(a_1A+xJ)\mathbf 1$, and the parity rows come from the TP2 block matrix $\begin{pmatrix}A&\mathbf 1c^{\mathsf T}\\0&A\end{pmatrix}$, with $c_j=A_{jj}$ and determinant polynomial $F(z)^2$, together with a Cauchy–Binet bound on Wronskians for strictness.

References

  1. [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

  • Nonnegative entries and nonnegative ordered 2 × 2 minors

    Matrix.IsTP2source
    def IsTP2 {ι κ : Type*} [PartialOrder ι] [PartialOrder κ] (M : Matrix ι κ ℝ) : Prop :=
      (∀ i j, 0 ≤ M i j) ∧
        ∀ ⦃i₁ i₂ : ι⦄ ⦃j₁ j₂ : κ⦄, i₁ < i₂ → j₁ < j₂ →
          0 ≤ M i₁ j₁ * M i₂ j₂ - M i₁ j₂ * M i₂ j₁
  • The vector recursion f_{k+1} = (A + X J) f_k

    RealRooted.hessenbergVectorsource
    def hessenbergVector (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ) :
        ℕ → Fin (n + 1) → ℝ[X]
      | 0 => fun _ => 1
      | k + 1 => tp2AffineStep A 1 (hessenbergVector A k)
  • The rows P_k, the coefficients of 1 / (det (I + z A) - t z)

    RealRooted.hessenbergRowsource
    def hessenbergRow (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ) (k : ℕ) : ℝ[X] :=
      PowerSeries.coeff k (hessenbergRowSeries A)
  • The site-weighted run sum Z_N(z), a sum over subsets of products of run weights

    RealRooted.siteWeightedRunssource
    def siteWeightedRuns (u : ℕ → R) {N : ℕ} (z : Fin N → R) : R :=
      siteRunSum u 0 z
  • The run kernel u_k = e_1^T A^k 1

    RealRooted.runKernelsource
    def runKernel (A : Matrix (Fin (n + 1)) (Fin (n + 1)) R) (k : ℕ) : R :=
      (A ^ k *ᵥ fun _ => 1) 0
  • B_N(t) = Z_N(a_0 t, ..., a_{N-1} t)

    RealRooted.siteWeightedRunPolynomialsource
    def siteWeightedRunPolynomial (u a : ℕ → ℝ) (N : ℕ) : ℝ[X] :=
      siteWeightedRuns (fun k => C (u k)) fun i : Fin N => C (a i) * X
  • The block matrix [[A, 1 c^T], [0, A]]

    RealRooted.parityBlocksource
    def parityBlock (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ) :
        Matrix (Fin (n + 1 + (n + 1))) (Fin (n + 1 + (n + 1))) ℝ :=
      Matrix.of fun i j => Fin.addCases
        (fun i' => Fin.addCases (fun j' => A i' j') (fun j' => A 0 j') j)
        (fun i' => Fin.addCases (fun _ => 0) (fun j' => A i' j') j) i
  • The rows P_n^gamma, the coefficients of 1 / (G(z^2) + gamma z - t z)

    RealRooted.parityRowsource
    def parityRow (A : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ) (γ : ℝ) (k : ℕ) : ℝ[X] :=
      PowerSeries.coeff k (parityRowSeries A γ)

Theorems

  • A TP2 constant matrix preserves interlacing sequences with nonnegative coefficientsRealRooted original

    Matrix.IsTP2.map_interlacingSeqsource
    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

    Matrix.IsTP2.interlacingSeqNonneg_cons_tp2AffineStepsource
    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

    RealRooted.hessenbergDenominator_mul_mk_hessenbergRowsource
    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

    RealRooted.hessenbergRow_eqsource
    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

    RealRooted.isInterlacingSeqNonneg_hessenbergVectorsource
    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

    RealRooted.hessenbergRow_certificatesource
    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

    RealRooted.hessenbergRow_exampleTwosource
    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

    RealRooted.det_eq_last_mul_prod_of_forall_lesource
    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

    RealRooted.det_add_smul_runJ_eqsource
    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

    RealRooted.eval_hessenbergVectorsource
    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

    RealRooted.not_isRoot_hessenbergVector_succ_zerosource
    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

    RealRooted.hasSimpleRoots_hessenbergVector_zerosource
    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

    RealRooted.hessenbergRow_strictsource
    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

    RealRooted.hessenbergRow_exampleTwo_strictsource
    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

    RealRooted.siteWeightedRuns_runKernelsource
    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

    RealRooted.siteWeightedRuns_one_by_onesource
    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

    RealRooted.runVector_eq_reflect_affineVectorsource
    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

    RealRooted.isRealRootedIn_Iio_siteWeightedRunPolynomialsource
    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

    RealRooted.strictInterl_siteWeightedRunPolynomialsource
    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

    RealRooted.siteWeightedRunPolynomial_certificatesource
    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

    RealRooted.le_eval_wronskian_sum_sumsource
    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

    RealRooted.le_eval_wronskian_hessenbergVector_succsource
    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

    RealRooted.parityBlock_isTP2source
    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

    RealRooted.hessenbergDet_parityBlocksource
    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

    RealRooted.hessenbergSeries_parityBlock_natAdd_zerosource
    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

    RealRooted.parityRow_zero_two_mulsource
    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

    RealRooted.parityRow_zero_two_mul_add_onesource
    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

    RealRooted.parityRow_eq_compsource
    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

    RealRooted.le_eval_wronskian_parityBlocksource
    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

    RealRooted.not_isRoot_parityVector_zero_succ_indexsource
    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

    RealRooted.parityRow_certificate_of_natDegree_ne_zerosource
    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

    RealRooted.parityRow_certificate_seedsource
    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))

Lean source RealRooted/Challenges/Matrices/TP2HessenbergCertificate.lean at revision d6670742. Formalized 2026-11-09.