# 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.

-
I've posted it also to mathoverflow.net/questions/82804/… –  Łukasz Grabowski Dec 6 '11 at 17:52
Google for "Polynomial identity testing" –  Markus Bläser Dec 6 '11 at 20:45
@MarkusBläser: I wanted to give a similar answer as yours. Yet, I am not sure what can be said on this particular problem, in terms of a deterministic algorithm, using the current results on PIT. –  Bruno Dec 7 '11 at 7:45
@Bruno: Derandomizing the problem would imply circuit lower bounds. This problem is considered under the name SDIT (Symbolic Determinant Identity testing) by Kabanets & Impagliazzo. (Comput. Complexity 13, 2004) –  Markus Bläser Dec 7 '11 at 8:47
@MarkusBläser: your previous comment should be made an answer. I would add that Gurvits has given a deterministic algorithm for some special cases of SDIT (dx.doi.org/10.1145/780542.780545). He refers to SDIT as "Edmonds' problem". –  Joshua Grochow Dec 11 '11 at 0:25

Thanks, but this doesn't really answer the question whether you can improve from $p^{n^2}$ to p^n. See the discussion on mathoverflow - there it is shown how to embed instances of 3-SAT of size n into $n\times n$ matrix. But this just shows that one shoudn't hope for an algorithm better than p^n. I made it precise in this question –  Łukasz Grabowski Dec 14 '11 at 14:47