Determinant pencils of totally nonnegative matrices

Determinants $\det(I+xA)$ of totally nonnegative matrices, and their checkerboard-signed generalizations, are Pólya frequency polynomials, and their leading sections interlace.

Results

A real matrix is totally nonnegative (TNN) if all its minors are nonnegative. For a matrix $L$ the checkerboard matrix has entries $(-1)^{i+j}L_{ij}$.

Theorem (pencils). If $A$ is TNN, then $\det(I+xA)$ is a Pólya frequency polynomial. More generally, if $M$ and $L$ are TNN with $\det M>0$, then $\det\bigl(M+x\cdot\mathrm{checkerboard}(L)\bigr)$ is a Pólya frequency polynomial.

Theorem (interlacing of leading sections). Let $H$ be a TNN $(n+1)\times(n+1)$ matrix and $H_n$ its leading principal $n\times n$ section. Then $\det(xI_n+H_n)\ll\det(xI_{n+1}+H)$. More generally, let $A$ be lower triangular with $\det A\ne0$ and TNN inverse, and let $M$ be TNN. Then the leading $n\times n$ section of $\det(M+xA)$ interlaces $\det(M+xA)$. For $A=\mathrm{checkerboard}(L)$ with $L$ lower triangular, TNN and $\det L>0$, this gives the same conclusion for the pencil $\det(M+x\cdot\mathrm{checkerboard}(L))$.

Theorem (principal interlacing). Let $L$ be lower triangular and TNN with $\det L>0$, let $M$ be TNN with $\det M\ne0$ and positive superdiagonal entries, and suppose that for each $i$ either $M_{i+1,i}>0$, or $L_{i+1,i}>0$ and $M_{ii}>0$. Put $H=(\mathrm{checkerboard}\,L)^{-1}M$ and let $H'$ be $H$ without its last row and column. Then $\chi_{H'}\ll\chi_H$, both $\chi_H$ and $\chi_{H'}$ have simple roots, they have no common root, and all roots of $\chi_H$ are positive.

Proof

The last theorem uses the oscillatory case of principal interlacing for totally nonnegative matrices.

References

The background on totally nonnegative and oscillatory matrices is on the totally nonnegative matrices page.

Theorems

  • det(I + X A) is a PF polynomial for a totally nonnegative matrix ARealRooted original

    Matrix.IsTotallyNonneg.isPFPolynomial_det_one_add_X_smulsource
    theorem IsTotallyNonneg.isPFPolynomial_det_one_add_X_smul
        {n : ℕ} {A : Matrix (Fin n) (Fin n) ℝ} (hA : A.IsTotallyNonneg) :
        RealRooted.IsPFPolynomial (det (1 + (X : ℝ[X]) • A.map C))
  • det(M + X · checkerboard L) is PF for totally nonnegative M, L with det M > 0Main resultRealRooted original

    Matrix.IsTotallyNonneg.isPFPolynomial_det_map_add_X_smul_checkerboardsource
    theorem IsTotallyNonneg.isPFPolynomial_det_map_add_X_smul_checkerboard
        {n : ℕ} {M L : Matrix (Fin n) (Fin n) ℝ}
        (hM : M.IsTotallyNonneg) (hL : L.IsTotallyNonneg) (hdet : 0 < M.det) :
        RealRooted.IsPFPolynomial
          (det (M.map C + (X : ℝ[X]) • (checkerboard L).map C))
  • The leading section interlaces the full determinant pencil det(X I + H)RealRooted original

    Matrix.IsTotallyNonneg.leading_det_X_smul_one_add_map_interlacessource
    theorem IsTotallyNonneg.leading_det_X_smul_one_add_map_interlaces
        {n : ℕ} {H : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ}
        (hH : H.IsTotallyNonneg) :
        RealRooted.Interlaces
          (det ((X : ℝ[X]) • (1 : Matrix (Fin n) (Fin n) ℝ[X]) +
            (H.submatrix Fin.castSucc Fin.castSucc).map C))
          (det ((X : ℝ[X]) • (1 : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ[X]) +
            H.map C))
  • Leading sections of det(M + X A) interlace for triangular A with TNN inverseRealRooted original

    Matrix.IsLowerTriangular.leading_det_map_add_X_smul_interlacessource
    theorem IsLowerTriangular.leading_det_map_add_X_smul_interlaces
        {n : ℕ} {A M : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ}
        (hA : A.IsLowerTriangular) (hdet : IsUnit A.det)
        (hinv : A⁻¹.IsTotallyNonneg) (hM : M.IsTotallyNonneg) :
        RealRooted.Interlaces
          (det ((M.submatrix Fin.castSucc Fin.castSucc).map C +
            (X : ℝ[X]) • (A.submatrix Fin.castSucc Fin.castSucc).map C))
          (det (M.map C + (X : ℝ[X]) • A.map C))
  • Leading sections of checkerboard-signed determinant pencils interlaceRealRooted original

    Matrix.IsLowerTriangular.leading_det_map_add_X_smul_checkerboard_interlacessource
    theorem IsLowerTriangular.leading_det_map_add_X_smul_checkerboard_interlaces
        {n : ℕ} {L M : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ}
        (hLtri : L.IsLowerTriangular) (hL : L.IsTotallyNonneg)
        (hdet : 0 < L.det) (hM : M.IsTotallyNonneg) :
        RealRooted.Interlaces
          (det ((M.submatrix Fin.castSucc Fin.castSucc).map Polynomial.C +
            (Polynomial.X : Polynomial ℝ) •
              (checkerboard (L.submatrix Fin.castSucc Fin.castSucc)).map Polynomial.C))
          (det (M.map Polynomial.C +
            (Polynomial.X : Polynomial ℝ) • (checkerboard L).map Polynomial.C))
  • Principal sections of (checkerboard L)⁻¹ M interlace, with simple roots and no common rootRealRooted original

    Matrix.IsLowerTriangular.checkerboard_inv_mul_leading_charpoly_strictInterlacessource
    theorem IsLowerTriangular.checkerboard_inv_mul_leading_charpoly_strictInterlaces
        {n : ℕ} {L M : Matrix (Fin (n + 1)) (Fin (n + 1)) ℝ}
        (hLtri : L.IsLowerTriangular) (hL : L.IsTotallyNonneg)
        (hdet : 0 < L.det) (hM : M.IsTotallyNonneg) (hMdet : M.det ≠ 0)
        (hsuper : ∀ i : Fin n, 0 < M i.castSucc i.succ)
        (hsub : ∀ i : Fin n, 0 < M i.succ i.castSucc ∨
          (0 < L i.succ i.castSucc ∧ 0 < M i.castSucc i.castSucc)) :
        let H

Lean source RealRooted/Challenges/Matrices/TotallyNonnegativePencils.lean at revision d6670742. Formalized 2026-11-07.