7
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ I've posted it also to mathoverflow.net/questions/82804/… $\endgroup$ Dec 6, 2011 at 17:52
  • 2
    $\begingroup$ Google for "Polynomial identity testing" $\endgroup$ Dec 6, 2011 at 20:45
  • $\begingroup$ @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. $\endgroup$
    – Bruno
    Dec 7, 2011 at 7:45
  • 5
    $\begingroup$ @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) $\endgroup$ Dec 7, 2011 at 8:47
  • 3
    $\begingroup$ @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". $\endgroup$ Dec 11, 2011 at 0:25

1 Answer 1

9
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ "I suggest that when you want to upvote my answer, you should upvote any of his answers with probability 1/4 instead." <-- that made me smile. :-) $\endgroup$ Dec 12, 2011 at 16:37
  • $\begingroup$ 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 $\endgroup$ Dec 14, 2011 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.