4
$\begingroup$

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 non-symmetric case, is there an $O(n^\omega)$ algorithm to determine if all the principal minors are positive?

$\endgroup$
5
  • $\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 non-symmetric 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 non-negativity? Why is the non-symmetric case interesting? The skew-symmetric part contributes nothing to a quadratic form. $\endgroup$ – Rodrigo de Azevedo Aug 1 '18 at 21:33
1
$\begingroup$

The question amounts to asking for an efficient test whether a given matrix is a P-matrix. Unfortunately, the problem is computationally hard. See this paper: The P-matrix problem is co-NP-complete by G. Coxson, Mathematical Programming, March 1994, Volume 64, Issue 1–3, pp 173–178.

$\endgroup$
1
  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.