22
$\begingroup$

The following problem recently appeared in my research. Being no expert on algorithmic questions I have Googled extensively in the search for suitable problems to reduce from. I don't see how 3SAT would work, and even though ZOE is similar in spirit a reduction is not obvious. Another possibility would be the existential theory of the reals. That doesn't seem to be quite the match either but I might be wrong about that.

Problem: $A$ and $B$ are both $n\times n$-matrices over your favorite field. We assume that an arbitrary set of indices of $A$ are set to 0. Likewise, an arbitrary set of indices of $B$ are set to 0. Question: can we fill in the remaining indices of $A$ and $B$ such that $AB = I_n$?

Example: $A = \begin{bmatrix} 0 & a_1 \\ a_2 & 0 \end{bmatrix}$, $B = \begin{bmatrix} b_1 & 0 \\ 0 & b_2 \end{bmatrix}$. Not possible.

What is the computational complexity of this (in $n$)?

Any hints or ideas to where to look for similar results in the literature will be greatly appreciated.

EDIT (completely forgot about this post): In recent work which is available on the arXiv (if anyone is interested in the preprint let me know) we have shown that the problem is NP-hard over any finite field.

Improve this question
$\endgroup$
10
  • 4
    $\begingroup$ Provided the base field is large enough, the problem of checking whether you can make $AB$ invertible reduces to (the complement of) polynomial identity testing. Just observe that the determinant of $AB$ is a polynomial in the values of the missing entries. $\endgroup$
    – Andrew Morgan
    Oct 25, 2016 at 19:55
  • 3
    $\begingroup$ Also, the case where we restrict the entries of $A$ and $B$ to be zero-one, and the characteristic of the field is larger than $n$, reduces to bipartite perfect matching. You can imagine picking for each index $i$ another index $k_i$ so that you set $A_{i,k_i} = B_{k_i,i} = 1$ and the remaining entries zero. (Putting more ones than this can only hurt.) Then the condition $AB = I_n$ can be expressed as a bipartite graph with the indices $i$ on the left, choices of $k_i$ on the right, and edges for $(i,k_i)$ pairs for which we can set $A_{i,k_i}$ and $B_{k_i,i}$. $\endgroup$
    – Andrew Morgan
    Oct 25, 2016 at 20:02
  • 2
    $\begingroup$ @M.B.: Also, note that while checking if $AB$ can be made invertible is the same as checking whether both $A$ and $B$ can, separately, be made invertible, checking whether $AB$ can be made invertible isn't the same as checking whether $AB$ can be made the identity. For checking whether $A$ (resp. $B$) can be made invertible, you say "that can be done effectively," but in your setting this is equivalent to checking for a perfect matching among the support of $A$ (resp. $B$) (same problem, but slightly different setting from Andrew Morgan's second comment). $\endgroup$
    – Joshua Grochow
    Oct 26, 2016 at 22:15
  • 2
    $\begingroup$ Some special case of this problem seems likely to in PPAD, like the Linear Complementarity Problem: kintali.wordpress.com/2009/08/04/linear-complementarity-prob‌​lem This would show that finding a solution is hard. $\endgroup$
    – domotorp
    Oct 29, 2016 at 6:17
  • 2
    $\begingroup$ In case others haven't already figured this out, there's a choice of $A,B$ (over any field) for which $AB = I$, but for which the perfect matching test fails. ie there is no permutation matrix $P$ so that $P$ is supported on the support of $A$, and $P^{-1}=P^{\intercal}$ is supported on the support of $B$. The choice is given by $A=\begin{bmatrix}1&-1&0\\1&0&1\\1&-1&1\end{bmatrix}$ and $B=\begin{bmatrix}1&1&-1\\0&1&-1\\-1&0&1\end{bmatrix}$. $\endgroup$
    – Andrew Morgan
    Oct 29, 2016 at 20:53

1 Answer 1

Reset to default
9
+25
$\begingroup$

Well, here's a not-horrible upper bound over $\mathbb{C}$: $\mathsf{PSPACE}$, or assuming the Riemann Hypothesis, $\mathsf{AM}$. This is because for any given patterns of zeros for $A,B$, checking whether one can make $AB=I_n$ is checking whether a certain system of $n^2$ integer polynomial equations has a solution in $\mathbb{C}$, and this can be done in these upper bounds, by Koiran.

Another approach is to try to leverage the fact that this is in fact a system of bilinear equations. Solving bilinear equations is equivalent to finding "rank 1" solutions to linear equations. I've been trying to determine if there are better upper bounds for solving bilinear systems in general, but with no luck so far. It's also possible that one could leverage the particular structure of these bilinear equations to get something better than what's known in general...

Improve this answer
$\endgroup$
2
  • $\begingroup$ Doesn't PSPACE follow from the problem being in NP? $\endgroup$
    – M.B.
    Oct 31, 2016 at 14:11
  • 2
    $\begingroup$ @M.B.: Over finite fields the problem is obviously in NP (just show the setting of variables), which is a better upper bound than AM, even. When the input is integer polynomials but you ask for a solution in the complex numbers, when there is a solution it's not even obvious that you can write it down in any finite amount of memory, let alone polynomially-bounded. $\endgroup$
    – Joshua Grochow
    Oct 31, 2016 at 14:20

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.