Suppose you have a $5\times 5$ matrix where each element is either $1$ or $-1$. How many unique matrices are there such that each row and each column multiplies to $1$?
How to adapt this to a $N\times N$ matrix?
Asked
Active
Viewed 73 times
1 Answers
1
Consider the $4\times 4$ submatrix in the upper left corner. Fill this arbitrarily, which can be done in $2^{16}$ ways. Then, the first four entries in the rightmost column are determined, as are the first four entries in the bottom row. The only issue is whether the bottom right entry can be filled in.
Considering the $4\times 5$ submatrix, it has an even total number of $-1$'s, since each row does. Hence the parity in the $4\times 4$ submatrix equals the parity of the $4\times 1$ partial column on the right.
Repeating this process with the $5\times 4$ submatrix, we see that the parity of the $4\times 4$ submatrix equals the parity of the $1\times 4$ partial row on the bottom. Hence the partial row and partial column have the same parity, and therefore there is a way (and only one way) to finish the matrix.
None of this was dependent on $5$ being the dimension; for $N\times N$ the answer is $2^{(N-1)^2}$.
vadim123
- 82,796