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

Let $X$ be an $m\times n$ matrix, such that all of its elements are binary, i.e., for every $1\leq i\leq m$ and $1\leq j\leq n$ holds $x_{ij}=(X)_{ij}\in\{0,1\}$.

Is there any possible way to express the number of non-zero rows of $X$ (that is, the number of rows in which there exist at least one non-zero element) as a multivariate polynomial (s.t. $x_{ij}$ are the variables) ?

share|cite|improve this question
Yes. Think about $(1-x_{i1})(1-x_{i2})...(1-x_{in})$. – Ragib Zaman Oct 7 '11 at 12:05
@Ragib: You could post that as an answer so the question won't remain unanswered, since it's likely that noone will have anything to add to that. – joriki Oct 7 '11 at 12:26
up vote 3 down vote accepted

As per joriki's suggestion, I may as well post my above comment as an answer.

The idea is to think about how to detect even a single $1$ entry. If the job was to detect the presence of a $0$ in a row, then $x_{i1} x_{i2} x_{i3} \cdots x_{in} $ would do the job - it would be $0$ if and only if any entries were zero. So then after thinking about it for a few seconds (or as I did, a few minutes) we realize we can detect $1$'s in the same way, by instead considering

$$ \prod_{j=1}^n (1-x_{ij}) =(1-x_{i1})(1-x_{i2})...(1-x_{in}),$$ which is $0$ if and only if any of the entries in a row is $1$, and is $1$ otherwise (that is, if all entries are $0$).

So then the number of zero rows is given by $ \sum_{i=1}^m \prod_{j=1}^n (1-x_{ij})$, meaning the number of non-zero rows is equal to $$m -\sum_{i=1}^m \prod_{j=1}^n (1-x_{ij}).$$

share|cite|improve this answer
Many thanks mate ! – User1234 Oct 7 '11 at 13:02

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.