Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
I've posted it also to mathoverflow.net/questions/82804/… –  Łukasz Grabowski Dec 6 '11 at 17:52
2  
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
5  
@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
3  
@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
add comment

1 Answer 1

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.

share|improve this answer
2  
"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. :-) –  Aaron Sterling Dec 12 '11 at 16:37
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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