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 -