2
$\begingroup$

Given a set of matrix $M_i$, by picking a sign coefficient $S_i\in\{-1,1\}$

How can I effectively find a combination that the sum $M^*= \sum_{i=1}^N S_iM_i$ is a nonnegative matrix.

i.e. ${M^*}_{i,j}\geq0$ $\forall i,j$

  • 1
    This is not necessarily possible: take $M_1=\left( \begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right)$ and $M_2=\left( \begin{array}{cc} 0 & 1 \\ -1 & 0 \end{array}\right)$. Then you can't find such $s_i$2012-09-12
  • 0
    How about if there exist such a combination?2012-09-12
  • 0
    It doesn't sound that it is always possibleto do so...2012-09-12
  • 0
    Yes but I mean if the matrix set guarantee there is such a combination.2012-09-12
  • 0
    Why not try to count how many positive elements there are in each matrix $M_i$. The ones with more positive than negative elements you give a $+$ sign, the ones with more negative elements a $-$ sign. The remaining ones you just search the space of possible combinations.2012-09-12
  • 0
    It looks like this problem can be rephrased as an [integer linear programming](http://en.wikipedia.org/wiki/Integer_linear_programming) problem, in which case, software for solving arbitrary integer linear programming instances should be able to handle this task.2012-09-13

0 Answers 0