This is a follow-up to the [previous question][1] 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][2] 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][3] 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$?


  [1]: https://mathoverflow.net/questions/82804/determining-if-a-matrix-of-linear-forms-represents-a-non-degenerate-matrix
  [2]: https://mathoverflow.net/questions/82804/determining-if-a-matrix-of-linear-forms-represents-a-non-degenerate-matrix/82808#82808
  [3]: http://en.wikipedia.org/wiki/Exponential_time_hypothesis