Circle criterion for Hessenberg Toeplitz matrices

If the symbol of a lower Hessenberg Toeplitz matrix has nonnegative imaginary part on an upper half-circle, then the characteristic polynomials of its sections have simple real roots and consecutive ones strictly interlace.

Results

Let $b(z)=z^{-1}+b_0+\sum_{k\ge1}b_kz^k$ with finitely many real coefficients. The characteristic polynomials $P_n(t)=\det(tI-T_n)$ of the Toeplitz sections $T_n=(b_{i-j})_{i,j=1}^n$ satisfy $P_0=1$ and $$ P_{n+1}(t)=(t-b_0)P_n(t)-\sum_{k=1}^n b_kP_{n-k}(t). $$

Theorem (circle criterion). If $\operatorname{Im}b(Re^{i\theta})\ge0$ for $0<\theta<\pi$ and some $R>0$, then every $P_n$ has $n$ simple real zeros and $P_n$ and $P_{n+1}$ strictly interlace. Equivalently, the hypothesis says that $$ Q_R(u)=-R^{-1}+\sum_{k\ge1}b_kR^kU_{k-1}(u)\ge0\qquad(-1\le u\le1), $$ since $Q_R(\cos\theta)\sin\theta=\operatorname{Im}b(Re^{i\theta})$.

Proof

At a real zero $\xi$ of $P_n$, an exact identity writes $-R^{2n+1}P_{n-1}(\xi)P_{n+1}(\xi)$ as $R$ plus a quadratic form in the values $R^jP_{j-1}(\xi)$; integrating over the circle of radius $R$ shows that the form is nonnegative. So $P_{n-1}$ and $P_{n+1}$ have opposite signs at the zeros of $P_n$, and induction gives the interlacing.

References

Definitions

  • RealRooted.Toeplitz.Circle.rowsource
    def row (b : ℕ →₀ ℝ) : ℕ → ℝ[X]
      | 0 => 1
      | n + 1 => X * row b n -
          b.sum fun k a => if k ≤ n then C a * row b (n - k) else 0
    termination_by n => n
  • RealRooted.Toeplitz.Circle.CircleNonnegsource
    def CircleNonneg (b : ℕ →₀ ℝ) (R : ℝ) : Prop :=
      ∀ u ∈ Set.Icc (-1 : ℝ) 1, 0 ≤ (circlePolynomial b R).eval u

Theorems

  • The circle criterion gives simple real roots and consecutive interlacingMain result

    RealRooted.Toeplitz.Circle.strictInterl_of_circleNonnegsource
    theorem strictInterl_of_circleNonneg (b : ℕ →₀ ℝ) (R : ℝ)
        (hR : 0 < R) (hQ : CircleNonneg b R) (n : ℕ) :
        StrictInterl (row b n) (row b (n + 1)) ∧
          HasSimpleRoots (row b n) ∧ HasSimpleRoots (row b (n + 1))
  • Consecutive rows have no common root

    RealRooted.Toeplitz.Circle.not_isRoot_succ_of_circleNonnegsource
    theorem not_isRoot_succ_of_circleNonneg (b : ℕ →₀ ℝ) (R : ℝ)
        (hR : 0 < R) (hQ : CircleNonneg b R) (n : ℕ) (x : ℝ)
        (hx : (row b n).IsRoot x) : ¬ (row b (n + 1)).IsRoot x
  • The exact correlation energy identity at a row root

    RealRooted.Toeplitz.Circle.energy_identitysource
    theorem energy_identity (b : ℕ →₀ ℝ) (R x : ℝ) (n : ℕ)
        (hR : R ≠ 0) (hn : 1 ≤ n) (hx : (row b n).IsRoot x) :
        -R ^ (2 * n + 1) * (row b (n - 1)).eval x * (row b (n + 1)).eval x =
          R + quadraticForm b R (fundamentalVector b R x n)

Lean source RealRooted/Challenges/Matrices/CircleCriterion.lean at revision d6670742. Formalized 2026-11-13.