Probability that a random binary matrix has at least one zero-row or zero-column

Question

Let $M$ be a random $(0,1)-matrix$ where the occurrence of $0$ or $1$ is equiprobable in each entry. The probability that this randomly generated Matrix $M$ has at least one zero-row or zero-column is

$$\sum_{k=1}^{2n} (-1)^{k-1} \sum_{m=0}^{k} \binom{n}{m} \binom{n}{k-m} 2^{m(k-m)-kn}$$

Can anyone explain this to me using the inclusion exclusion principle? Thank you!

Answer 1

First off, I don't think you stated it, but it seems clear that $M$ is a $n \times n$ matrix.

For any such matrix $M$, let's define $z(M)$ to be the number of all-zero rows plus the number of all-zero columns. We wish to count how many $M$ exist with $z(M) \geq 1$. We'll do this via the inclusion-exclusion principle, first counting the number of $M$ with $z(M)$ at least 1, then subtracting the number with $z(M)$ at least 2, then adding the ones with $z(M)$ at least 3, etc.

Once we have the count, we'll divide by $2^{n^2}$ to get the probability.

So, suppose you had to construct all the matrices with $z(M)$ at least $k$. How would you do this?

Well, you'd first need to decide how many all-zero rows there are: some number between $0$ and $k$. Call this number $m$, so that the number of all-zero columns is $k-m$. Now, how many ways are there to select $m$ rows and $k-m$ columns out of this $n \times n$ matrix? Well, that's just:

$$ \binom{n}{m} \binom{n}{k-m} $$

Now, if we've selected our rows and columns that we want to have as zero, how many matrices do we have? To work that out, we need to know how many elements of the matrix aren't in our selected rows or columns. We've got $n^2$ elements total, $mn$ elements in our rows, $(k-m)n$ elements in our columns, and $(k-m)m$ elements in both our all-zero rows and all-zero columns so we have $n^2 - mn - (k - m)n + (k-m)m = n^2 + (k-m)m - kn$ elements that we can choose freely as either 0 or 1.

So the number of matrices with $z(M)$ at least $k$ with $m$ all-zero rows is:

$$ \binom{n}{m} \binom{n}{k-m} 2^{n^2 + (k-m)m - kn} $$

Now, summing that over all possible values for $m$:

$$ \sum_{m=0}^k\binom{n}{m} \binom{n}{k-m} 2^{n^2 + (k-m)m - kn} $$

And that is - with duplicates counted extra - the number of matrices with $k$ all-zero rows and columns.

Combining them with alternating signs as the inclusion-exclusion principle uses gives:

$$ \sum_{k=1}^{2n}(-1)^{k-1}\sum_{m=0}^k\binom{n}{m} \binom{n}{k-m} 2^{n^2 + (k-m)m - kn} $$

And divide by $2^{n^2}$ to get the probability, as mentioned before.