Let $k$ be a field, let $n$ be a natural number and for $i,j=1,\ldots n$  let $M_{ij}$ be a linear form in variables $X_{11}, \ldots X_{nn}$ ($n^2$ variables). 

> **Question:** What is known about algorithms which given $M_{ij}$ decide whether the matrix $M_{ij}$ represents a non-degenerate matrix for some choice of variables $X_{11}, \ldots, X_{nn}$?

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

If $k$ has $p$ elements then 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). 

Also, consider the case when each $M_{ij}$ is equal either to $0$ or to $X_{ij}$. Maybe this is simpler. It seems to be such a natural problem ("how many $0$'s do I need to put into the matrix to make sure it's not invertible?"), that I imagine it's been studied.