2
$\begingroup$

Given an $n\times n$ matrix $M$ with $\mathbb Z$ entries is 'does an $\frac n2\times\frac n2$ minor of $M$ vanish?' in $\bf{coNP}$?

At least one $\frac n2\times\frac n2$ minor non-vanish implies rank $\geq\frac n2$. However does all $\frac n2\times\frac n2$ minor non-vanish have a short certificate? I think it might be the case and perhaps there is a convex way to detect this.

$\endgroup$
  • $\begingroup$ @JoshuaGrochow it may still be in coNP by a non-direct algebraic property. Maybe that is what Brout is interested in. $\endgroup$ – holf May 21 at 15:42
  • 1
    $\begingroup$ Yes is there something that can directly tell? At least one $\frac n2\times\frac n2$ minor non-vanish implies rank $\geq\frac n2$. However does all $\frac n2\times\frac n2$ minor non-vanish have a short certificate? I think it might be the case and perhaps there is a convex way to detect this. $\endgroup$ – Turbo May 21 at 16:52
  • $\begingroup$ @holf What was Joshua Grochow's argument ( I missed it)? $\endgroup$ – Turbo May 21 at 16:53
  • $\begingroup$ Oh, sorry, mine was the obvious that this problem is in NP: Guess the minor, compute its determinant, accept if it is zero. $\endgroup$ – Joshua Grochow May 21 at 17:27
  • $\begingroup$ @Brout: Your first comment above would make an excellent addition to the question itself. Also, it would be nice to add some motivation (though it is a natural enough question). $\endgroup$ – Joshua Grochow May 21 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.