Efficient recognition of totally nonnegative matrix cells (Q404284)

A real \(m\times p\) matrix \(M\) is totally nonnegative (totally positive) if each of its minors is nonnegative (strictly positive). Totally nonnegative matrices arise in many areas of mathematics and have lately been studied with increasing interest. Checking all minors is clearly impractical and \textit{M. Gasca} and \textit{J. M. Peña} [Linear Algebra Appl. 165, 25--44 (1992; Zbl 0749.15010)] have provided a well-known criterion for total positivity involving the testing of a specified set of mp minors and this number of minors is best possible, but many other choices of such sets of mp minors are possible. In contrast, there is no known small set of minors for testing for total nonnegativity. In this paper the authors go a step in this direction. Stated briefly, they show that the space of real totally nonnegative \(m\times p\) matrices has a stratification into totally nonnegative cells, the largest of which is the space of totally positive matrices. In their main result they then provide a set of \(mp\) minors for deciding whether or not an arbitrary real \(m\times p\) matrix belongs to a specified non-empty cell. This extends the criterion of Gasca and Peña for the totally positive cell to any non-empty cell.