Bug in charpoly over discrete valuation rings

[xcaruso]

There is a bug in the computation of the characteristic polynomial over a discrete valuation ring.

sage: R.<t> = GF(5)[[]]
sage: M = matrix(3, 3, [1, t + O(t^3), t^2,
....:                   1 + t + O(t^3), 2 + t^2, 3 + 2*t + O(t^3),
....:                   t - t^2, 2*t, 1 + t])
sage: M.charpoly()
Traceback (most recent call last):
...
TypeError: 'PlusInfinity' object cannot be interpreted as an integer
Hessenberg form only possible for matrices over a field

Expected:

sage: M.charpoly()
x^3 + (1 + 4*t + 4*t^2 + O(t^3))*x^2 + (t + 2*t^2 + O(t^3))*x + 3 + 2*t^2 + O(t^3)

This ticket fixes that.

CC: @sagetrac-rpages @slel

Component: linear algebra

Keywords: characteristic polynomial, charpoly

Author: Xavier Caruso

Branch/Commit: 41b3880

Reviewer: Samuel Lelièvre

Issue created by migration from https://trac.sagemath.org/ticket/31753

[xcaruso]

Branch: u/caruso/charpoly

[xcaruso]

Commit: de32db6

[sagetrac-git]

Changed commit from de32db6 to ca3285a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ca3285a

handle case where precision_relative is infinite

[xcaruso]

Author: Xavier Caruso

[slel]

Reviewer: Samuel Lelièvre, ...

[slel]

comment:5

a.

The patchbot reports an incorrect Trac link. To fix it:

-    We check that trac:`31753` is resolved::
+    We check that :trac:`31753` is resolved::

b.

Your fix for the bug seems to consist in removing m from a cdef declaration.

Can you explain why that caused a problem, and why this is a good solution?

But probably someone who knows more Cython than me should review that part.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e43030c

missing colon

[sagetrac-git]

Changed commit from ca3285a to e43030c

[xcaruso]

comment:7

Replying to @slel:

Your fix for the bug seems to consist in removing m from a cdef declaration.
Can you explain why that caused a problem, and why this is a good solution?

It's just because precision_relative can return +Infinity which cannot be cast to an integer (in fact an element of type Py_ssize_t). Removing the declaration, we let python handle this.

[slel]

comment:9

Right, m can be infinity. That's why maxi is also
left out of the cdef. Is there a cdef type for
Python or Sage objects that could be used?
Perhaps not crucial, as the inner loop matters most.

Still, about cdef lines, maybe remove the one about c
and add entry to the RingElement one?

-    cdef Matrix_generic_dense c
-    cdef RingElement pivot, inv, scalar
+    cdef RingElement entry, pivot, inv, scalar

Commit 28a35a97
from #30892 added the cdef ... c line while removing the use of c.

[xcaruso]

comment:10

Replying to @slel:

-    cdef Matrix_generic_dense c
-    cdef RingElement pivot, inv, scalar
+    cdef RingElement entry, pivot, inv, scalar

Good point!

[sagetrac-git]

Changed commit from e43030c to 41b3880

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

41b3880

better cdef

[slel]

comment:12

Since this fixes a bug, maybe it can still go in Sage 9.3.

[slel]

Changed reviewer from Samuel Lelièvre, ... to Samuel Lelièvre

[slel]

Changed keywords from characteristic polynomial to characteristic polynomial, charpoly

[fchapoton]

comment:14

milestone to 9.4, as 9.3 has been released

[vbraun]

Changed branch from u/caruso/charpoly to 41b3880