I am trying to solve $Ax = b$ with the following properties:

  • $A$ is a boolean (aka. logical, binary) matrix, i.e., each entry in $A$ is either $0$ or $1$
  • $A$ is of size $m \times n$ where $m \ll n$
  • Each entry in $b$ is a non-negative integer
  • Each entry in $x$ should be a non-negative integer
  • It is known that such a $x$ exists

I am able to solve it as an integer linear program using standard LP solvers but how to solve it with a matrix based approach? Given the special properties of the problem, I believe there definitely would be some nice matrix based approach.

We may also relax $x$ to have non-negative real numbers and/or settle for an approximate solution if getting an exact solution in not easy.

  • $\begingroup$ Are you looking for something different than regular old Gaussian elimination? $\endgroup$ – wgrenard Oct 7 '16 at 5:35
  • $\begingroup$ @wgrenard Gaussian elimination doesn't ensure non-negative x $\endgroup$ – raghavsood33 Oct 7 '16 at 17:01
  • $\begingroup$ The fact that you talk about linear programming makes me wonder if you are interested in the complexity theory aspects of this problem. If so, you should state that fact explicitly and probably should post it on cs theory stack exchange. $\endgroup$ – Stella Biderman Oct 7 '16 at 18:05
  • $\begingroup$ @StellaBiderman Thanks for pointing! I added the #computational-complexity tag. I guess only mathematicians can exploit the special structure of this problem and comeup with maybe a closed-form expression for x $\endgroup$ – raghavsood33 Oct 7 '16 at 18:17
  • $\begingroup$ As a general rule of thumb, answers requiring pseudocode (which this is, if GE isn't fast enough) aren't "math-y enough" for here. CS theory stack exchange is your best best. $\endgroup$ – Stella Biderman Oct 7 '16 at 18:18

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.