# Counting matrices over $\mathbb{Z}/2\mathbb{Z}$ with conditions on rows and columns

I want to solve the following seemingly combinatorial problem, but I don't know where to start.

How many matrices in $\mathrm{Mat}_{M,N}(\mathbb{Z}_2)$ are there such that the sum of entries in each row and the sum of entries in each column is zero? More precisely find cardinality of the set $$\left\{A\in\mathrm{Mat}_{M,N}(\mathbb{Z}/2\mathbb{Z}): \forall j\in\{1,\ldots,N\}\quad \sum\limits_{k=1}^M A_{kj}=0,\quad \forall i\in\{1,\ldots,M\}\quad \sum\limits_{l=1}^N A_{il}=0 \right\}$$.

-
Is $\mathbb{Z}_2$ the residue class ring of integers or the ring of $2$-adic integers? I'm guessing the former, for otherwise the set is uncountable. – Jyrki Lahtonen Jun 7 '12 at 10:21
@JyrkiLahtonen, I'll edit my notation. – Norbert Jun 7 '12 at 10:35

Take any $(M-1)\times (N-1)$ matrix of $0$'s and/or $1$'s. We can in a unique way add a column of $0$'s and/or $1$'s at the right and bottom to make the sums of rows and columns congruent to $0$. In coding theory they would be called check bits. Note that the entry at bottom right is uniquely determined, for the sum of row sums must, by basic accounting principles, be equal to the sum of column sums.

So there are just as many restricted $M\times N$ matrices as there are unrestricted $(M-1)\times (N-1)$ matrices.

The number of restricted $M\times N$ matrices is therefore $2^{(M-1)(N-1)}$.

-
@ChrisEagle: Thanks, didn't notice. Same argument works for rectangular. – André Nicolas Jun 7 '12 at 10:29
Similar approach was used e.g. in this problem at AoPS. – Martin Sleziak Jun 7 '12 at 10:31
You are right, that was a silly question... – Norbert Jun 7 '12 at 10:36
Not silly at all, it just happens to have a not very hard answer. – André Nicolas Jun 7 '12 at 10:37

If you consider the entries of the matrices as unknowns, you have $N\cdot M$ unknowns and $N+M$ linear equations. If you think a little bit, you find out that these equations are not independent, but you get linearly independent equations if you omit one of them. So the solution space has the dimension $NM-N-M+1$, hence it contains $2^{MN-N-M-1}=2^{(N-1)(M-1)}$ elements.

-