Number of matrices n x n with n^2 different elements which have that same characteristic polynomial

[Max A.]

It is easy to see that every element of this sequence a(n) is a
multiple of 2*n! (for n>1) and a divisor of (n^2)!.

In particular, for n>1, 2*n! divides a(n) since simultaneous
permutations of rows and columns (of the total number n!) of a matrix
do not change its characteristic polynomial and neither do
transpositions (bringing the factor of 2). Moreover, b(n)=a(n)/(2*n!)
gives the number of non-equivalent (in terms of simultaneous
permutations of rows and columns, and transpositions) with equal
characteristic polynomials.

Every characteristic polynomial of n x n matrices on the same set of
n^2 variables appears exactly a(n) times, implying that a(n) divides
(n^2)!. The number of distinct characteristic polynomials is given by
c(n)=(n^2)!/a(n).

Now, fixing elements on the main diagonal, it can be shown that
binomial(n^2,n) divides c(n), implying that a(n) divides n!*(n^2-n)!
and that b(n) divides (n^2-n)!/2.

These are the values of a(n), b(n), and c(n) for n=1,2,3:
a(n): 1, 4, 12
b(n): 1, 1, 1
c(n): 1, 6, 30240

Max

On 1/8/07, Artur <grafix at csl.pl> wrote:
> Dear Seqfans,
> I'm asking: How many different matrices n x n with n^2 different elements
> occured which have that same characteristic polynomial
> We have to count all permutations n^2 elements in n x n matrix and count
> only these permutations
> which don't changed starting polynomial
> for 2 x 2 case
> we have 4 matrices X^2-(a+d)X+ad-bc
> a b   a c   d c   d b
> c d   b d   b a   c a
>
> BEST WISHES
> ARTUR
>
>



(Oops, just spotted this sitting in the mail queue due to greylisting)

Dean Hickerson <dean at math.ucdavis.edu> wrote:
:I don't know the answer to Leroy's first question.  The answer to the second
:one (Is the number of m's where floor(m/d(m)) = n finite for all n?) is "yes",
:since  d(m) < 2 sqrt(m)  for all m. [...]

Using this upper bound for simplicity, I get the following results for
a(n) = min(m), b(n) = max(m) and c(n) = count(m) : floor(m/d(m)) = n,
for 1<=n<=100:

a(n) = 1 5 7 28 11 13 44 17 19 63 23 51 55 29 31 49 69 37 77 41 43 91 47 147
b(n) = 6 12 30 48 60 72 120 96 144 180 140 240 216 252 360 336 420 224 312 480
c(n) = 5 4 9 3 7 5 6 11 7 4 8 6 9 5 4 16 7 4 8 7 11 5 10 7 7 8 7 12 9 6 10 8 8

This underlines the looseness of the upper bound: I checked up to m=4.101^2,
going about 8.7 times as far as I needed to for actual elements of b(n).

Hugo