<p>This answer summarizes and expands my comments above:</p>

<p>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.)</p>

<p>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, <a href="http://www.cs.sfu.ca/~kabanets/Research/poly.html">http://www.cs.sfu.ca/~kabanets/Research/poly.html</a>), the problem is called
SDIT (Symbolic Determinant Identity testing) in the paper. </p>

<p>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.)</p>

<p>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. </p>

CC BY-SA 3.0
2011-12-12T16:37:39.053Z
"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
CC BY-SA 3.0
2011-12-14T14:47:49.433Z
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](http://mathoverflow.net/questions/82892/3-sat-and-linear-forms-representing-a-non-degenerate-matrix)
Łukasz Grabowski
CC BY-SA 3.0
2011-12-12T09:42:54.903Z
2011-12-12T09:42:54.903Z
Markus Bläser
<p>Let $k$ be a field with $p$ elements. Consider the following computational problem</p>

<blockquote>
  <p><em>Input</em>: a natural number $n$,  $n^2$ linear forms $M_{ij}$, $i,j=1,\ldots n$ in $n^2$ variables $X_{11}, \ldots X_{nn}$. </p>
  
  <p><em>Problem:</em> Is there an assignement of values to the variables $X_{ij}$ so that the matrix $M_{ij}$ is invertible?</p>
</blockquote>

<p>${}$</p>

<blockquote>
  <p><strong>Question:</strong> What is known about algorithms for this problem?</p>
</blockquote>

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

<p>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). </p>

<p>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.</p>

CC BY-SA 3.0
2011-12-06T17:52:47.617Z
I've posted it also to http://mathoverflow.net/questions/82804/determining-if-a-matrix-of-linear-forms-represents-a-non-degenerate-matrix
Łukasz Grabowski
CC BY-SA 3.0
2011-12-06T20:45:39.257Z
Google for "Polynomial identity testing"
Markus Bläser
CC BY-SA 3.0
2011-12-07T07:45:13.943Z
@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
CC BY-SA 3.0
2011-12-07T08:47:46.820Z
@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
CC BY-SA 3.0
2011-12-11T00:25:47.480Z
@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 (http://dx.doi.org/10.1145/780542.780545). He refers to SDIT as "Edmonds' problem".
Joshua Grochow
<ds.algorithms><co.combinatorics><linear-algebra>
determining if a matrix of linear forms represents a non-degenerate matrix
Łukasz Grabowski
# determining if a matrix of linear forms represents a non-degenerate matrix

(Asked by: username_0 on 2011-12-06)

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.

**Tags:** ds.algorithms, co.combinatorics, linear-algebra
> **Comments:**
> **username_0**: I've posted it also to http://mathoverflow.net/questions/82804/determining-if-a-matrix-of-linear-forms-represents-a-non-degenerate-matrix  
> **username_1**: Google for "Polynomial identity testing"  
> **username_2**: @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.  
> **username_1**: @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)  
> **username_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 (http://dx.doi.org/10.1145/780542.780545). He refers to SDIT as "Edmonds' problem".  

---

## 1 answers

### Answer by username_1 on 2011-12-12. Score: 9

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.

> **Comments:**
> **username_4**: "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. :-)  
> **username_0**: 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](http://mathoverflow.net/questions/82892/3-sat-and-linear-forms-representing-a-non-degenerate-matrix)  

---

