Characterizing total positivity: Single vector tests via linear complementarity, sign non‐reversal and variation diminution

A matrix A A is called totally positive (or totally non-negative) of order k k, denoted by T P k TPₖ (or T N k TNₖ), if all minors of size at most k k are positive (or non-negative). These matrices have featured in diverse areas in mathematics, including algebra, analysis, combinatorics, differential equations and probability theory. The goal of this article is to provide a novel connection between total positivity and optimization/game theory. Specifically, we draw a relationship between totally positive matrices and the linear complementarity problem (LCP), which generalizes and unifies linear and quadratic programming problems and bimatrix games — this connection is unexplored, to the best of our knowledge. We show that A A is T P k TPₖ if and only if for every submatrix A r Aᵣ of A A formed from r r consecutive rows and r r consecutive columns (with r ⩽ k r k), LCP (A r, q) LCP (Aᵣ, q) has a unique solution for each vector q < 0 q<0. In fact this can be strengthened to check the solution set of the LCP at a single vector for each such square submatrix. These novel characterizations are in the spirit of classical results characterizing T P TP matrices by Gantmacher–Krein Compos. Math. 1937 and P P -matrices by Ingleton Proc. London Math. Soc. 1966. Our work contains two other contributions, both of which characterize total positivity using single test vectors whose coordinates have alternating signs — that is, lie in a certain open bi-orthant. First, we improve on one of the main results in recent joint work Bull. London Math. Soc. , 2021, which provided a novel characterization of T P k TPₖ matrices using sign non-reversal phenomena. We further improve on a classical characterization of total positivity by Brown–Johnstone–MacGibbon J. Amer. Statist. Assoc. 1981 (following Gantmacher–Krein, 1950) involving the variation diminishing property. Finally, we use a Pólya frequency function of Karlin Trans. Amer. Math. Soc. 1964 to show that our aforementioned characterizations of total positivity, involving (single) test-vectors drawn from the 'alternating' bi-orthant, do not work if these vectors are drawn from any other open orthant.