MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a follow-up to the previous question on the same topic. Thanks to Emil Jeřábek I can now ask a more specific question.

As before, let $k$ be a field with $p$ elements. Consider the following computational problem.

Input: a natural number $n$, $n^2$ linear forms $M_{ij}$, $i,j=1,\ldots n$ in $n^2$ variables $X_{11}, \ldots X_{nn}$.

Problem: Is there an assignment of values to the variables $X_{ij}$ so that the matrix $M_{ij}$ is invertible?

As usually, let's assume the addition and multiplication in the field to have computational cost $1$.

On the one hand, we have a trivial algorithm of checking all the possible assignments for $X_{ij}$, and for each such assignment checking by Gauss elimination whether the resulting matrix is invertible. This takes time bounded by a polynomial in $p^{n^2}$.

On the other hand, Emil Jeřábek showed previously that we can encode a 3-SAT instance consisting of $n$ clauses into a $3n\times 3n$ matrix of linear forms which is invertibe iff the 3-SAT instance is satisfiable. Assuming exponential time hypothesis this gives a lower bound on the problem above of the form $O(2^{\delta n})$ for some $\delta>0$.

Question 1 Is there an algorithm for the problem above, whose execution time is bounded by a polynomial in $p^{n^\alpha}$ for $\alpha <2$?

Question 2 Is there a natural number $k$ such that one can encode a 3-SAT instance with $n^\beta$ clauses into a problem as above for a $kn\times kn$ matrix, for $\beta>1$?

share|cite|improve this question
Probabilistic checking of invertibility means choosing values at random and evaluating the resulting determinant and seeing if it is nonzero. This is O(n^3), with a good chance of success if there are such values. Is the 3SAT problem solved if we find such values? Gerhard "Ask Me About System Design" Paseman, 2011.12.07 – Gerhard Paseman Dec 7 '11 at 18:36
@Gerhard: As discussed in the previous question, this probabilistic algorithm only works if the size of the field is larger than the degree of the polynomial (i.e., $n$). Here, the field size is constant. – Emil Jeřábek Dec 7 '11 at 18:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.