# 4 by 4 Matrix Puzzle

I was solving the puzzle for the Company interview exam. I found this puzzle, I cannot come up with the solution. How to solve it and what is the correct answer?

Determine the number of $4\times 4$ matrices having all entries 0 or 1 that have an odd number of $1$s in each row and each column.

-
What company asks these questions? –  copper.hat Jul 29 '12 at 6:53

Fill the upper-left hand $3\times 3\,$ arbitrarily with $0$'s and/or $1$'s. This can be done in $2^9$ ways.
For any such choice of $0$'s and/or $1$'s, fill in the first three entries in the fourth row, and the first three entries in the fourth column, so that the number of $1$'s in each of the first three columns, and in each of the first three rows, is odd. This can be done in precisely one way.
Now put a $0$ or a $1$ in the lower right-hand corner, to make the number of $1$'s in the bottom row odd. It turns out that this makes the number of $1$'s in the rightmost column odd. To check this, work modulo $2$.
Yes, the answer is $2^9$. And it does generalize. –  André Nicolas Jul 28 '12 at 22:46
In general, there are $2^{(m-1)(n-1)}$ solutions if $m-n$ is even, and no solutions if $m-n$ is odd. The basic strategy should be unchanged. –  Erick Wong Jul 28 '12 at 22:59