# Minimal polynomial isn't minimal?

Quoting MathWorld,

The minimal polynomial of a matrix $A$ is the monic polynomial in $A$ of smallest degree $n$ such that

$$p(A) = \sum_{i=0}^n c_i A^i = 0$$.

I'd like to find the minimal polynomial of a matrix $A$ over the reals. My attempt:

sage: A = matrix(RR, [
....:     [0,-9, 0, 0, 0, 0],
....:     [1, 6, 0, 0, 0, 0],
....:     [0, 0, 0,-9, 0, 0],
....:     [0, 0, 1, 6, 0, 0],
....:     [0, 0, 0, 0, 0,-5],
....:     [0, 0, 0, 0, 1, 0]
....: ])
sage: f = A.minpoly()
sage: f.is_monic()
True
sage: f(A).is_zero()
True


However, $f$ doesn't appear to actually be the minimal polynomial:

sage: R.<x> = RR['x']
sage: g = x^4 - 6*x^3 + 14*x^2 - 30*x + 45
sage: g(x).is_monic()
True
sage: g(A).is_zero()
True
sage: g.degree() < f.degree()
True


Did I make a mistake or is this a bug?

I noticed that A.minpoly() gives $g$ if I do the computation over $\mathbb{Q}$ instead of $\mathbb{R}$. Perhaps the minpoly function just needs to be restricted to exact rings?

edit retag close merge delete

Sort by » oldest newest most voted

You are right, it is a bug. Thanks for reporting.

If we explore the source code of the .minpoly() method (by typing A.minpoly??), we can see that the problem is twofold:

in the test of squarefreeness of f:

sage: f = A.charpoly()
sage: f
x^6 - 12.0000000000000*x^5 + 59.0000000000000*x^4 - 168.000000000000*x^3 + 351.000000000000*x^2 - 540.000000000000*x + 405.000000000000
sage: f.is_squarefree()
True


and (if we skip this shortcut) in the computation of f.radical().

sage: f = A.charpoly()
sage: f
x^6 - 12.0000000000000*x^5 + 59.0000000000000*x^4 - 168.000000000000*x^3 + 351.000000000000*x^2 - 540.000000000000*x + 405.000000000000
x^6 - 12.0000000000000*x^5 + 59.0000000000000*x^4 - 168.000000000000*x^3 + 351.000000000000*x^2 - 540.000000000000*x + 405.000000000000


Indeed:

sage: f.factor()
(x - 3.00000000000000)^4 * (x^2 + 5.00000000000000)
(x - 3.00000000000000) * (x^2 + 5.00000000000000)


Inspecting further, we can see that the bug in the computation of f.radical() is in the computation of the gcd between f and its derivative:

sage: f.gcd(f.derivative())
1.00000000000000
sage: f.derivative()
6.00000000000000*x^5 - 60.0000000000000*x^4 + 236.000000000000*x^3 - 504.000000000000*x^2 + 702.000000000000*x - 540.000000000000
sage: f.derivative().factor()
(6.00000000000000) * (x - 3.00000000000000)^3 * (x^2 - x + 3.33333333333333)


Which is told in the documentation of the .gcd() method : "Unless the division is exact (i.e. no rounding occurs) the returned gcd is almost certain to be 1".

There are various possibities to fix this:

• In the .minpoly() method, we can start with mp = f.parent().one_element() instead of mp = f.radical(), replace mp *= h**(n-1) by mp *= h**(n-1) and add mp *= h if e == 1.

• In the .radical() method, use factorization instead of gcd (if one can guarantee that this will lead to less errors).

• In the .gdc() method, use factorization instead of Euclid algorithm (if one can guarantee that this will lead to less errors). The problem is that factorization is much slower.

more