How to pick correct sign on matrices such that their sum is a nonnegative matrix?

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$

-
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$ – Dennis Gulko Sep 12 '12 at 9:03
How about if there exist such a combination? – Rein Sep 12 '12 at 9:03
It doesn't sound that it is always possibleto do so... – Belgi Sep 12 '12 at 9:03
Yes but I mean if the matrix set guarantee there is such a combination. – Rein Sep 12 '12 at 9:05
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. – Raskolnikov Sep 12 '12 at 20:49