2
$\begingroup$

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

  • 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.2011-10-07

1 Answers 1

2

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