1
$\begingroup$

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 $.

$\endgroup$
  • $\begingroup$ 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/… $\endgroup$ – Gerry Myerson Jul 1 '14 at 11:29
  • $\begingroup$ Have you had a look? $\endgroup$ – Gerry Myerson Jul 2 '14 at 12:32
  • $\begingroup$ 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. $\endgroup$ – user1024 Jul 2 '14 at 12:37
  • $\begingroup$ 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)? $\endgroup$ – Gerry Myerson Jul 2 '14 at 12:52
  • $\begingroup$ 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? $\endgroup$ – user1024 Jul 2 '14 at 15:59
2
$\begingroup$

I post a summary of comments, since nobody wrote an answer.


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 Birkhoff 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.

$\endgroup$

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.