# Number of Nice Matrices

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?

• google for "latin squares". – Wolfgang Jun 10 '15 at 11:57
• I think that is no formula is discovered until now but is it proved that there is no formula? – Z.A.Z.Z Jun 10 '15 at 12:00
• 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? – Vincent Jun 10 '15 at 12:16
• See en.wikipedia.org/wiki/Latin_square In particular, the OEIS links. – Kimball Jun 10 '15 at 12:29
• @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. – Douglas Zare Jun 10 '15 at 18:04

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

• is there a relation to the generalized problem that I have proposed? thanks – Z.A.Z.Z Jun 10 '15 at 12:43
• 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. – Vincent Jun 10 '15 at 12:44
• 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. – Vincent Jun 10 '15 at 12:49
• 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. – Gerry Myerson Jun 10 '15 at 13:14
• 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. – Vincent Jun 10 '15 at 13:40