Number of 4x4 matrices such sum of all rows and columns is zero.

1.6k Views Asked by At

The number of matrices $A = [a_{ji}], 1 \le i,j \le 4$ such that $a_{ij} = +- 1$ and $\sum_{i = 1}^{4}a_{ij} = \sum_{j=1}^{4}a_{ij} = 0$ is...

I solved it by first selecting two values of “i” which is $\binom{4}{2}$ and two values of “j” similarly. Now if I fill thes four positions by 1, the value of remaining positions also get fixed because sum of all rows and columns is zero. So answer should be 36 $(\binom{4}{2}\times \binom{4}{2})$but the correct answer is 90.

Why this method is wrong and what is the correct way of solving this?

2

There are 2 best solutions below

0
On BEST ANSWER

You are both over-counting and under-counting!

First, you are over-counting:

Suppose you first pick $i=1,2$ and $j=1,2$. So, $a_{11}$, $a_{12}$, $a_{21}$, and $a_{22}$ are all set to $1$. But that forces $a_{33}$, $a_{34}$, $a_{43}$, and $a_{44}$ to be a $1$ as well.

OK, but now start with $i=3,4$ and $j=3,4$. Then $a_{33}$, $a_{34}$, $a_{43}$, and $a_{44}$ are a $1$. But that forces $a_{11}$, $a_{12}$, $a_{21}$, and $a_{22} $ to $1$. So, you get the exact same matrix.

But, you are also under-counting, since it is not true that there must be two row with the same entries being a $1$. Consider:

$$\begin{bmatrix} 1& 1 &-1 & -1 \\ -1& 1 &1 & -1 \\ -1& -1 &1 & 1 \\ 1& -1 &-1 & 1 \\ \end{bmatrix}$$

OK, here's how you can get them all.

First, pick two entries from the first column that are a $1$

Then, for the second row, you have the following possibilities:

$A$. Pick the exact same entries. That can be done in one way only, and it forces the rest of the matrix, so $ 1$ possibility

$B$. Pick the 'opposite' entries (example, if you picked entries $1$ and $2$ for row $1$, pick $3$ and $4$ for row $2$). That can also only be done in one way. Now, notice that for the third row, since rows $1$ and $2$ do not share any entries, you can still pick any two entries from row $3$, so $6$ possibilities for that one. Of course, after row $3$ is done, row $4$ is forced, so option $B$ leads to a total of $6$ possibilities

C. Row $2$ shares one entry with row $1$, which can be done in $4$ ways ($2$ choices for the shared entry, and $2$ for the other two entries. (Example: if the entries for row $1$ are $1$ and $2$, then for row $2$ we can pick $1$ and $3$, $1$ and $4$, $2$ and $3$, and $2$ and $4$)). Then for row $3$, you cannot use the shared entry from rows $1$ and $2$, but you have to pick the one non-shared entry, and then one out of the remaining $2$ entries, so $2$ options there (Example, if you picked entries $1$ and $2$ for row $1$, and entries $1$ and $3$ for row $2$, then the entries for row $3$ can only be $2$ and $4$ or $3$ and $4$)

And again, since row $4$ is now fixed, option $C$ gives $4\cdot 2 = 8$ possibilities.

Finally, since there were $6$ ways to pick the first two entries for row $1$, that gives $6 \cdot(1 + 6 + 8) = 90$ possibilities

1
On

You are counting it wrong,you only count some of teh matrices.

What do you mean by picking 2 values for $i$ and two for $j$? To understand the problem, consider this matrix $$\begin{bmatrix} -1& 1 &-1 & 1 \\ -1& -1 &1 & 1 \\ 1& -1 &1 & -1 \\ 1& 1 &-1 & -1 \\ \end{bmatrix}$$

Which are the two $i$'s and 2 $j$'s which give this matrix?