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 &amp; a_1 \\ a_2 &amp; 0 \end{bmatrix}$, $B = \begin{bmatrix} b_1 &amp; 0 \\ 0 &amp; 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.
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...