# How many nonnegative integer matrices of size $N$ have all row and column sums equal to $D$?

Given the positive integer $N$ and $D$, generate all the non-negative integer matrices which satisfy

1. matrix dimension is $N\times N$;
2. sum of each row elements equals to $D$
3. sum of each column elements equals to $D$

when $N\leq 5, D\leq 8$, there are how many matrices in each $\langle N,D\rangle$.

• This isn't so easy. There are research papers on the number of such matrices. For the given parameters, might be simplest just to bung it on a computer and count the matrices. This looks useful: drvinceknight.blogspot.com.au/2013/05/… – Gerry Myerson Jul 1 '14 at 11:29
• Have you had a look? – Gerry Myerson Jul 2 '14 at 12:32
• Sorry, i am late. you know the damned GFW, i can't get into the link, can you copy that or show me another one. – user1024 Jul 2 '14 at 12:37
• It's a bit long to copy. Can you send email to the guy who wrote it, KnightVA at cardiff.ac.ukq (but leave off the q at the end)? – Gerry Myerson Jul 2 '14 at 12:52
• Thanks, i have bypassed the GFW, i have read the blog, i got this: 1. the matrix that satisfies these condition is called semi magic matrix. 2. |SMS(3,r)|=C(44,r)+C(34,r)+C(24,r) 3. |SMS(n,2)|=taylor(f(x),x,0,n).coeff(x^n)*(factorial(n)^2), f(x) = e ^ (x / 2)/(sqrt(1 - x)) But when n,r are others, what's the result? – user1024 Jul 2 '14 at 15:59

### Gerry Myerson:

This isn't so easy. There are research papers on the number of such matrices. For the given parameters, might be simplest just to bung it on a computer and count the matrices. This looks useful: Counting semi-magic squares from drvinceknight.blogspot.com. I did find a couple of other papers that should help:

MR0332532 (48 #10859), Ehrhart, Eugène, Sur les carrés magiques, C. R. Acad. Sci. Paris Sér. A-B 277 (1973), A651–A654. Author's summary: "Le nombre de carrés magiques de côté $c$ et de somme $n$ est un polynôme en $n$ de degré $(c−1)^2$.

MR0317970 (47 #6519), Stanley, Richard P, Linear homogeneous Diophantine equations and magic labelings of graphs, Duke Math. J. 40 (1973), 607–632.

The Stanley paper says, Let $H_n(r)$ denote the number of squares of side $n$, with nonnegative integral entries in each of the $n^2$ cells into which the square can be divided, such that every line-sum in the direction of an edge is $r$. The reviewer noted that $H_n(r)$ is a polynomial in $r$ of degree $d=(n-1)^2$ with rational coefficients, satisfying the relations $H_n(−t)=0$, $t=1,2,\dots,n−1$, and $H_n(r)=(−1)^dH_n(−n−r)$, $r\ge0$. If you can calculate the answers for some small values of $N,D$ then the Online Encyclopedia of Integer Sequences might have your answers.

Two more papers:

MR2023999 (2004k:05009), Beck, Matthias; Cohen, Moshe; Cuomo, Jessica; Gribelyuk, Paul, The number of "magic'' squares, cubes, and hypercubes, Amer. Math. Monthly 110 (2003), no. 8, 707–717.

MR2519852 (2010h:52017), De Loera, J. A.; Liu, F.; Yoshida, R., A generating function for all semi-magic squares and the volume of the Birkhoff polytope, J. Algebraic Combin. 30 (2009), no. 1, 113–139.

OEIS sequences oeis.org/A122751 and oeis.org/A002817 might be helpful.

### user2468587:

I found this paper: The Ehrhart polynomial of the Birkhoﬀ polytope, it told me how to get $H_n(t)$, it's really useful. In the same website, Ehrhart polynomials for $n =1, \dots , 9$ are given, that's amazing.