4
$\begingroup$

Find the number of $4 \times 4$ matrices such that its elements are $1$ and $-1$ and the sum of elements in each of its rows and columns is $0$.

I am only able to make trivial progress that there are $6$ ways to fill a row and $3$ ways to fill a column.I couldn't find a way to proceed further.

Can this be generalised to a $n \times n$ matrix under the same conditions?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You mean, of course, that the row sum of each of its rows is zero, not the sum of all the rows. (Similarly for columns.). $\endgroup$ – Mark Fischler Apr 24 '17 at 16:12
  • $\begingroup$ Thanks for pointing the error $\endgroup$ – user362405 Apr 24 '17 at 16:14
  • $\begingroup$ Can you say why there are 6 and 3 ?(!!!) $\endgroup$ – ancientmathematician Apr 24 '17 at 16:14
  • $\begingroup$ 6 is $\frac{4!}{2!2!}$ (since it has to be filled with 1 and -1 in 4 places) and 3 is $\frac{3!}{2!1!}$ $\endgroup$ – user362405 Apr 24 '17 at 16:17
  • $\begingroup$ If you replace the $-1$s by $0$s you get an adjacency matrix of a bipartite graph with four vertices in each half. The condition that the line-sums are zero translates into the graph being $2$-regular. $\endgroup$ – Lord Shark the Unknown Apr 24 '17 at 16:17
2
$\begingroup$

For the $4\times 4$ case, the number of ways is $90$ and the method is as follows:

The two $+$ in the first row can be placed in six ways. Take the first row to be $++--$; we will have to multiply the counting by six in the end.

Then the second row can be formed in three essentially different ways.

  • (a) $++--$: Now the third and fourth rows are completely determined; there is one such matrix.

  • (b) $--++$: Now the third row is completely arbitrary (the two $+$ can be in any positions) giving $6$ possibiliites; but then the fourth row will be determined.

  • (c) $+-+-$: There are four "equivalent" ways of doing this for the second row, The other three are $+--+$, $-++-$, and $-+-+$; consider just the first one $+-+1$. Then The items in the first and fourth coumn in the third and fourth rows are completely determined, and the little $2\times 2$ square remaining has two allowable arrangements (the $(3,2)$ element can be $+$ or $-$, after which the others are determined). So case (c) gives $4\times 2=8$ allowed arrangements.

    The total answer is $$ 6 (1+6 + 4\cdot 2) = 90 $$ ADDED

I am working on the general case of $2m \times 2n$.
For $2m \times 2$ the answer is of course $\binom{2n}{n}$.

For a $6\times 4$ matrix the answer appears to be $$ 20(1\cdot 1 + 9 \cdot 2 + 9 \cdot 6 + 1 \cdot 20) = 1860 = 31\cdot 60$$

The $4\times 2n$ cases

For $m=2$, the number of allowable $4\times 2n$ matrices is obtained by asking how many ($k$) minus signs in the second row lie under $+$ signs in the first row. The number of arrangements of the non-fixed elements of the third and 4-th row is of the form $\binom{2k}{k}$. You can get the expression in closed form: $$ N(4\times 2n) = \binom{2n}{n}\sum_{k=0}^n \binom{n}{k}^2\binom{2k}{k} = \binom{2n}{n} F\left( \left. \begin{array}{c} \frac12, -n, -n\\1,1 \end{array}\right| 4\right) $$ where the $F$ is a hypergeomentric function of three upper and two lower indices (sometimes written _3F2) as specified above.

$$ N(4,2) = 3\binom{2}{1}\\ N(4,4) = 15\binom{4}{2}\\ N(4,6) = 93\binom{6}{3}\\ N(4,8) = 939\binom{8}{4}\\ N(4,10) = 4653\binom{10}{5}\\ N(4,12) = 35169\binom{12}{6}\\ \vdots $$

The $6\times 2n$ cases

Counting the allowable $6\times 2n$ matrices is more difficult, since a column of the $4 \times 2n$ matrices underneath the first two rows are not fixed when the first two rows contain the same symbol in that column. I don't have, at this point, a good way of attacking this.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Neat. +1. But is there a typo at the start of case(c) and again later, the $1$ should be $-$. $\endgroup$ – ancientmathematician Apr 24 '17 at 16:32
  • $\begingroup$ In the end of case (c) I think it should be "so case (c) gives $4 \times 2 =8$".... a negligible typo... $\endgroup$ – user362405 Apr 24 '17 at 16:39
  • $\begingroup$ When done please add your progress on the generalisation $\endgroup$ – user362405 Apr 24 '17 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.