Ask Your Question
5

Minimal polynomial isn't minimal?

asked 2014-08-24 13:13:39 -0500

Wilson gravatar image

updated 2014-08-24 14:22:48 -0500

tmonteil gravatar image

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 flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
4

answered 2014-08-24 14:20:23 -0500

tmonteil gravatar image

updated 2014-08-24 17:25:38 -0500

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 more

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2014-08-24 13:13:39 -0500

Seen: 373 times

Last updated: Aug 24 '14