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

<p>Another approach is to try to leverage the fact that this is in fact a system of <em>bilinear</em> 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...</p>

CC BY-SA 3.0
2016-10-31T14:11:00.963Z
Doesn't PSPACE follow from the problem being in NP?
M.B.
CC BY-SA 3.0
2016-10-31T14:20:17.450Z
@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.
Joshua Grochow
CC BY-SA 3.0
2016-10-30T18:11:29.630Z
2016-10-30T18:11:29.630Z
Joshua Grochow
<p>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.</p>

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

<p>Example: <span class="math-container">$A = \begin{bmatrix} 0 &amp; a_1 \\ a_2 &amp; 0 \end{bmatrix}$</span>, <span class="math-container">$B = \begin{bmatrix} b_1 &amp; 0 \\ 0 &amp; b_2 \end{bmatrix}$</span>. Not possible.</p>

<p>What is the computational complexity of this (in <span class="math-container">$n$</span>)?</p>

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

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

CC BY-SA 3.0
2016-10-25T18:47:07.030Z
I think you can solve it in polynomial time !
Fayez Abdlrazaq Deab
CC BY-SA 3.0
2016-10-25T19:55:39.160Z
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.
Andrew Morgan
CC BY-SA 3.0
2016-10-25T20:02:34.660Z
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}$.
Andrew Morgan
CC BY-SA 3.0
2016-10-26T16:04:55.650Z
Thank you @AndrewMorgan. First comment: that is true and there might be some interesting connections to PIT. OTOH checking if the matrix product can be made invertible can also be done by independently checking if A and B can be made invertible. That can be done effectively. Second comment: Unfortunately we cannot restrict ourself to that setting.
M.B.
CC BY-SA 3.0
2016-10-26T22:15:01.307Z
@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).
Joshua Grochow
CC BY-SA 3.0
2016-10-27T09:33:30.643Z
@JoshuaGrochow: I agree with both of your comments, and that was indeed what I meant by 'effectively'. But considering the determinant will also not tell me if the product can be *equal* to the identity matrix. One might consider solving a system of quadratic equations.
M.B.
CC BY-SA 3.0
2016-10-29T06:17:30.703Z
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.
domotorp
CC BY-SA 3.0
2016-10-29T20:53:02.327Z
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}$.
Andrew Morgan
<cc.complexity-theory>
Complexity of a matrix problem
M.B.
# Complexity of a matrix problem

(Asked by: username_0 on 2016-10-25)

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.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: I think you can solve it in polynomial time !  
> **username_2**: 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.  
> **username_2**: 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}$.  
> **username_0**: Thank you @AndrewMorgan. First comment: that is true and there might be some interesting connections to PIT. OTOH checking if the matrix product can be made invertible can also be done by independently checking if A and B can be made invertible. That can be done effectively. Second comment: Unfortunately we cannot restrict ourself to that setting.  
> **username_3**: @username_0: 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 username_2's second comment).  
> **username_0**: @JoshuaGrochow: I agree with both of your comments, and that was indeed what I meant by 'effectively'. But considering the determinant will also not tell me if the product can be *equal* to the identity matrix. One might consider solving a system of quadratic equations.  
> **username_4**: 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.  
> **username_2**: 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}$.  

---

## 1 answers

### Answer by username_3 on 2016-10-30. Score: 9

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

> **Comments:**
> **username_0**: Doesn't PSPACE follow from the problem being in NP?  
> **username_3**: @username_0: 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.  

---

