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?
$\begingroup$
$\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 AzevedoCommented Jul 29, 2018 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 MitchellCommented Aug 1, 2018 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 AzevedoCommented Aug 1, 2018 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 MitchellCommented Aug 1, 2018 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 AzevedoCommented Aug 1, 2018 at 21:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
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$– SuvritCommented Aug 1, 2018 at 21:14