# How to count matrices with rows and columns with an odd number of ones?

I proved that $\displaystyle \left(\sum_{k\, \rm odd}\binom{m}{k}\right)^{n-1}=\left(\sum_{k\;{\rm odd}}\binom{n}{k}\right)^{m-1}$

by counting matrices of size $n\times m$ with entries in $\{0,1\}$ such that the sum of columns and rows is odd. One can show that this can only happen if $m,n$ share the same parity.

What are other ways of counting such matrices?

By Davids observation, this is just $2^{(m-1)\times (n-1)}$, which suggests a better counting argument might be produced. Maybe something in the lines of my argument, but completing the $n-1\times m-1$ matrix freely with $1$s and $0$s, and showing its final rows and column may be completed so that it is a solution. I'll think about it.

Proof From $\sum_i a_{ij}=1\mod 2,\sum_j a_{ij}=1\mod 2$, we get $$\sum_i\sum_j a_{ij}=m\equiv n=\sum_j\sum_i a_{ij}\mod 2$$ so that $m,n$ have the same parity. It follows in particular that if a matrix with uneven columns and rows has all rows with an odd number of ones, there exists at least one column with an even number of $1$s. To prove the formula, we can produce an even number of ones in a bitstring of length $m$ in $\sum_{k\;\rm odd}\binom{m}{k}$ ways. Take the first $n-1$ rows and complete so that each has an odd number of ones. I claim the last row may be completed so that every column also has an odd number of ones.

Since the matrix built so far is $n-1\times m$; the first observation says there is a column with an even number of ones, for $m,n-1$ have opposite parity. Put a $1$, to obtain an $n-1\times m-1$ matrix, call it $M$. If $M$ has all columns with an odd number of $1$s, we're done, else there is some column with an even number of $1$s. Insert a $1$ in the corresponding place in the $n$-th row. Then we obtain an $n-1\times m-2$ matrix $M'$ with an odd number of $1$ in the rows (because we deleted $2$ columns, and our original rows had an odd number of ones), so there must exist a column with an even number of $1$s, thus we insert another $1$. Continuing, we see the algorithm stops at an odd numbers of $1$ always, and the proof is complete. The argument is of course symmetric in $m$ and $n$, since the method provides with any matrix of your liking, so the equation follows.

• Doesn't seem right. Can't you just evaluate the sums as $2^m$ and $2^n$, give or take a little? – Gerry Myerson Mar 20 '14 at 6:37
• @GerryMyerson I have corrected the formula. It holds say with $n=10,m=2$ to give $2^9=\binom {10} 9+\binom {10} 7+\binom {10 }5+\binom {10} 3+\binom {10} 1=512$. I'm 100% positive my proof is correct. =) – Pedro Tamaroff Mar 20 '14 at 6:48
• Then it seems to me the easiest proof is to evaluate each of the sums, as they should both come out to be simple powers of 2. – Gerry Myerson Mar 20 '14 at 8:14
• Should there be $\binom nk$ instead of $\binom mk$ in the sum on the RHS? The way it is written now we get for $n=10$ and $m=2$ the sum $\binom21+\binom23+\binom25+\binom27+\binom29=\binom21=2$. – Martin Sleziak Mar 20 '14 at 9:24

## 2 Answers

For $m>0$, we have $\sum_k (-1)^k \binom{m}{k} = (1-1)^m = 0$ and $\sum_k \binom{m}{k} = (1+1)^m = 2^m$. So $$\sum_{k \ \mathrm{odd}} \binom{m}{k} = (2^m-0)/2 = 2^{m-1}.$$

Your identity is $$(2^{m-1})^{n-1} = (2^{n-1})^{m-1}.$$

• Yes, of course. Now I'm thinking the proof I devised might be overly complicated perhaps. – Pedro Tamaroff Mar 20 '14 at 14:10
• David: I posted the question a bit late at night, and didn't care to check the observation you make. I am thinking about rephrasing the question to find another counting argument, so I hope you don't mind. I have duly upvoted. – Pedro Tamaroff Mar 20 '14 at 14:20

Here's the solution that gives the formula $2^{(n-1)(m-1)}$ right away, and happens to prove what David used.

Fill the $(n-1)(m-1)$ matrix freely. Complete the $n$-th column so the first $m-1$ rows have an odd number of ones, and use the method described in the post to complete the matrix so that it fits the conditions.