1
$\begingroup$

Let's call a nice matrix a square matrix of size $n$ with elements from $\{1,...,n\}$ such that every row and every column contains all the number $1,...,n$, What is the number of nice matrices ?

a possible generalization is the following: the elements of the matrix are exactly $\{1,...,n^2\}$ and we ask that the sum of the element of the rows are equal.

always the question what is their number?

All comments are welcomed! Thanks in advance

$\endgroup$
  • 4
    $\begingroup$ google for "latin squares". $\endgroup$ – Wolfgang Jun 10 '15 at 11:57
  • $\begingroup$ I think that is no formula is discovered until now but is it proved that there is no formula? $\endgroup$ – Z.A.Z.Z Jun 10 '15 at 12:00
  • 1
    $\begingroup$ I find it hard to imagine a world where it can be proven that there is no formula, unless you make some very fierce restrictions on your definition of formula. How would you envision such a proof? $\endgroup$ – Vincent Jun 10 '15 at 12:16
  • $\begingroup$ See en.wikipedia.org/wiki/Latin_square In particular, the OEIS links. $\endgroup$ – Kimball Jun 10 '15 at 12:29
  • $\begingroup$ @Vincent: There actually are ways you can prove something has no computable formula, say if it encodes the halting problem, although I doubt something like that would work here. $\endgroup$ – Douglas Zare Jun 10 '15 at 18:04
4
$\begingroup$

Ok, the posibillity of no formula existing fascinated me so I followed Wolfgang's advise (even if it was not meant for me) and found a formula on the internet. I quote:

Theorem 3. Let $p(z)$ be any monic polynomial of degree $n$ and let $M_n$ be the family of all $n × n$ matrices over $\{−1,+1\}$. Then $$L_n = 2^{−n^2} \sum_{X \in M_n} p(\textrm{Per} X) \pi(X),$$ where Per$(X)$ is the permanent of $X$ and $\pi(X)$ is the product of the entries of $X$.

From: On the number of Latin squares by Brendan D. McKay and Ian M. Wanless.

However the following quote from the same article is maybe more relevant in some respects:

The literature contains quite a few exact formulas for $R_n$, but none of them appear very efficient for explicit computation (though Saxena [16] managed to compute $R_7$ using such a formula).

($L_n$ is the number of nice matrices, $R_n$ is the number of nice matrices whose first row and column read $1, \ldots, n$. $L_n$ can easily be computed from $R_n$ but is much bigger. The problem here more than anything else is that the numbers $R_n$ and $L_n$ grow perversely fast with $n$.)

$\endgroup$
  • $\begingroup$ is there a relation to the generalized problem that I have proposed? thanks $\endgroup$ – Z.A.Z.Z Jun 10 '15 at 12:43
  • $\begingroup$ The name for the generalized matrices is 'magic squares'. There is a huge literature on them, but I was surprised to find that the number of $n \times n$ magic squares is known for even less values of $n$ than the number of $n \times n$ Latin squares. $\endgroup$ – Vincent Jun 10 '15 at 12:44
  • $\begingroup$ Ok, my comment is phrased somewhat ambiguously. I mean: number of $n$ by $n$ Latin square is known up to $n = 11$ and number of $n$ by $n$ magic squares only up to $n = 5$. While it is true that for most $n$ the number 5 is less than the number of $n$ by $n$ Latin squares, that was not what I wanted to say. $\endgroup$ – Vincent Jun 10 '15 at 12:49
  • $\begingroup$ The generalized problem only asks the row sums to be equal. In a magic square, the column sums are also equal, as are the diagonal sums. The generalized problem is not about magic squares. $\endgroup$ – Gerry Myerson Jun 10 '15 at 13:14
  • $\begingroup$ Ah, I misread. The generalized problem seems then to be the $a = b$-case of this question: mathoverflow.net/questions/78906/… which apparently has no full answer. $\endgroup$ – Vincent Jun 10 '15 at 13:40

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.