4
$\begingroup$

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

Thanks for your help.

  • 0
    @JyrkiLahtonen, I'll edit my notation.2012-06-07

2 Answers 2

9

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

  • 0
    Not silly at all, it just happens to have a not very hard answer.2012-06-07
2

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.