determining if a matrix of linear forms represents a non-degenerate matrix 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). 

The special case when each $M_{ij}$ is equal either to $0$ or to $X_{ij}$ is solved  by Emil Jeřábek on the mathoverflow thread linked to below.
This answer summarizes and expands my comments above:

1) If the size of the underlying field is large enough, then this problem has efficient randomized algorithms: You have to test whether the resulting determinant is nonzero as a polynomial. You can use the Schwartz-Zippel lemma for this. (Search for the keyword "Polynomial Identity testing"
for further algorithms/results.)

2) The question whether this problem can be derandomized is open.
Derandomizing it implies circuit lower bounds. See the work by Kabanets &amp; Impagliazzo. (Comput. Complexity 13, 2004, http://www.cs.sfu.ca/~kabanets/Research/poly.html), the problem is called
SDIT (Symbolic Determinant Identity testing) in the paper. 

3) Gurvits has a deterministic algorithm for some special cases of SDIT
(http://dx.doi.org/10.1145/780542.780545). He refers to SDIT as "Edmond's problem". (This item was provided by Joshua Grochow. I suggest that when 
you want to upvote my answer, you should upvote any of his answers with probability 1/4 instead.)

4) Over finite fields (size is fixed), it is NP-complete. Over GF(2), you can just arithmetize a given formula in 3-CNF (that is, write it as an equivalent arithmetic formula)
and then use fact that you can write any arithmetic formula as a poly-size determinant (proven by Valiant, see also Bürgisser, Clausen, Shokrollahi,
Algebraic Complexity Theory, Chapter 21). Over other finite fields, you can start with appropriate CSPs instead of 3-SAT.