GATE 2026 CS1 Q.12: solution and answer

Official answer: ASource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

1. Every row sum and every column sum must be even, that is $\equiv 0(\mathrm{mod}2)$.

2. Fill the top-left $3\times 3$ block with any entries from $\{0,1\}$. It has $9$ cells, so there are $2^9$ choices.

3. Entries $a_{14},a_{24},a_{34}$ are each forced: each is the parity bit that makes its own row sum even.

4. Entries $a_{41},a_{42},a_{43}$ are each forced the same way: each is the parity bit that makes its own column sum even.

5. Choose $a_{44}$ so that row $4$ has an even sum. Then rows $1$ to $4$ are all even, so the sum of all $16$ entries is even. The first three columns each have an even sum, so column $4$ has sum $\text{(total)}-\text{(columns 1 to 3)}$, which is even. So this one choice of $a_{44}$ satisfies row $4$ and column $4$ together.

6. Hence every choice of the $3\times 3$ block extends to exactly one valid matrix. Conversely, any valid matrix is fixed by its top-left $3\times 3$ block, because all the other entries were forced above. Distinct blocks give distinct matrices.

7. Count $=2^{(4-1)(4-1)}=2^9=512$. Check on a $2\times 2$ matrix: the formula gives $2^1=2$, and the valid matrices are the all-zero matrix and the all-one matrix. This agrees.