# Complexity of a matrix problem

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.

• 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. Oct 25, 2016 at 19:55
• 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}$. Oct 25, 2016 at 20:02
• @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). Oct 26, 2016 at 22:15
• 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. Oct 29, 2016 at 6:17
• 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}$. Oct 29, 2016 at 20:53

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.