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?
Best Answer
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.
In Remark 4.2 of the above, the complexity of checking total positivity with matrix factorization is analyzed and found to be cubic.
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.'')
This recent preprint gives another cubic algorithm that makes use of Dodgson condensation.