Q. about {0,1}-matrices.

[Peter Pein]

Artur schrieb:
> P.S.
> Sample 2 x 2:
> For case 2 x 2 we have only 2 different characteristic polynomials with
> frequences:
> 1  x^2-x-1   Golois S2 = C2
> 3  x^2-2x+1  Reducible
> __
> 4
> Will be interesting later do sequences with frequency of different
> Galois Tranzitive Groups
> 
> 
> ARTUR

With the following Mathematica program I get

Timing[A125587[5]]
--> {45.656 Second, 1603232}

(  Timing[A125587 /@ Range[4]] --> {0.125 Second, {1, 4, 68, 5008}}  )

The number of distinct char. polynomials is for n=1..4:

{1, 2, 12, 156}

My computer still counts for the case n=5.


Code:
In[1]:=
Clear[mats, A125587];
mats[1] = {{{1}}};
mats[(n_Integer)?Positive] :=
  mats[n] =
  Module[{mp1 = Flatten[
    Function[k,
      (Thread[(Append[#1, #2] & )[#1, PadLeft[k, n - 1]]] & ) /@ mats[n - 1]]
    /@ IntegerDigits[Range[0, 2^(n - 1) - 1], 2], 1]},
    Select[Flatten[Function[k, (Append[#1, PadLeft[k, n]] & ) /@ mp1] /@
      IntegerDigits[Range[2^n - 1], 2], 1], MatrixRank[#1] === n & ]
];

A125587[n_] := Length[mats[n]];


and the counting of distinct c.p. for n=5 has an end!

Timing[Length[Union[CharacteristicPolynomial[#1, x]& /@ mats[5]]]]
--> {454.984*Second, 5612}

Peter