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
- F. R. Gantmacher and M. G. Krein, Oscillation Matrices and Kernels and Small Vibrations of Mechanical Systems, 1937; revised English edition, AMS Chelsea, 2002.
- [Kar68]; [Cry76]; [FJ11].
- [Fis06, Thm. 3.7].
See also totally nonnegative matrices, the variation-diminishing property and TNN mixing on symmetricfunctions.com.
- [Fis06] 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} } - [Cry76] 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} } - [Kar68] 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} } - [FJ11] 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} }