Re: [Sage] #14117: Jordan normal form not computed for nilpotent matrix over rational function field / polynomials cannot be factored over rational function field
Sage
field / polynomials cannot be factored over rational function field
------------------------------------------------------------------+---------
Reporter: darij | Owner: AlexGhitza
Type: defect | Status: needs_review
Priority: major | Milestone: sage-5.10
Component: algebra | Resolution:
Keywords: polynomials, factorization, jordan normal form | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Darij Grinberg | Merged in:
Dependencies: | Stopgaps:
------------------------------------------------------------------+---------
Changes (by {'newvalue': u'Darij Grinberg', 'oldvalue': ''}):
* cc: itolkov, sage-combinat (added)
* status: new => needs_review
* author: => Darij Grinberg
Old description:
> 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:
> }}}
>
> Unfortunately, I have no idea how to debug, let alone fix, things in C
> code, so I have nothing positive to contribute on this issue. 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.
New description:
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:
}}}
Unfortunately, I have no idea how to debug, let alone fix, things in C
code, so I have nothing positive to contribute on this issue. 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.)
* Apply: [attachment:trac_14117-jordan_normal_form-v1.py]
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14117#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB
Sage
field / polynomials cannot be factored over rational function field
------------------------------------------------------------------+---------
Reporter: darij | Owner: AlexGhitza
Type: defect | Status: needs_review
Priority: major | Milestone: sage-5.10
Component: algebra | Resolution:
Keywords: polynomials, factorization, jordan normal form | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Darij Grinberg | Merged in:
Dependencies: | Stopgaps:
------------------------------------------------------------------+---------
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14117#comment:2>
Sage
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14117#comment:3>
Sage
field / polynomials cannot be factored over rational function field
------------------------------------------------------------------+---------
Reporter: darij | Owner: AlexGhitza
Type: defect | Status: needs_review
Priority: major | Milestone: sage-5.10
Component: algebra | Resolution:
Keywords: polynomials, factorization, jordan normal form | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Darij Grinberg | Merged in:
Dependencies: | Stopgaps:
------------------------------------------------------------------+---------
Comment (by itolkov):
Thanks for the CC. I'm somewhat new here, anything I should do?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14117#comment:4>
Sage
field / polynomials cannot be factored over rational function field
------------------------------------------------------------------+---------
Reporter: darij | Owner: AlexGhitza
Type: defect | Status: needs_review
Priority: major | Milestone: sage-5.10
Component: algebra | Resolution:
Keywords: polynomials, factorization, jordan normal form | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Darij Grinberg | Merged in:
Dependencies: | Stopgaps:
------------------------------------------------------------------+---------
Comment (by darij):
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...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14117#comment:5>
Sage
field / polynomials cannot be factored over rational function field
------------------------------------------------------------------+---------
Reporter: darij | Owner: AlexGhitza
Component: algebra | Resolution:
Keywords: polynomials, factorization, jordan normal form | Work issues:
Dependencies: | Stopgaps:
------------------------------------------------------------------+---------
* status: needs_review => needs_work
* reviewer: => Luis Felipe Tabera Alonso
Comment:
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14117#comment:6>
Sage
field / polynomials cannot be factored over rational function field
------------------------------------------------------------------+---------
Reporter: darij | Owner: AlexGhitza
Type: defect | Status: needs_work
Priority: major | Milestone: sage-5.10
Component: algebra | Resolution:
Keywords: polynomials, factorization, jordan normal form | Work issues:
Report Upstream: N/A | Reviewers: Luis Felipe Tabera Alonso
Authors: Darij Grinberg | Merged in:
Dependencies: | Stopgaps:
------------------------------------------------------------------+---------
Comment (by darij):
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...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14117#comment:7>
Sage
field / polynomials cannot be factored over rational function field
------------------------------------------------------------------+---------
Reporter: darij | Owner: AlexGhitza
Component: algebra | Resolution:
Keywords: polynomials, factorization, jordan normal form | Work issues:
Report Upstream: N/A | Reviewers: Luis Felipe Tabera Alonso
Authors: Darij Grinberg | Merged in:
Dependencies: | Stopgaps:
------------------------------------------------------------------+---------
* status: needs_work => needs_review
> EDIT: beginner mistake at hg fixed
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 2:''' Better version.
* Apply: [attachment:trac_14117-jordan_normal_form-v2.py]
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14117#comment:8>
Sage
field / polynomials cannot be factored over rational function field
------------------------------------------------------------------+---------
Reporter: darij | Owner: AlexGhitza
Type: defect | Status: needs_review
Keywords: polynomials, factorization, jordan normal form | Work issues:
Report Upstream: N/A | Reviewers: Luis Felipe Tabera Alonso
Authors: Darij Grinberg | Merged in:
Dependencies: | Stopgaps:
------------------------------------------------------------------+---------
Comment (by darij):
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14117#comment:9>
Sage
field / polynomials cannot be factored over rational function field
------------------------------------------------------------------+---------
Reporter: darij | Owner: AlexGhitza
Type: defect | Status: needs_review
Priority: major | Milestone: sage-5.11
Component: algebra | Resolution:
Keywords: polynomials, factorization, jordan normal form | Work issues:
Report Upstream: N/A | Reviewers: Luis Felipe Tabera Alonso
Authors: Darij Grinberg | Merged in:
Dependencies: | Stopgaps:
------------------------------------------------------------------+---------
* Apply: [attachment:trac_14117-jordan_normal_form-dg-v3.patch]
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14117#comment:10>
Sage
field / polynomials cannot be factored over rational function field
------------------------------------------------------------------+---------
Reporter: darij | Owner: AlexGhitza
Type: defect | Status: needs_review
Priority: major | Milestone: sage-5.11
Component: algebra | Resolution:
Keywords: polynomials, factorization, jordan normal form | Work issues:
Report Upstream: N/A | Reviewers: Luis Felipe Tabera Alonso
Authors: Darij Grinberg | Merged in:
Dependencies: | Stopgaps:
------------------------------------------------------------------+---------
Comment (by darij):
patchbot:
apply trac_14117-jordan_normal_form-dg-v3.patch
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14117#comment:11>