# 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? Commented Mar 20, 2014 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
Commented Mar 20, 2014 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. Commented Mar 20, 2014 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$. Commented Mar 20, 2014 at 9:24

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