GATE CS 2026 Set 1 Q2 — Combinatorics: Counting, Recurrence Relations, Generating Functions

To find the number of $4 \times 4$ matrices with elements from $\{0, 1\}$ such that every row and every column has an even number of $1$s, we can analyze the degrees of freedom in choosing the elements.

Let the matrix be $M = (a_{ij})$ of size $4 \times 4$. Consider the top-left $3 \times 3$ submatrix:

Each of these $3 \times 3 = 9$ elements can be chosen independently as either $0$ or $1$. There are $2^9 = 512$ ways to choose these elements.

Once these $9$ elements are chosen, the remaining elements of the $4 \times 4$ matrix are uniquely determined to satisfy the even-parity constraints:

1. First 3 elements of the 4th column: For each row $i \in \{1, 2, 3\}$, the element $a_{i4}$ must be chosen such that the row sum is even: $$a_{i4} \equiv \sum_{j=1}^3 a_{ij} \pmod 2$$ This uniquely determines $a_{14}, a_{24},$ and $a_{34}$.
2. First 3 elements of the 4th row: For each column $j \in \{1, 2, 3\}$, the element $a_{4j}$ must be chosen such that the column sum is even: $$a_{4j} \equiv \sum_{i=1}^3 a_{ij} \pmod 2$$ This uniquely determines $a_{41}, a_{42},$ and $a_{43}$.
3. The corner element $a_{44}$:
   • To satisfy the parity of the 4th row: $$a_{44} \equiv \sum_{j=1}^3 a_{4j} \equiv \sum_{j=1}^3 \sum_{i=1}^3 a_{ij} \pmod 2$$
   • To satisfy the parity of the 4th column: $$a_{44} \equiv \sum_{i=1}^3 a_{i4} \equiv \sum_{i=1}^3 \sum_{j=1}^3 a_{ij} \pmod 2$$
   Both conditions yield the exact same value for $a_{44}$. Thus, $a_{44}$ is consistently and uniquely determined.

Since the remaining elements are uniquely determined for any choice of the $3 \times 3$ submatrix, the total number of such matrices is: