Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.