Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
4  
Yes. Think about $(1-x_{i1})(1-x_{i2})...(1-x_{in})$. –  Ragib Zaman Oct 7 '11 at 12:05
2  
@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
add comment

1 Answer

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|improve this answer
    
Many thanks mate ! –  Tom Oct 7 '11 at 13:02
add comment

Your Answer

 
discard

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.