Question 12

For any $n \times n$ matrix over $\{0, 1\}$ with even row sums and even column sums, we can choose all $(n-1)^2$ entries in the top-left $(n-1) \times (n-1)$ submatrix arbitrarily in $2^{(n-1)^2}$ ways:

• For each row $i \in \{1, \dots, n-1\}$, the entry $a_{i,n}$ is uniquely determined so that row $i$ has an even number of $1$s.
• For each column $j \in \{1, \dots, n-1\}$, the entry $a_{n,j}$ is uniquely determined so that column $j$ has an even number of $1$s.
• Finally, $a_{n,n} \equiv \sum_{i=1}^{n-1} a_{i,n} \equiv \sum_{i=1}^{n-1} \sum_{j=1}^{n-1} a_{i,j} \equiv \sum_{j=1}^{n-1} a_{n,j} \pmod 2$ is uniquely and consistently determined.

For $n = 4$, the number of such matrices is $2^{(4-1)^2} = 2^9 = 512$.