Establishing determinantal inequalities for positive-definite matrices Original Research Article

Let A be an n × n matrix, and S be a subset of N = {1,2,…, n}. A[S] denotes the principal submatrix of A which lies in the rows and columns indexed by S. If α = {α1, …, αp} and β = {β1,…,βq} are two collections of subsets of N, the inequality α ⩽ β expresses that Πpi = 1 det A[αi] ⩽ Πqi = 1 det A[βi], for all n × n positive-definite matrices A. Recently, Johnson and Barrett gave necessary and sufficient conditions for α ⩽ β. In their paper they showed that the necessary condition is not sufficient, and they raised the following questions: What is the computational complexity of checking the necessary condition? Is the sufficient condition also necessary? Here we answer the first question proving that checking the necessary condition is co-NP-complete. We also show that checking the sufficient condition is NP-complete, and we use this result to give their second question the following answer: If NP ≠ co-NP, the sufficient condition is not necessary.