I have a matrix $A \in \mathbb{R}^{n \times n}$ with positive eigenvalues. In the symmetric case, Sylvester's criterion implies that all the principal minors are positive. In the nonsymmetric case, is there an $O(n^\omega)$ algorithm to determine if all the principal minors are positive?

$\begingroup$ Isn't the determinant the product of the diagonal entries upon reduction to upper triangular form via Gaussian elimination? $\endgroup$ – Rodrigo de Azevedo Jul 29 '18 at 19:17

$\begingroup$ @RodrigodeAzevedo  Thanks for your comments. I have fixed the errors you noted. As you point out there are fast methods to calculate any given minor, but there are an exponential number of such minors. $\endgroup$ – Gabriel Mitchell Aug 1 '18 at 18:14

1$\begingroup$ Which minors? What do you want to conclude? Positive definiteness? Then it's only $n$ leading principal minors. Not exponential at all. $\endgroup$ – Rodrigo de Azevedo Aug 1 '18 at 18:28

$\begingroup$ @RodrigodeAzevedo  positivity of all the principal minors if what I am looking for. I don't especially care about positive definiteness, but if it implies positivity of all the principal minors then that is great. Do you know of any proof of that conjecture valid for nonsymmetric matrices? I am only aware of the proof in the symmetric case. $\endgroup$ – Gabriel Mitchell Aug 1 '18 at 21:29

$\begingroup$ Why do you care about the positivity of all the principal minors? Why not their nonnegativity? Why is the nonsymmetric case interesting? The skewsymmetric part contributes nothing to a quadratic form. $\endgroup$ – Rodrigo de Azevedo Aug 1 '18 at 21:33
The question amounts to asking for an efficient test whether a given matrix is a Pmatrix. Unfortunately, the problem is computationally hard. See this paper: The Pmatrix problem is coNPcomplete by G. Coxson, Mathematical Programming, March 1994, Volume 64, Issue 1–3, pp 173–178.

1$\begingroup$ I did not notice the restriction on all eigenvalues being positive. I am not sure if that changes the complexity. Will update the answer in case it does. $\endgroup$ – Suvrit Aug 1 '18 at 21:14