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.