TY - JOUR

T1 - Establishing determinantal inequalities for positive-definite matrices

AU - Cerdeira, J. Orestes

AU - Faria, Isabel

AU - Bárcia, Paulo

PY - 1995/10/27

Y1 - 1995/10/27

N2 - 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 Πp
i = 1 det A[αi] ≤ Πq
i = 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.

AB - 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 Πp
i = 1 det A[αi] ≤ Πq
i = 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.

UR - http://www.scopus.com/inward/record.url?scp=58149208976&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(94)00027-B

DO - 10.1016/0166-218X(94)00027-B

M3 - Article

AN - SCOPUS:58149208976

SN - 0166-218X

VL - 63

SP - 13

EP - 24

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1

ER -