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

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ google for "latin squares". $\endgroup$
    – Wolfgang
    Commented Jun 10, 2015 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
    Commented Jun 10, 2015 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
    Commented Jun 10, 2015 at 12:16
  • $\begingroup$ See en.wikipedia.org/wiki/Latin_square In particular, the OEIS links. $\endgroup$
    – Kimball
    Commented Jun 10, 2015 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
    Commented Jun 10, 2015 at 18:04

1 Answer 1

Reset to default
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$.)

Improve this answer
$\endgroup$
5
  • $\begingroup$ is there a relation to the generalized problem that I have proposed? thanks $\endgroup$
    – Z.A.Z.Z
    Commented Jun 10, 2015 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
    Commented Jun 10, 2015 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
    Commented Jun 10, 2015 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
    Commented Jun 10, 2015 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
    Commented Jun 10, 2015 at 13:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .