Combinatorics – Number of Binary $M\times N$ Matrices with Even Row Sums, Even Column Sums, and $K$ Ones

combinatoricsmatrices

A combinatorial problem arising with certain checksums: When sending messages, the user data are protected by adding a parity bit for bit positions $1\dots8$ and a parity bit for each byte. So, the checksum protected messages have both even parity bitwise (columns) and even parity bytewise (rows). Now, bit failures will not be detected on the receiver side, if they occur on an even number of positions in rows and on an even number of positions in columns. I have to figure out the undetected error probability of this checksum for certain user message lengths ($1$ byte up to $15$ bytes). As a consequence, assuming equally distributed bit failure probability, I have to find out for each even number $K$ of bit failures, a (closed) formula for:

How many $M\times N$ binary matrices are there having even row sums and even column sums, whereby the number of $1s$ is $K$, $K$ even?

It's relatively easy to answer this question, if there is no restriction to a specific value of $K$. This is stated e.g. as exercise $20$ in Richard P. Stanleys "Enumerative Combinatorics, Vol I, 2nd Edition" (see also the answer to question 329932).

I tried to solve this problem with generating functions. In order to do so, I was looking for a proper decomposition similar to the examples e.g. in "Combinatorial Enumeration, ch. 3", especially section 3.4 "2-covers of a set and homeomorphically irreducible labeled graphs" from Goulden and Jackson. I'm thinking a lot about symbolic equations describing this type of matrices giving me proper decompositions, so that it can be translated into generating functions, but I was not successful so far.

A relatively simple one-dimensional example of decomposition is the essence of my answer to question 713409.

Another idea was to apply some two-fold variations of the inclusion-exclusion principle similar to the one-dimensional example which answers question 439596, regrettably without success so far.

Any helpful hints are welcome.
Thanks.

Best Answer

Here is a recursive formula: Let $A_M(N,L,K)$ be the number of matrices with $N$ columns and $M$ rows such that

  • all columns have an even number of ones
  • there are a total of $2K$ ones
  • the number of rows with an odd number of ones is $2L$.

Then $A_M(N,0,K)$ is the number we want to compute and for $N>0$: $$A_M(N,L,K) = \sum_{k=0}^K \sum_{l=0}^K A_M(N-1,l,k) {2l \choose K-k-L+l} {M-2l\choose K-k+L-l}.$$

From the definition we can see that $A_M(0,0,0) = 1$ and $A_M(0,L,K)=0$ for $L>0$ or $K>0$.

Reasoning is: We enumerating all matrices that can appear if we delete the last column. Assume we obtain a matrix with $2k$ ones and $2l$ rows with an odd number of ones. Then in the last column we add $2(K-k)$ ones of which $l_1$ are written in rows where there have been an odd number of ones before, and $l_2$ where the number of ones was even. Then $$2(K-k) = l_1+l_2 \\ 2L = 2l-l_1+l_2$$ from which we conclude $$l_1 = K-k-L+l \\l_2 = K-k+L-l.$$ Therefore, there are ${2l \choose l_1} {M-2l\choose l_2}$ ways to obtain the desired matrix.

Related Question