Opened 10 years ago

Closed 9 years ago

#14117 closed defect (fixed)

Jordan normal form not computed for nilpotent matrix over rational function field / polynomials cannot be factored over rational function field

Reported by: Darij Grinberg Owned by: Alex Ghitza
Priority: major Milestone: sage-5.13
Component: algebra Keywords: polynomials, factorization, jordan normal form
Cc: Igor Tolkov, Sage Combinat CC user Merged in: sage-5.13.beta0
Authors: Darij Grinberg Reviewers: Luis Felipe Tabera Alonso, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Darij Grinberg)

The manual for the jordan_form method on a matrix explicitly claims that the Jordan form is computed over arbitrary fields as long as the characteristic polynomial splits over there. This should particularly imply that the Jordan normal form of a nilpotent matrix is always computed. Unfortunately, this is not so:

sage: Qx = PolynomialRing(QQ, 'x11, x12, x13, x21, x22, x23, x31, x32, x33')
sage: x11, x12, x13, x21, x22, x23, x31, x32, x33 = Qx.gens()
sage: M = matrix(Qx, [[0, 0, x31], [0, 0, x21], [0, 0, 0]])
sage: M**3
[0 0 0]
[0 0 0]
[0 0 0]
sage: N = M.base_extend(Qx.fraction_field())
sage: N
[  0   0 x31]
[  0   0 x21]
[  0   0   0]
sage: N.base_ring() 
Fraction Field of Multivariate Polynomial Ring in x11, x12, x13, x21, x22, x23, x31, x32, x33 over Rational Field
sage: N.jordan_form()
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)

/home/darij/sage-5.6/<ipython console> in <module>()

/home/darij/sage-5.6/local/lib/python2.7/site-packages/sage/matrix/matrix2.so in sage.matrix.matrix2.Matrix.jordan_form (sage/matrix/matrix2.c:43627)()

/home/darij/sage-5.6/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_element.so in sage.rings.polynomial.polynomial_element.Polynomial.roots (sage/rings/polynomial/polynomial_element.c:35063)()

NotImplementedError: root finding for this polynomial not implemented

This seems to boil down to polynomial factorization over function fields not being implemented:

sage: N.characteristic_polynomial().factor()
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)

/home/darij/sage-5.6/<ipython console> in <module>()

/home/darij/sage-5.6/local/lib/python2.7/site-packages/sage/rings/polynomial/polynomial_element.so in sage.rings.polynomial.polynomial_element.Polynomial.factor (sage/rings/polynomial/polynomial_element.c:24161)()

NotImplementedError: 

Maybe a workaround is adding a new key "nilpotent" to the jordan_form method which, when set to True, skips the factorization of the characteristic polynomial and lets sage know that the matrix is nilpotent? In my personal experience, nilpotent matrices are the ones with the most interesting Jordan forms, and skipping the useless factorization would probably save quite some CPU cycles for them.

Update: Here's a noobish patch, which adds an optional parameter to the jordan_form method allowing pre-computed factorizations of the characteristic polynomial. What do you guys think about it?

(This doesn't mean that we don't need a polynomial factorization algorithm for multivariate polynomial rings over QQ; but I guess that's for a different patch. We might want to do Jordan forms of, say, nilpotent matrices over fields where factorization isn't even theoretically possible.)

Update 3: Better version.

Attachments (5)

trac_14117-jordan_normal_form-v1.py (3.4 KB) - added by Darij Grinberg 10 years ago.
slightly improved
trac_14117-jordan_normal_form-v2.py (4.6 KB) - added by Darij Grinberg 10 years ago.
version 2
trac_14117-jordan_normal_form-dg-v3.patch (6.3 KB) - added by Darij Grinberg 9 years ago.
version 3
trac_14117-jordan_normal_form-dg-v4.patch (6.4 KB) - added by Darij Grinberg 9 years ago.
reviewed version
trac_14117-jordan_normal_form-dg-v4.2.patch (6.4 KB) - added by Darij Grinberg 9 years ago.
reviewed version

Download all attachments as: .zip

Change History (22)

comment:1 Changed 10 years ago by Darij Grinberg

Authors: Darij Grinberg
Cc: Igor Tolkov Sage Combinat CC user added
Description: modified (diff)
Status: newneeds_review

comment:2 Changed 10 years ago by Darij Grinberg

Description: modified (diff)

comment:3 Changed 10 years ago by Darij Grinberg

Description: modified (diff)

Changed 10 years ago by Darij Grinberg

slightly improved

comment:4 Changed 10 years ago by Igor Tolkov

Thanks for the CC. I'm somewhat new here, anything I should do?

comment:5 Changed 10 years ago by Darij Grinberg

Hi -- I cc'ed you since I saw you working on the Jordan normal form today, so I'm wondering if you can provide some comments, maybe even a review...

comment:6 Changed 10 years ago by Luis Felipe Tabera Alonso

Reviewers: Luis Felipe Tabera Alonso
Status: needs_reviewneeds_work

With your example

sage: M.jordan_form(eigenvalues=[(0,3)])
[0 1|0]
[0 0|0]
[---+-]
[0 0|0]
sage: M.jordan_form(eigenvalues=[(1,3)])
[]

The code should not return the second but raise a type of error. Also, add to the doctest a test with your eigenvalues option with transformation=True to make sure it works as expected.

As a matter of style, avoid blank lines containing only blanckspaces (up to the indent level) in your code. I think this is not enforced though.

comment:7 Changed 10 years ago by Darij Grinberg

Good point about the error raising! I'll do it later today, when I have time. I am going to add a check variable that defaults to True so that the checking is only done when it is True, though; otherwise the speed advantage of this might be significantly diminished. (Checking is best done by just comparing the characteristic polynomial to the product of (X-eigenvalue)(multiplicity) , or is there a better way?)

I didn't know that blank lines should not be indented! This makes my life easier, since I actually thought they *should* be indented...

Last edited 10 years ago by Darij Grinberg (previous) (diff)

comment:8 Changed 10 years ago by Darij Grinberg

Description: modified (diff)
Status: needs_workneeds_review

Changed 10 years ago by Darij Grinberg

version 2

comment:9 Changed 9 years ago by Darij Grinberg

Oooops, I've just noticed that I gave the patch the extension .py rather than .patch. Anyway, here comes a new version, with a few typos fixed.

Changed 9 years ago by Darij Grinberg

version 3

comment:10 Changed 9 years ago by Darij Grinberg

Description: modified (diff)

comment:11 Changed 9 years ago by Darij Grinberg

patchbot:

apply trac_14117-jordan_normal_form-dg-v3.patch

comment:12 Changed 9 years ago by Darij Grinberg

Any idea why one of the patchbot machines reports PluginFailed??

comment:13 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:14 Changed 9 years ago by Travis Scrimshaw

Reviewers: Luis Felipe Tabera AlonsoLuis Felipe Tabera Alonso, Travis Scrimshaw

One very minor point, instead of Polyring(1), it's better to use Polyring.one() to take advantage of caching. Once you've made this change, you can set this to positive review on my behalf.

Best,
Travis

Changed 9 years ago by Darij Grinberg

reviewed version

Changed 9 years ago by Darij Grinberg

reviewed version

comment:15 Changed 9 years ago by Darij Grinberg

Thank you!

For the patchbot:

apply trac_14117-jordan_normal_form-dg-v4.patch

comment:16 Changed 9 years ago by Darij Grinberg

Description: modified (diff)
Status: needs_reviewpositive_review

comment:17 Changed 9 years ago by Jeroen Demeyer

Merged in: sage-5.13.beta0
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.