4
$\begingroup$

So I want to find the number of ways to fill an $m\times n$ matrix with only 0s and 1s such that each row and column has an even number of 1s. I'm pretty stumped here. I've set up m+n equations summing the respective rows and columns yielding 0 mod2, but other than that I'm not too sure of a clean way to approach this.

The subsequent part asks for the same thing except that there's an odd number of 1s. Any hints and/or tips very much welcome.

|cite|improve this question
$\endgroup$
6
$\begingroup$

Hint: If $m=1$ or $n=1$, the problem is simple. So suppose they are both $\gt 1$.

Fill in everything with $0$'s and/or $1$'s except the bottom row and the rightmost column, in an arbitrary way.

Forget temporarily about the bottom right-hand corner. There is exactly one way to choose the rest of the bottom row and the rest of the rightmost column.

Now show that the bit in the bottom right corner that makes the sum of the full bottom row have even sum is the same bit that makes the full rightmost column have even sum. For this, use an old accounting principle.

Remark: For the question that was mentioned but not asked (odd sums) there will be parity considerations involving $m$ and $n$,

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Ah! So there's exactly as many ways to do it as there are ways to fill in the (m-1)x(n-1) submatrix arbitrarily? $\endgroup$ – AsinglePANCAKE Mar 14 '13 at 2:28
  • $\begingroup$ Yes. But you need to use a parity argument for the bottom right-hand corner. $\endgroup$ – André Nicolas Mar 14 '13 at 2:30
  • $\begingroup$ Oh, so I need to check that if the bottom row needs a one in that bottom corner then the right-most column needs one, too...and vice versa? $\endgroup$ – AsinglePANCAKE Mar 14 '13 at 2:37
  • $\begingroup$ Precisely. Suppose that in the $m-1$ by $n-1$, the sum of the bits is odd. Show that the sum of the bits in the bottom row, except for the corner, is also odd. Same for rightmost column except for the corner. So a $1$ in the corner will fix things. Similarly, show that if the sum of the bits in the $m-1$ by $n-1$ is even, then so is the sum of the bits in the bottom row, except for corner, and so on. The basic principle is an accounting one. Write the column sums of an $m-1$ by $n-1$, in dollars. Write the row sums. The sum of the column sums is the same as the sum of the row sums. $\endgroup$ – André Nicolas Mar 14 '13 at 2:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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