4
$\begingroup$

(I will not be surprised if this problem has been solved and/or has a trivial solution – I just do not know the right terminology to google for it.)

So the problem is as follows. I have an $m \times n$ matrix consisting of zeroes and ones. I treat the rows $\mathbf r_1, \mathbf r_2, \dotsc, \mathbf r_m$ of the matrix as vectors in $\mathbb R^n$ (or, to be more precise, in $\mathbb R_{\geq 0}^n$) and want to generate linear combinations that give vectors with non-negative entries:

$$ \alpha_1 \mathbf r_1 + \alpha_2 \mathbf r_2 + \dotsb \alpha_m \mathbf r_m = \mathbf h = (h_1, h_2, \dotsc, h_n) \in \mathbb R_{\geq 0}^n \,, $$ where the coefficients of the combination can be bothe positive, zeroes, and negative: $\alpha_1, \alpha_2, \dotsc, \alpha_m \in \mathbb R$.

In other words, I want to find many vectors from $\operatorname{span} \{\mathbf r_1, \mathbf r_2, \dotsc, \mathbf r_m\}$ that have non-negative entries. It goes without saying, that number of such vectors is infinite. But I am paricularly interested in generating vectors with different supports — this requires that some of $\alpha_1, \alpha_2, \dotsc, \alpha_m$ are sometimes negative. The routine can be (or should be?) randomised, and for my real task $n$ is usually around 100–500.

P.S. The support of the vector is a set of non-zero positions: $$ \operatorname{supp} (\mathbf h) = \{ i : h_i \neq 0 \} \,. $$

$\endgroup$
  • $\begingroup$ If you choose a certain support, then you have to decide the feasibility of a linear program. If feasible, you can sample the (non-empty) polytope. $\endgroup$ – Rodrigo de Azevedo Dec 12 '17 at 14:59
  • $\begingroup$ actually, that is what I have come to already :) But can you form this suggestion as an answer? So that I can formally "accept" it :) $\endgroup$ – Yauhen Yakimenka Dec 12 '17 at 22:55
  • $\begingroup$ If you arrived at that conclusion, then my "answer" can stay as a comment. I usually write non-telegraphic answers ;-) $\endgroup$ – Rodrigo de Azevedo Dec 13 '17 at 7: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.