Total positivity tests: optimal in the number of minors vs. the computational cost A real matrix is called totally positive if all of its minors are positive. Of course, to check that a given matrix is totally positive it is not necessary to check all the minors: for example, it suffices to check that all initial minors are positive. A minor $A\begin{pmatrix}I\\J\end{pmatrix}$ of $A$, corresponding to the sets of row indices $I$ and column indices $J$ is called initial if both $I$ and $J$ consist of consecutive indices and $1\in I\cup J$ (so every entry of $A$ is the lower right entry of a unique initial minor). In fact, there are many distinct families of minors such that their positivity implies total positivity, parametrized by "double wiring diagrams" (see https://link.springer.com/article/10.1007/BF03024444).
There are similar tests for total non-negativity. But all such tests seem to optimize the number of minors to be checked and not the total computational cost. One would imagine that checking more smaller minors could in some cases be done faster then checking fewer larger minors. Has any work been done in this direction?
 A: There are at least a few places looking at complexity for total positivity counting arithmetic operations. I don't know if people have looked at trying to find smaller minors. These use initial minors but try to compute smartly.

Cryer, Colin W. Some properties of totally positive matrices. Linear Algebra Appl. 15 (1976), no. 1, 1--25. link

In Remark 4.2 of the above, the complexity of checking total positivity with matrix factorization is analyzed and found to be cubic.

Gasca, M.; Peña, J. M. Total positivity and Neville elimination. Linear Algebra Appl. 165 (1992), 25--44. link

After Theorem 5.4 in the above, another cubic method for checking total positivity is discussed. (Here STP is ''strictly totally positive'' and TP is ''totally positive'' which is often called ''totally nonnegative.'')

Daniel Carter, Charles Johnson. The Complexity of Checking Partial Total Positivity.     arXiv:2103.08742 [cs.CC]

This recent preprint gives another cubic algorithm that makes use of Dodgson condensation.
