2

That is, to fill in an $n\times n$ matrix $M$ with all the first $n^2$ positive integers, how many different determinants $\det(M)$ could we get?

If the number is denoted by $f(n)$, is it an explicit function of $n$? Or is it just some kind of meaningless function that can hardly be written down?

1 Answers1

3

I answer because Federico Poloni suggested it in a comment.

This sequence is in the oeis: oeis.org/A088217

I don't think the question is very well defined, what does "explicit function of $n$" mean? And what is a "meaningless function"? The number is computable of course, for example this sage code could be considered a "function" for this number.

def a088217(n):
        return len(set(Matrix(n, n, [p(i)  for i in range(1, n^2 + 1)]).det() for p in Permutations(n^2)))

Maybe a more meaningful question would be "What is the complexity of calculating that number?" For this I would expect one can do better than $O(n!\cdot n^3).$

Moritz Firsching
  • 10,663
  • 3
    I personally would be more interested in its asymptotics than the complexity of computing it. Do you happen to know anything about that? It is significantly smaller than the most obvious bound of $(n^2)!$. – Wojowu Jun 07 '21 at 15:37
  • 2
    @Wojowu, permuting rows or columns only changes the sign of the determinant, so the obvious bound is really $2(n^2)!(n!)^{-2}$ (although the point that the values are considerably smaller still stands) – Peter Taylor Jun 07 '21 at 16:01
  • 1
    Gaspar's determinant theorem can be used to further reduce this bound to something like $O(n^{5n/2})$, which appears to have at least roughly the right growth rate. – Nathaniel Johnston Jun 07 '21 at 16:41
  • @Wojowu I agree that the asymptotics would be even more interesting; don't know anything non-obvious about it though.. – Moritz Firsching Jun 07 '21 at 18:30
  • Using the techniques in this MO answer, it is possible to compute the expected value of $\det(A)^2$ where $A$ is a $n \times n$-matrix whose coefficients are independent random variables in ${1,\ldots,n^2}$. Your setting is different in that the coefficients are all distinct, but it gives an idea of the size of the determinant. – François Brunault Jun 07 '21 at 19:58