2

Find the number of $n\times n$ matrices whose entries are each 1 or -1 be such that the sum of the entries in each row and in each column is 0. ($n$ is given even)

I attempted this question in a way similar to an existing similar question about multiplication - Number of ways of filling $n \times n$ binary matrix.

I tried a similar approach here. Fill the upper-left $(n-1)\times(n-1)$ matrix with 1 or -1 arbitrarily. But the problem here is that if a single row gets filled with more than $n/2$ $1$s, then it's impossible to put the sum zero for that row. Similar is the problem with the column.

So, I could instead start at a $(n-2)\times(n-2)$ matrix, but again, I'm not quite sure how that evades the problem.

So, what is the logic for the better method?

Important note: the original question had $n=4$, but I have attempted to post a generalized question here. Hopefully, that does not make the answer too complex. If it does, please post a solution for $4\times4$ instead. Though, I'll still be more than happy to reward an answer with a bounty, if they are able to solve the general $n\times n$ case.

I attempted to count by hand for $4\times4$ matrices, hopefully it gives the people an intuition to count the general case as well.

Let us first set two $1$s in the first row in $^4C_2$ ways. The second row has three cases of placing 1s:

  1. both 1s below the first 1s - in only one way
  2. one 1 below the first one - in four ways
  3. neither of the 1s below the first row 1s - in only one way

Note that, in case 1, the rest of the matrix elements will be set automatically - to satisfy the property that the sum of the rows and the sum of columns is zero.

In case 2, for each way, we'll be able to fix automatically a few of the columns and rows, but four squares will be left - below the columns which have a 1 and -1 at their head. We have two more ways of placing 1s in those squares.

In case 3, only the first two rows are automatically fixed, and each columns would be similar to each other. So, wlog, choose the first column, place 1 and -1 below it in two ways. Similarly place 1 and -1 below the next one in two more ways. The remaining four squares are now automatically fixed.

This gives a total of $6\times(1\times1+4\times2+1\times2\times2)=78$ as the total number of ways. Unfortunately, this is the wrong answer. (acc my textbook) But, I've been unable to find the mistake here either.

Gaurang Tandon
  • 6,449
  • My intuition here is that this will indeed add a lot of complexity. I would try solving the $6 \times 6$ case, and see if anything gets simpler, but I doubt it would. – Theo Bendit Apr 21 '18 at 16:34
  • @TheoBendit Thanks for your input! I edited the question accordingly – Gaurang Tandon Apr 21 '18 at 16:36
  • 1
    This is the same as the number of $2m$-by-$2m$ matrices with entries $0$ or $1$ with each row and column sum equal to $m$. A more general problem is solved on pages 203-204 of Fulton, Young Tableaux, using the RSK correspondence. – fred goodman Apr 21 '18 at 18:10
  • 1
    In fact, an exact formula is available for the number $m$-by-$n$ matrices with entries $0$ or $1$ with prescribed row and column sums . – fred goodman Apr 21 '18 at 18:42

1 Answers1

3

Given that $n$ must be even, it is clear that this question is equivalent to another one asked on Mathematics SE:

"How many ways are there to fill up a $2n x 2n matrix with 1, -1 so that each column and each row has n 1s and n -1s?"

In your case for a $4\times4$ matrix the answer is 90. An explanation on how to derive this can be found at "Number of 4×4 matrices with sum along row or column 0", and a different one at "Number of ways to arrange signs in a grid"

The generalised problem is very difficult to solve, however, the method of enumerating them can be found "Asymptotic Enumeration of Dense 0-1 Matrices withEqual Row Sums and Equal Column Sums".

This question was also asked and answered on Math Overflow. For reasons of completeness and convenience, I have copied and collated the information that was given there.

As stated by others, this sequence can be found in OEIS A058527 which lists the first 7 terms.

An explicit (closed) formula for this was published about 30 years ago, but it was wrong. As the matter stands, there is no explicit formula. The values up to $m=15$ can be found here, and the values relevant to this specific question are all those of the form $B(2m,m; 2m,m)$.

For convenience, I have listed them below.

$$\begin{align} m=1. \quad & 2 \\ m=2. \quad & 90 \\ m=3. \quad & 297200 \\ m=4. \quad & 116963796250 \\ m=5. \quad & 6736218287430460752 \\ m=6. \quad & 64051375889927380035549804336 \\ m=7. \quad & 108738182111446498614705217754614976371200 \\ m=8. \quad & 34812290428176298285394893936773707951192224124239796250\\ m=9. \quad & 21882630320667689225357109687240364487595251549773\ 48944382853301460850000 \end{align}$$

$m=10.$ 27856726619148825494784078580561902698029561072477313921903857594739813713335069572835719440 ,

$m=11.$ 73598361490497320315061303329860141625489297388873097402577973995078475595177219907273524251166598220695445665280 ,

$m=12.$ 41166741168628144936713296088571382312319541605035039202139739426526710130553316487181153798718623434772470791046740497537457960747230000 ,

$m=13.$ 4955718943988940005004146237479895414479770954795218135246063162883554097069851160345377950138482450273137136644609946481127918748277794634799510166778789400000000 ,

$m=14.$ 130182965915524188822374132662598705148400755946368804279519820149265310510762181776582751351898520706779949869976891542842075030612982451615770950941110943399182350404672558394208550600000000 ,

$m=15.$ 755108153829514055973248475938007693494252921038915181695050280737084462727343843042892520013526446320417069829825720805149300044864243469236136642966675916041398513473858832514945641793476366441713887508829265486123827200 ,

Martin Roberts
  • 1,779