Question

Consider 4 × 4 matrices with their elements from {𝟎, 𝟏}. The number of such
matrices with even number of 𝟏s in every row and every column is

• A. 512
• B. 1025
• C. 1023
• D. 255

Hint:

Freely fill a 3x3 block (2^9 choices); the last row and last column are then forced by the even-parity requirement, and the last corner entry is automatically consistent - so the count is 2^9 = 512.

Answer 1

The Correct Option is A

We need to count 4×4 matrices over {0,1} such that every row sum and every column sum is even.

Step 1: Freely choose the top-left 3×3 sub-matrix.

The entries \( a_{ij} \) for \( 1 \le i,j \le 3 \) can be chosen arbitrarily as 0 or 1. There are \( 2^{9} = 512 \) ways to do this.

Step 2: Fix the 4th column entries for rows 1-3.

For each of the first three rows, the entry in column 4 is forced to whatever value (0 or 1) makes that row's sum even - it must equal the parity (XOR) of the first three entries in that row. This gives exactly one valid choice, not a free choice.

Step 3: Fix the 4th row entries for columns 1-3.

Similarly, for each of the first three columns, the entry in row 4 is forced to be the parity of the first three entries of that column, so that the column sum is even. Again, this is a single forced value for each of the 3 columns.

Step 4: The bottom-right entry \( a_{44} \) is automatically consistent.

The value required by row 4's parity and the value required by column 4's parity are always equal, because the total number of 1s placed so far has a parity that is consistent by construction (sum of all row parities = sum of all column parities). So \( a_{44} \) is uniquely and consistently determined - no contradiction arises and no extra freedom is introduced.

Step 5: Count the total.

Since only the free top-left 3×3 block contributes choices, and everything else is forced,

\[ \text{Total matrices} = 2^{3 \times 3} = 2^{9} = 512 \]

Final Answer: 512, option (A).