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 assignement of values to the variables $X_{ij}$ so that the matrix $M_{ij}$ is invertible?

${}$

> **Question:** What is known about algorithms for this problem?

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

The naive algorithm of checking each assignment of the variables $X_{ij}$ takes time bounded by a polynomial in $p^{n^2}$. I'd be interested to know if there is an improvement to polynomial in $p^n$ (or better). 

EDIT: Below Emil Jeřábek shows that the problem is NP-complete, but the reduction from 3-SAT is done in such a way that it still could be that there is an improvement to $p^n$ without proving anything unexpected about 3-SAT.

EDIT: The special case when each $M_{ij}$ is equal either to $0$ or to $X_{ij}$ is solved below by Emil Jeřábek.

EDIT: I've decided to ask a [more specific follow-up question][1].


  [1]: http://mathoverflow.net/questions/82892/3-sat-and-linear-forms-representing-a-non-degenerate-matrix