<p>Given an <span class="math-container">$n\times n$</span> matrix <span class="math-container">$M$</span> with <span class="math-container">$\mathbb Z$</span> entries is 'does an <span class="math-container">$\frac n2\times\frac n2$</span> minor of <span class="math-container">$M$</span> vanish?' in <span class="math-container">$\bf{coNP}$</span>?</p>

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

CC BY-SA 4.0
2019-05-21T15:42:39.047Z
@JoshuaGrochow it may still be in coNP by a non-direct algebraic property. Maybe that is what Brout is interested in.
holf
CC BY-SA 4.0
2019-05-21T16:52:30.683Z
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.
Turbo
CC BY-SA 4.0
2019-05-21T16:53:18.590Z
@holf What was Joshua Grochow's argument ( I missed it)?
Turbo
CC BY-SA 4.0
2019-05-21T17:27:40.827Z
Oh, sorry, mine was the obvious that this problem is in NP: Guess the minor, compute its determinant, accept if it is zero.
Joshua Grochow
CC BY-SA 4.0
2019-05-21T17:28:20.750Z
@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).
Joshua Grochow
CC BY-SA 4.0
2019-05-21T18:49:16.690Z
Not that this rules out "a convex way to detect this", but just to note that over C, the set of such matrices is not convex, as it is the complement of a nontrivial variety (in fact, a hypersurface).
Joshua Grochow
CC BY-SA 4.0
2019-05-22T02:23:16.933Z
@JoshuaGrochow I think it is complement of union of irreducible varieties, I guess in Zariski terminology union of varieties is also another variety. Perhaps there is a different way. The only canonical topology we can use here is Zariski correct (even with $M$ in $\mathbb F_p^{n\times n}$)?
Turbo
<cc.complexity-theory><complexity-classes><np><convex-geometry><determinant>
Is the following problem in $coNP$?
Turbo
# Is the following problem in $coNP$?

(Asked by: username_0 on 2019-05-21)

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.

**Tags:** cc.complexity-theory, complexity-classes, np, convex-geometry, determinant
> **Comments:**
> **username_1**: @JoshuaGrochow it may still be in coNP by a non-direct algebraic property. Maybe that is what Brout is interested in.  
> **username_0**: 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.  
> **username_0**: @holf What was Joshua Grochow's argument ( I missed it)?  
> **username_2**: Oh, sorry, mine was the obvious that this problem is in NP: Guess the minor, compute its determinant, accept if it is zero.  
> **username_2**: @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).  
> **username_2**: Not that this rules out "a convex way to detect this", but just to note that over C, the set of such matrices is not convex, as it is the complement of a nontrivial variety (in fact, a hypersurface).  
> **username_0**: @JoshuaGrochow I think it is complement of union of irreducible varieties, I guess in Zariski terminology union of varieties is also another variety. Perhaps there is a different way. The only canonical topology we can use here is Zariski correct (even with $M$ in $\mathbb F_p^{n\times n}$)?  

---

## 0 answers

