Given a two rectangular binary matrices $A$ and $B$ with dimensions $c\times a$ and $c \times b$ respectively, does there exist an invertible binary matrix C with dimensions $c \times c$ such that the total number of 1 entries in $CA$ and $C^TB$ is below a target threshold $t$?

Here we are working in $GF(2)$, where multiplication and addition are AND and XOR respectively.

What is the hardness of this problem? Are there approximation algorithms to this problem?

We know this problem is in $NP$, as a valid $C$ can be used as a certificate. Also, we know how to find $C$ when there exists the a solution for $t = a+b$, by using Gaussian Elimination.

  • $\begingroup$ Can you explain why you think that checking $t = a + b$ can be done in polynomial time? I suspect that this problem is GI-complete for $a = b = c$. Indeed, suppose that $A$ and $B$ are invertible matrices (they have dimensions $c \times c$, so the notion of invertibility makes sense). Then, $CA$ and $C^T B$ are invertible as well. There exists a solution with $t = a + b$ ones if and only if there are two permutation matrices $P$ and $Q$, such that $CA = P$, $B^T C = (C^T B)^T = Q$. Hence, the existence of a solution if equivalent to $PA^{-1} = B^{-T} Q$ (because both are equal to $C$). $\endgroup$ – Kaban-5 Aug 1 '20 at 15:55
  • $\begingroup$ Therefore, we need to check whether there are two permutation matrices $P$ and $Q$, such that $PA^{-1} Q^{-1} = B^{-T}$. Denote $L := A^{-1}$, $R := B^{-T}$. Then, we need to check whether there are two permutations $\sigma$ (corresponds to $P$) and $\tau$ (corresponds to $Q$), such that $L_{\sigma(i), \tau(j)} = R_{i, j}$. $\endgroup$ – Kaban-5 Aug 1 '20 at 15:56
  • $\begingroup$ If we treat $L$ and $R$ as "adjacency matrices" of bipartite graphs with $2c$ vertices ($c$ in both sides), this is an instance of graph isomorphism problem. Admittedly, there are some restrictions (graphs should be bipartite, have the same number of vertices in both sides and their "adjacency matrices" should be invertible). I doubt that those restrictions stop the problem from being GI-complete, though. $\endgroup$ – Kaban-5 Aug 1 '20 at 15:56
  • $\begingroup$ Here, by "adjacency matrix" I mean what is usually known as biadjacency matrix: en.wikipedia.org/wiki/Adjacency_matrix#Of_a_bipartite_graph Basically, the cell $(i, j)$ contains $1$ if and only if the $i$-th vertex of the left-hand side and the $j$-th vertex of the right-hand side are neighbours. $\endgroup$ – Kaban-5 Aug 1 '20 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.