Opened 8 years ago

Closed 7 years ago

#12693 closed defect (fixed)

bug in jordan_form(transformation=true) for integer matrices

Reported by: hthomas Owned by: jason, was
Priority: major Milestone: sage-5.1
Component: linear algebra Keywords: jordan form, sd40.5
Cc: Merged in: sage-5.1.beta5
Authors: Douglas McNeil Reviewers: Rob Beezer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by rbeezer)

sage: M=matrix(((2,2,2),(0,0,0),(-2,-2,-2)))
sage: M.jordan_form(transformation=true) 
(
[0 1|0]            
[0 0|0]  [ 2  1  1]
[---+-]  [ 0  0  0]
[0 0|0], [-2  0 -1]
)

If the output from M.jordan_form(transformation=true) is J,P, then we are supposed to have J=P-1 M P. The output here is obviously wrong, since P is not invertible (having a zero row).

If you change the 2's to 1's and the -2's to -1's it works properly.

This behaviour exists in 4.8 and 5.0beta5.

Apply:

  1. trac_12693_fix_jordan_form_bug.3.patch
  2. trac_12693_fix_jordan_form_reviewer.patch

Attachments (4)

trac_12693_fix_jordan_form_bug.patch (4.0 KB) - added by dsm 8 years ago.
push ring to the field
trac_12693_fix_jordan_form_bug.2.patch (3.5 KB) - added by dsm 8 years ago.
push ring to the field
trac_12693_fix_jordan_form_bug.3.patch (3.5 KB) - added by dsm 8 years ago.
push ring to the field
trac_12693_fix_jordan_form_reviewer.patch (1.4 KB) - added by rbeezer 8 years ago.
Reviewer patch

Download all attachments as: .zip

Change History (17)

comment:1 Changed 8 years ago by dsm

Looks like a simple type error somewhere. Fails for integers, works for rationals:

sage: M
[ 2  2  2]
[ 0  0  0]
[-2 -2 -2]
sage: parent(M)
Full MatrixSpace of 3 by 3 dense matrices over Integer Ring
sage: M.jordan_form(transformation=True)
(
[0 1|0]            
[0 0|0]  [ 2  1  1]
[---+-]  [ 0  0  0]
[0 0|0], [-2  0 -1]
)

but

sage: (M/1).jordan_form(transformation=True)
(
[0 1|0]            
[0 0|0]  [ 2  1  0]
[---+-]  [ 0  0  1]
[0 0|0], [-2  0 -1]
)
sage: parent(M/1)
Full MatrixSpace of 3 by 3 dense matrices over Rational Field
sage: (M/1).jordan_form(transformation=True)
(
[0 1|0]            
[0 0|0]  [ 2  1  0]
[---+-]  [ 0  0  1]
[0 0|0], [-2  0 -1]
)
sage: J, P = (M/1).jordan_form(transformation=True)
sage: J == P**(-1)*M*P
True

Will see if I can track it down.

comment:2 Changed 8 years ago by hthomas

Thanks! And thanks for the quick-and-dirty fix, which will mean I can finish the calculation I was working on!

comment:3 Changed 8 years ago by dsm

I can see what's going on, but I'm not sure what the best way to deal with it is. For my part I'd probably simply push everything to the fraction field during the base_ring changes of jordan_form() in matrix2.pyx and work with vector spaces over the field instead of free modules over the ring, but not everyone might like that.

Comparing the differences between the code paths for ZZ and QQ, the first divergence seems to come in _jordan_form_vector_in_difference. Both cases get V= [(1, 0, -1), (0, 1, -1)] and W = [(2, 0, -2), (1, 0, 0)], but in the integer case the resulting W_space is

W_space: Free module of degree 3 and rank 2 over Integer Ring
Echelon basis matrix:
[1 0 0]
[0 0 2]

i.e. a FreeModule_submodule_pid_with_category (not a FreeModule_submodule_field_with_category, as it would be in QQ) at which point Sage decides (reasonably enough) that (1, 0, -1) isn't in W_space. For comparison, the QQ case gives

W_space: Vector space of degree 3 and dimension 2 over Rational Field
Basis matrix:
[1 0 0]
[0 0 1]

and it returns (0, 1, -1) instead.

Good news is that whatever we decide to do should be straightforward.

comment:4 Changed 8 years ago by hthomas

Working over QQ (or, in general, over the fraction field) seems fine to me. Basically, though, I am not knowledgeable enough to have an opinion.

comment:5 Changed 8 years ago by was

  • Stopgaps set to todo

comment:6 Changed 8 years ago by rbeezer

  • Keywords sd40.5 added

I cannot see how this routine should be guaranteed to succeed over a ring that is not a field. And eventually we need to factor the characteristic polynomial over the ring anyway.

So I see no harm into moving to the fraction field now and if there is a way to do this over a ring, another patch can attempt that.

Rob

comment:7 Changed 8 years ago by dsm

Okay, here's a draft. It passes matrix/* doctests but I haven't yet run the full test suite.

Changed 8 years ago by dsm

push ring to the field

Changed 8 years ago by dsm

push ring to the field

Changed 8 years ago by dsm

push ring to the field

comment:8 Changed 8 years ago by rbeezer

Looking good. I'll be more thorough in the morning.

Changed 8 years ago by rbeezer

Reviewer patch

comment:9 Changed 8 years ago by rbeezer

  • Authors set to Douglas McNeil
  • Description modified (diff)
  • Reviewers set to Rob Beezer
  • Status changed from new to needs_review

comment:10 Changed 8 years ago by rbeezer

Version 3 patch has a positive review from me, my reviewer patch will need a look (from Doug?).

comment:11 Changed 8 years ago by dsm

Okay, the reviewer patch looks good to me.

comment:12 Changed 8 years ago by rbeezer

  • Status changed from needs_review to positive_review

comment:13 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.1.beta5
  • Resolution set to fixed
  • Status changed from positive_review to closed
  • Stopgaps todo deleted
Note: See TracTickets for help on using tickets.