Totally nonnegative matrices

Totally nonnegative matrices have real nonnegative eigenvalues, their leading and trailing principal submatrices have interlacing characteristic polynomials, and they map interlacing sequences to interlacing sequences.

Results

A real matrix is totally nonnegative (TNN) if every square minor is nonnegative. Products of TNN matrices are TNN, by the Cauchy–Binet formula.

Theorem (principal interlacing). Let $A$ be a TNN $(N+1)\times(N+1)$ matrix, and let $A'$ and $A''$ be obtained by deleting the last, respectively the first, row and column. Then the characteristic polynomials of $A'$ and of $A''$ both interlace that of $A$. If moreover $\det A\ne0$ and the super- and subdiagonal entries of $A$ are positive (the oscillatory case), then the characteristic polynomials of $A$ and $A'$ have simple roots and no common root, and all eigenvalues of $A$ are positive.

Theorem (Gantmacher–Krein). Let $A$ be a TNN $n\times n$ matrix. Then $\det(xI-A)=\prod_{i=1}^n(x-\mu_i)$ with all $\mu_i\ge0$; equivalently, every complex eigenvalue of $A$ is a nonnegative real number. If moreover all compound matrices of some power $A^k$, $k\ge1$, have positive entries, then all $\mu_i>0$. If every compound matrix of a real square matrix is primitive, its eigenvalues are real, positive and simple.

Theorem (Fisk). [Fis06, Thm. 3.7] Let $f_1,\dots,f_n$ be real-rooted polynomials with positive leading coefficients and $f_i\ll f_j$ for $i<j$, and let $A$ be a TNN $m\times n$ matrix. Then the nonzero entries of $A(f_1,\dots,f_n)^{\mathsf T}$ are real-rooted with positive leading coefficients and form an interlacing sequence in row order.

A TNN $m\times n$ matrix $A$ is variation diminishing: $\operatorname{var}(Ac)\le\operatorname{var}(c)$ for $c\in\mathbb R^n$, where $\operatorname{var}$ counts sign changes after deleting zeros. By Cryer [Cry76], a nonsingular lower-triangular matrix is TNN as soon as every minor formed from arbitrary rows and an initial segment of the columns is nonnegative. By Karlin [Kar68], for $a>0$ every minor of $\bigl(e^{-a(i-j)^2}\bigr)$ with strictly increasing rows and columns is positive.

Finally, index from $0$ and let $T$ be lower Hessenberg with diagonal $d_i$, superdiagonal $1$, and, in row $i$, subdiagonal $s_i$ and second subdiagonal $t_i$. The characteristic polynomials of its leading sections satisfy $p_0=1$, $p_1=x-d_0$, $p_2=(x-d_1)(x-d_0)-s_1$ and $$ p_N=(x-d_{N-1})\,p_{N-1}-s_{N-1}\,p_{N-2}-t_{N-1}\,p_{N-3}\qquad(N\ge3). $$ If $T$ is a unit lower matrix with subdiagonal $\ell$ and second subdiagonal $m$ times an upper-bidiagonal matrix with diagonal $u_n>0$ and superdiagonal $1$, then $d_0=u_0$, $d_{n+1}=u_{n+1}+\ell_n$, $s_{n+1}=\ell_nu_n+m_n$ and $t_{n+2}=m_{n+1}u_n$, and these equations determine $u,\ell,m$. For $m_n\ge0$, the lower factor splits into two unit lower-bidiagonal matrices with nonnegative entries, that is, there are $a_n,b_n\ge0$ with $a_n+b_n=\ell_n$ and $a_{n+1}b_n=m_{n+1}$, if and only if the canonical pivots $$ u_0=\ell_0,\qquad u_{n+1}=\begin{cases} \ell_{n+1}&\text{if }u_n=0,\\ \ell_{n+1}-m_{n+1}/u_n&\text{otherwise,} \end{cases} $$ satisfy $u_n\ge0$, with $u_n=0$ only if $m_{n+1}=0$; then $b_n=u_n$, $a_{n+1}=m_{n+1}/u_n$ (or $0$) is such a split, and $b_n\le u_n$ for every such split. This holds if there are $v_n>0$ with $v_0\le\ell_0$ and $v_{n+1}+m_{n+1}/v_n\le\ell_{n+1}$. This extends a criterion of Branquinho, Foulquié-Moreno and Mañas to vanishing pivots.

Proof

The eigenvalues of the $q$-th compound matrix are the $q$-fold products of eigenvalues of $A$, Perron–Frobenius theory for primitive compounds makes each top product real and positive, and a TNN matrix is a limit of nonsingular TNN matrices. Principal interlacing reduces to Cauchy interlacing for a symmetric matrix with the same characteristic polynomial and principal sections. Fisk's theorem follows from the matrix criterion for interlacing preservers, since the $2\times2$ minors of a TNN matrix satisfy its affine interlacing condition. Cryer's criterion follows from the Gaussian kernel by a limit.

References

See also totally nonnegative matrices, the variation-diminishing property and TNN mixing on symmetricfunctions.com.

  1. [Fis06] Steve Fisk. Polynomials, roots, and interlacing. arXiv e-prints, 2006.
    BibTeX
    @article{Fisk2006x,
      Author = {Steve Fisk},
      Title = {Polynomials, roots, and interlacing},
      Year = {2006},
      Eprint = {arXiv:math/0612833},
      journal = {arXiv e-prints}
    }
  2. [Cry76] Colin W. Cryer. Some properties of totally positive matrices. Linear Algebra and its Applications, 15(1), 1-25, 1976.
    BibTeX
    @article{Cryer1976,
      author = {Cryer, Colin W.},
      title = {Some properties of totally positive matrices},
      year = {1976},
      journal = {Linear Algebra and its Applications},
      volume = {15},
      number = {1},
      pages = {1--25},
      doi = {10.1016/0024-3795(76)90076-8},
      url = {https://doi.org/10.1016/0024-3795(76)90076-8}
    }
  3. [Kar68] Samuel Karlin. Total Positivity, Vol. I. Stanford University Press, 1968.
    BibTeX
    @book{Karlin1968,
      author    = {Karlin, Samuel},
      title     = {Total Positivity, {V}ol.~{I}},
      publisher = {Stanford University Press},
      year      = {1968}
    }
  4. [FJ11] Shaun M. Fallat & Charles R. Johnson. Totally Nonnegative Matrices. Princeton Series in Applied Mathematics, Princeton University Press, 2011.
    BibTeX
    @book{FallatJohnson2011,
      author    = {Fallat, Shaun M. and Johnson, Charles R.},
      title     = {Totally Nonnegative Matrices},
      publisher = {Princeton University Press},
      series    = {Princeton Series in Applied Mathematics},
      year      = {2011},
      doi       = {10.1515/9781400839018}
    }

Definitions

  • Totally nonnegative rectangular matrix

    Matrix.IsTotallyNonnegRectsource
    def IsTotallyNonnegRect (M : Matrix ι κ R) : Prop :=
      ∀ ⦃n : ℕ⦄ ⦃rows : Fin n → ι⦄ ⦃cols : Fin n → κ⦄,
        StrictMono rows → StrictMono cols → 0 ≤ (M.submatrix rows cols).det
  • Sign variations of a vector

    Fin.signVariationssource
    def signVariations {R : Type*} [Zero R] [LinearOrder R] {n : ℕ}
        (x : Fin n → R) : ℕ :=
      (List.ofFn x).signVariations
  • Nonnegative initial-column minors

    Matrix.HasNonnegInitialColumnMinorssource
    def HasNonnegInitialColumnMinors {R : Type*} [CommRing R] [PartialOrder R]
        {N : ℕ} (A : Matrix (Fin N) (Fin N) R) : Prop :=
      ∀ ⦃m : ℕ⦄ (hm : m ≤ N) (rows : Fin m → Fin N), StrictMono rows →
        0 ≤ (A.submatrix rows (Fin.castLE hm)).det
  • Nonnegative split of a lower matrix into two bidiagonal factors

    RealRooted.IsNonnegativeLowerSplitsource
    def IsNonnegativeLowerSplit (ell m a b : ℕ → ℝ) : Prop :=
      (∀ n, 0 ≤ a n) ∧
        (∀ n, 0 ≤ b n) ∧
          (∀ n, a n + b n = ell n) ∧
            ∀ n, a (n + 1) * b n = m (n + 1)
  • Success of the zero-aware canonical split

    RealRooted.CanonicalLowerSplitSucceedssource
    def CanonicalLowerSplitSucceeds (ell m : ℕ → ℝ) : Prop :=
      ∀ n, 0 ≤ canonicalSecondFactor ell m n ∧
        (canonicalSecondFactor ell m n = 0 → m (n + 1) = 0)
  • Tetradiagonal lower-Hessenberg matrix

    RealRooted.tetradiagonalMatrixsource
    def tetradiagonalMatrix (d s t : ℕ → ℝ) (n : ℕ) : Matrix (Fin n) (Fin n) ℝ :=
      Matrix.bandedLowerHessenberg d s t 1 n

Theorems

  • A totally nonnegative matrix has real nonnegative eigenvalues

    Matrix.IsTotallyNonneg.charpoly_factorization_nonnegsource
    theorem IsTotallyNonneg.charpoly_factorization_nonneg
        {A : Matrix (Fin n) (Fin n) ℝ} (hA : A.IsTotallyNonneg) :
        ∃ μ : Fin n → ℝ, (∀ i, 0 ≤ μ i) ∧
          A.charpoly = ∏ i, (X - C (μ i))
  • Leading principal submatrices interlaceMain result

    Matrix.IsTotallyNonneg.leading_charpoly_interlacessource
    theorem IsTotallyNonneg.leading_charpoly_interlaces {N : ℕ}
        {A : Matrix (Fin (N + 1)) (Fin (N + 1)) ℝ}
        (hA : A.IsTotallyNonneg) :
        RealRooted.Interlaces
          (A.submatrix Fin.castSucc Fin.castSucc).charpoly A.charpoly
  • Totally nonnegative matrices mix interlacing sequences

    Matrix.IsTotallyNonnegRect.isInterlacingSeq_filter_mulVecsourcestatement on symmetricfunctions.com
    theorem IsTotallyNonnegRect.isInterlacingSeq_filter_mulVec
        {m n : ℕ} {A : Matrix (Fin m) (Fin n) ℝ}
        (hA : A.IsTotallyNonnegRect) (f : Fin n → ℝ[X])
        (hf_real : ∀ j, HasPosLeadingCoeff (f j) ∧ (f j).Splits)
        (hf : IsInterlacingSeq (List.ofFn f)) :
        IsInterlacingSeq ((List.ofFn fun i => ∑ j, A i j • f j).filter (· ≠ 0)) ∧
          ∀ i, ∑ j, A i j • f j ≠ 0 →
            HasPosLeadingCoeff (∑ j, A i j • f j) ∧ (∑ j, A i j • f j).Splits
  • Trailing principal submatrices interlace

    Matrix.IsTotallyNonneg.trailing_charpoly_interlacessource
    theorem IsTotallyNonneg.trailing_charpoly_interlaces {N : ℕ}
        {A : Matrix (Fin (N + 1)) (Fin (N + 1)) ℝ}
        (hA : A.IsTotallyNonneg) :
        RealRooted.Interlaces
          (A.submatrix Fin.succ Fin.succ).charpoly A.charpoly
  • The complex spectrum lies on the nonnegative real axis

    Matrix.IsTotallyNonneg.complex_spectrum_nonnegsource
    theorem IsTotallyNonneg.complex_spectrum_nonneg
        {A : Matrix (Fin n) (Fin n) ℝ} (hA : A.IsTotallyNonneg)
        {z : ℂ} (hz : z ∈ spectrum ℂ (A.map (algebraMap ℝ ℂ))) :
        ∃ r : ℝ, 0 ≤ r ∧ (r : ℂ) = z
  • Oscillatory matrices have real positive eigenvalues

    Matrix.IsTotallyNonneg.charpoly_factorization_pos_of_pow_compound_possource
    theorem IsTotallyNonneg.charpoly_factorization_pos_of_pow_compound_pos {n : ℕ}
        {A : Matrix (Fin n) (Fin n) ℝ} (hA : A.IsTotallyNonneg) {k : ℕ} (hk : k ≠ 0)
        (hpos : ∀ q, 1 ≤ q → q ≤ n → ∀ s t, 0 < compound q (A ^ k) s t) :
        ∃ μ : Fin n → ℝ, (∀ i, 0 < μ i) ∧ A.charpoly = ∏ i, (X - C (μ i))
  • Oscillatory matrices: principal interlacing with simple roots and no common root

    Matrix.IsTotallyNonneg.leading_charpoly_strictInterlacessource
    theorem IsTotallyNonneg.leading_charpoly_strictInterlaces {N : ℕ}
        {A : Matrix (Fin (N + 1)) (Fin (N + 1)) ℝ}
        (hA : A.IsTotallyNonneg) (hdet : A.det ≠ 0)
        (hsuper : ∀ i : Fin N, 0 < A i.castSucc i.succ)
        (hsub : ∀ i : Fin N, 0 < A i.succ i.castSucc) :
        RealRooted.Interlaces
            (A.submatrix Fin.castSucc Fin.castSucc).charpoly A.charpoly ∧
          (∀ x : ℝ, A.charpoly.IsRoot x →
            A.charpoly.rootMultiplicity x = 1) ∧
          (∀ x : ℝ, (A.submatrix Fin.castSucc Fin.castSucc).charpoly.IsRoot x →
            (A.submatrix Fin.castSucc Fin.castSucc).charpoly.rootMultiplicity x = 1) ∧
          (∀ x : ℝ, ¬(A.charpoly.IsRoot x ∧
            (A.submatrix Fin.castSucc Fin.castSucc).charpoly.IsRoot x)) ∧
          ∀ x ∈ A.charpoly.roots, 0 < x
  • Products of totally nonnegative matrices

    Matrix.IsTotallyNonnegRect.mulsource
    protected theorem IsTotallyNonnegRect.mul {R : Type*} [CommRing R] [PartialOrder R]
        [IsOrderedRing R] {l n m : ℕ} {L : Matrix (Fin l) (Fin n) R} {A : Matrix (Fin n) (Fin m) R}
        (hL : L.IsTotallyNonnegRect) (hA : A.IsTotallyNonnegRect) :
        (L * A).IsTotallyNonnegRect
  • Variation-diminishing property

    Matrix.IsTotallyNonnegRect.signVariations_mulVec_lesourcestatement on symmetricfunctions.com
    theorem Matrix.IsTotallyNonnegRect.signVariations_mulVec_le
        {l n : ℕ}
        {A : Matrix (Fin l) (Fin n) ℝ}
        (hA : A.IsTotallyNonnegRect) (c : Fin n → ℝ) :
        Fin.signVariations (A.mulVec c) ≤ Fin.signVariations c
  • Cryer's criterion for lower-triangular matrices

    Matrix.HasNonnegInitialColumnMinors.isTotallyNonneg_of_upper_zero_of_det_ne_zerosource
    theorem HasNonnegInitialColumnMinors.isTotallyNonneg_of_upper_zero_of_det_ne_zero
        {N : Nat} (A : Matrix (Fin N) (Fin N) ℝ)
        (hA : A.HasNonnegInitialColumnMinors)
        (hupper : ∀ i j, i < j → A i j = 0) (hdet : A.det ≠ 0) :
        A.IsTotallyNonneg
  • Gantmacher–Krein: primitive compounds give a simple positive spectrum

    Matrix.exists_charpoly_eq_prod_strictAnti_of_compounds_primitivesource
    theorem exists_charpoly_eq_prod_strictAnti_of_compounds_primitive
        {A : Matrix (Fin n) (Fin n) ℝ}
        (hprim : ∀ q, 1 ≤ q → q ≤ n → (compound q A).IsPrimitive) :
        ∃ μ : Fin n → ℝ, StrictAnti μ ∧ (∀ i, 0 < μ i) ∧
          A.charpoly = ∏ i, (X - C (μ i))
  • Primitive compounds make the characteristic polynomial real-rooted with positive roots

    Matrix.charpoly_splits_of_forall_compound_primitivesource
    theorem charpoly_splits_of_forall_compound_primitive
        {A : Matrix (Fin n) (Fin n) ℝ}
        (hprim : ∀ q, 1 ≤ q → q ≤ n → (compound q A).IsPrimitive) :
        A.charpoly.Splits ∧ ∀ t ∈ A.charpoly.roots, 0 < t
  • The canonical algorithm succeeds exactly when a nonnegative bidiagonal split exists

    RealRooted.canonicalLowerSplitSucceeds_iffsource
    theorem canonicalLowerSplitSucceeds_iff {ell m : ℕ → ℝ}
        (hm : ∀ n, 0 ≤ m n) :
        CanonicalLowerSplitSucceeds ell m ↔
          ∃ a b, IsNonnegativeLowerSplit ell m a b
  • Every nonnegative split is bounded by the canonical pivots

    RealRooted.canonicalSecondFactor_maximalsource
    theorem canonicalSecondFactor_maximal {ell m a b : ℕ → ℝ}
        (hm : ∀ n, 0 ≤ m n) (h : IsNonnegativeLowerSplit ell m a b) (n : ℕ) :
        b n ≤ canonicalSecondFactor ell m n
  • A positive lower bound for the pivots forces the canonical split to succeed

    RealRooted.canonicalLowerSplitSucceeds_of_lower_boundsource
    theorem canonicalLowerSplitSucceeds_of_lower_bound {ell m v : ℕ → ℝ}
        (hm : ∀ n, 0 ≤ m n) (hv : ∀ n, 0 < v n) (hzero : v 0 ≤ ell 0)
        (hsucc : ∀ n, v (n + 1) + m (n + 1) / v n ≤ ell (n + 1)) :
        CanonicalLowerSplitSucceeds ell m ∧
          ∀ n, v n ≤ canonicalSecondFactor ell m n
  • Positive-pivot reconstruction of a tetradiagonal factorization is unique

    RealRooted.positivePivotReconstruction_uniquesource
    theorem positivePivotReconstruction_unique {d s t ell m u ell' m' u' : ℕ → ℝ}
        (h : IsPositivePivotReconstruction d s t ell m u)
        (h' : IsPositivePivotReconstruction d s t ell' m' u') :
        u = u' ∧ ell = ell' ∧ m = m'
  • The four-term recurrence gives the characteristic polynomials of tetradiagonal sections

    RealRooted.tetradiagonalPolynomial_eq_charpolysource
    theorem tetradiagonalPolynomial_eq_charpoly (d s t : ℕ → ℝ) (n : ℕ) :
        tetradiagonalPolynomial d s t n = (tetradiagonalMatrix d s t n).charpoly
  • Karlin: Gaussian matrices are strictly totally positive

    Matrix.det_gaussianMatrix_submatrix_possource
    theorem det_gaussianMatrix_submatrix_pos {n q : ℕ}
        (a : ℝ) (rows cols : Fin q → Fin n) (ha : 0 < a)
        (hrows : StrictMono rows) (hcols : StrictMono cols) :
        0 < ((gaussianMatrix n a).submatrix rows cols).det

Lean source RealRooted/Challenges/Matrices/TotallyNonnegativeMatrices.lean at revision d6670742. Formalized 2026-09-05.