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