Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

2 Answers 2

up vote 7 down vote accepted

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

share|improve this answer
    
@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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.