GATE 2026 CS (CS1) – Question 12
Consider $4 \times 4$ matrices with their elements from $\{0, 1\}$. The number of such matrices with even number of $1$s in every row and every column is
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) 512
Explanation
Consider an $n \times n$ matrix with entries from $\{0, 1\}$ where $n = 4$.
We require the sum of elements in each of the 4 rows and each of the 4 columns to be even modulo 2.
The top-left $(n - 1) \times (n - 1) = 3 \times 3$ submatrix can have its 9 entries chosen arbitrarily from $\{0, 1\}$, giving $2^{3 \times 3} = 2^9 = 512$ choices.
Once these 9 entries are chosen:
1. The 4th entry in each of the first 3 rows is uniquely determined to make each row sum even.
2. The 4th entry in each of the first 3 columns is uniquely determined to make each column sum even.
3. The bottom-right entry $(4, 4)$ is uniquely determined. Since the sum of all elements in the first 3 rows has the same parity as the sum of all elements in the first 3 columns, the parity requirement for row 4 and column 4 is consistent and satisfied by exactly one choice of entry $(4, 4)$.
Thus, the total number of such matrices is:
$$2^{(n-1)(n-1)} = 2^{3 \times 3} = 2^9 = 512$$
Therefore, option (A) is correct.