# Expressing the number of non-zero rows of a binary matrix as a polynomial

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) ?

-
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

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}).$$