Minimal polynomial isn't minimal?

asked 2014-08-24 20:13:39 +0100

Wilson
53 ●2 ●2 ●5

updated 2023-01-09 23:59:34 +0100

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

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?

answered 2014-08-24 21:20:23 +0100

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

updated 2014-08-25 00:25:38 +0100

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
sage: f.radical()
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)
sage: f.factor().radical()
(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.

edit flag offensive delete link

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Minimal polynomial isn't minimal?

1 Answer

Your Answer

Question Tools

Stats

Related questions

Minimal polynomial isn't minimal? edit

1 Answer

Your Answer

Question Tools

Stats

Related questions

Minimal polynomial isn't minimal?