4
$\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).

EDIT: Below Emil Jeřábek shows that the problem is NP-complete, but the reduction from 3-SAT is done in such a way that it still could be that there is an improvement to $p^n$ without proving anything unexpected about 3-SAT.

EDIT: The special case when each $M_{ij}$ is equal either to $0$ or to $X_{ij}$ is solved below by Emil Jeřábek.

EDIT: I've decided to ask a more specific follow-up question.

$\endgroup$
5
  • $\begingroup$ I've posted it also to cstheory.stackexchange.com/questions/9316/… $\endgroup$ Dec 6, 2011 at 17:52
  • 3
    $\begingroup$ As an experienced user, you are aware that simultaneous cross-posting is discouraged on both these sites? $\endgroup$ Dec 6, 2011 at 18:42
  • 1
    $\begingroup$ no, thanks for letting me know, i'll keep it mind $\endgroup$ Dec 7, 2011 at 0:09
  • $\begingroup$ Trying to solve $M_{ij}=c_{ij}$ is a linear system in n^2 unknowns and n^2 equations. If it has a solution for suitable $c_{ij}$ you are done, but the matrix might not be full rank. $\endgroup$
    – joro
    Dec 7, 2011 at 16:08
  • $\begingroup$ @joro: this is just another naive algorithm which takes time bounded by a polynomial in $p^{n^2}$, as this is how many possibilities for $c_{ij}$ there are, and it's not difficult to find examples where only $p-1$ choices for $c_{ij}$ lead to an invertible matrix. $\endgroup$ Dec 7, 2011 at 16:31

1 Answer 1

5
$\begingroup$

The determinant of $M$, considered as a matrix over the polynomial ring $R=k[X_{11},\dots,X_{nn}]$, is a polynomial $f\in R$, and your problem is to determine whether $f$ defines the constant $0$ function over $k$.

There are several division-free algorithms for computation of determinant in any commutative ring using polynomially many ring operations. In principle, you can use such an algorithm to compute $f$, but this may result in a long expression, since $f$ may have exponentially many terms. It is better to combine this with a polynomial identity testing algorithm: since $f$ has degree $n$, the Schwartz–Zippel lemma tells you that $f(a_{11},\dots,a_{nn})\ne0$ for randomly chosen $a_{ij}\in k$ with probability at least $1-n/p$, as long as $f\ne0$ and $p>n$. Thus, if (say) $p>2n$, you don’t actually have to evaluate $f$, you have a simple probabilistic polynomial-time algorithm: choose random assignment to your variables, and test whether the resulting matrix is nonsingular.

In the special case where each $M_{ij}$ is either $0$ or $X_{ij}$, things are much simpler: it is easy to see that there is an assignment making the matrix nonsingular if and only if there is a permutation $\pi$ such that $M_{i\pi(i)}\ne0$ for each $i$, in other words, if and only if the bipartite graph whose biadjacency matrix is defined from $M$ by replacing every $X_{ij}$ with $1$ has a perfect matching. There are various efficient algorithm for finding perfect matchings and/or checking their existence, see e.g. http://en.wikipedia.org/wiki/Perfect_matching#Algorithms_and_computational_complexity .

EDIT: For a fixed $p$, the full problem is NP-complete. The reduction is simplest for $\mathbb F_2$. Assume we are given a $3$-CNF $C(x_1,\dots,x_n)=\bigwedge_{i< m}\bigvee_{j< 3}l_{ij}$, where each $l_{ij}$ is either some $x_k$ or $\neg x_k$. We identify $\neg x_k$ with the linear polynomial $1+x_k$. Then $C$ is satisfiable if and only if the polynomial $f(x_1,\dots,x_n)=\prod_i(1+\prod_jl_{ij})$ assumes a nonzero value for some assignment over $\mathbb F_2$. Let $M$ be the block diagonal matrix consisting of $m$ blocks $M_i$, where $$M_i=\begin{pmatrix}1&l_{i0}&0\\\0&1&l_{i1}\\\\l_{i2}&0&1\end{pmatrix}.$$ Then $\det(M)=f$, thus there is an assignment in $\mathbb F_2$ making $M$ invertible iff $C$ is satisfiable. One can get rid of the constants $1$ in the matrix as follows: we include in $M$ the identity matrix as yet another block, and then we replace $1$ with a new variable $x_0$ everywhere (i.e., in the $1$ entries as well as in the entries of the form $1+x_k$). Any assignment making the new matrix invertible must have $x_0=1$, and then it works as before. The new matrix has only entries of the form $0$, $x_k$, $x_0+x_k$.

$\endgroup$
12
  • $\begingroup$ Thanks, this solves the special problem. I'll reformulate the question to make clear that I mean $p$ to be fixed; in particular the probabilistic polynomial-time algorithm you suggest is of not much use. $\endgroup$ Dec 7, 2011 at 0:11
  • $\begingroup$ After thinking about it, I don't understand your solution to the special problem. I agree that it's equivalen to checking if there is a permutaion $\pi$ such that $M_{i\pi(i)}\neq 0$ for all $i$. But what doe it have to do with perfect matchings? Could you give a reference or expand the argument? $\endgroup$ Dec 7, 2011 at 13:03
  • $\begingroup$ Also, if you conider the case when $M_{ij}$ is non-zero for $(i,j)= (1,2), (2,3), (3,1)$, there's no perfect matching. Perhaps you meant that vertiices lie in a union of disjoint cycles? (mathings would be then "cycles of length 2", but then the problem dangerously reminds me of finding a hamiltonian cycle) $\endgroup$ Dec 7, 2011 at 13:06
  • $\begingroup$ I’m talking about bipartite graphs. Your matrix corresponds to the graph with vertex set $U\cup V$, $U=\{u_1,u_2,u_3\}$, $V=\{v_1,v_2,v_3\}$, and edge set $E=\{(u_1,v_2),(u_2,v_3),(u_3,v_1)\}$. This graph has a perfect matching, in fact, it is a perfect matching. $\endgroup$ Dec 7, 2011 at 13:12
  • 1
    $\begingroup$ It's useful to know it's NP complete, but note that you encode a 3-sat instance of $m$ clauses with $n$ variables into a $3m \times 3m$ matrix. I believe this can be solved in a number of steps which is polynomial in $2^m$, so this doesn't seem to directly answer my question whether you can go from $p^{n^2}$ to $p^n$. $\endgroup$ Dec 7, 2011 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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