Establishing determinantal inequalities for positive-definite matrices

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish
Pages (from-to)13-24
Number of pages12
JournalDiscrete Applied Mathematics
Volume63
Issue number1
DOIs
Publication statusPublished - 27 Oct 1995

Fingerprint Dive into the research topics of 'Establishing determinantal inequalities for positive-definite matrices'. Together they form a unique fingerprint.

  • Cite this