# Is the following problem in $coNP$?

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.

• @JoshuaGrochow it may still be in coNP by a non-direct algebraic property. Maybe that is what Brout is interested in.
– holf
May 21 '19 at 15:42
• 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.
– Mr.
May 21 '19 at 16:52
• @holf What was Joshua Grochow's argument ( I missed it)?
– Mr.
May 21 '19 at 16:53
• Oh, sorry, mine was the obvious that this problem is in NP: Guess the minor, compute its determinant, accept if it is zero. May 21 '19 at 17:27
• @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). May 21 '19 at 17:28