Characteristic polynomial of integer matrix has wrong degree

[vneiger]

An issue in SageMath was raised here sagemath/sage#35846 . When computing the characteristic polynomial of some 35 x 35 integer matrix, we get x^27, which does not have the correct degree. The same issue already appears within LinBox. Running the piece of code attached, with the current git version of LinBox, and with the matrix from the above Sage issue (attached as well in sms format), I get:

$ ./issue_charpoly
Characteristic Polynomial is X^27

whereas we expect a polynomial of degree 35. Trying with the same matrix on some Modular<double> coefficient domain (for this, comment/uncomment a couple of lines in the code), everything seems to be fine.

I wondered about some problem due to randomization and briefly tried to force a deterministic algorithm, but did not find quickly how to do this. May be related to #53 .

issue_sage_35846_charpoly.zip

[gilvillard]

I've raised linbox-team/fflas-ffpack#381.
I also get x^27 with ntl. I get a polynomial with nonzero coefficients between x^27 and x^35 without ntl.
The behaviour seems to be wrong mod p already, hence both situations are affected (ok differently).

[bdsaunders]

Just fyi, when i use the blackbox method in linbox/algorithms/frobenius-small.h I get usertime: 0.005487 x^13 x^9 x^7 x^5 x is that what it should be?

…

On Mon, Sep 4, 2023 at 12:20 PM Gilles Villard ***@***.***> wrote: I've raised linbox-team/fflas-ffpack#381 <linbox-team/fflas-ffpack#381>. I also get x^27 with ntl. I get a polynomial with nonzero coefficients between x^27 and x^35 without ntl. The behaviour seems to be wrong mod p already, hence both situations are affected (ok differently). — Reply to this email directly, view it on GitHub <#305 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AA4TUI74N3XSG32ZBGO66VDXYX5WPANCNFSM6AAAAAA2M3T22Q> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[gilvillard]

Hi Dave,
Yes, that's correct I think.
Cheers