2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ oeis.org/A088217 $\endgroup$
    – Moritz Firsching
    Commented Jun 7, 2021 at 11:04
  • $\begingroup$ @MoritzFirsching: thx a lot. So i guess there's no explicit formula for this? $\endgroup$
    – user178596
    Commented Jun 7, 2021 at 11:12
  • $\begingroup$ @MoritzFirsching Would you like to write that in an answer to settle the question? $\endgroup$
    – Federico Poloni
    Commented Jun 7, 2021 at 11:50

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ 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)!$. $\endgroup$
    – Wojowu
    Commented Jun 7, 2021 at 15:37
  • 2
    $\begingroup$ @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) $\endgroup$
    – Peter Taylor
    Commented Jun 7, 2021 at 16:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – Nathaniel Johnston
    Commented Jun 7, 2021 at 16:41
  • $\begingroup$ @Wojowu I agree that the asymptotics would be even more interesting; don't know anything non-obvious about it though.. $\endgroup$
    – Moritz Firsching
    Commented Jun 7, 2021 at 18:30
  • $\begingroup$ 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. $\endgroup$
    – François Brunault
    Commented Jun 7, 2021 at 19:58

You must log in to answer this question.