Opened 9 years ago
Closed 8 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 )
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:
Attachments (4)
Change History (17)
comment:1 Changed 9 years ago by
comment:2 Changed 9 years ago by
Thanks! And thanks for the quick-and-dirty fix, which will mean I can finish the calculation I was working on!
comment:3 Changed 9 years ago by
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 9 years ago by
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 9 years ago by
- Stopgaps set to todo
comment:6 Changed 9 years ago by
- 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 9 years ago by
Okay, here's a draft. It passes matrix/* doctests but I haven't yet run the full test suite.
comment:8 Changed 9 years ago by
Looking good. I'll be more thorough in the morning.
comment:9 Changed 9 years ago by
- Description modified (diff)
- Reviewers set to Rob Beezer
- Status changed from new to needs_review
comment:10 Changed 9 years ago by
Version 3 patch has a positive review from me, my reviewer patch will need a look (from Doug?).
comment:11 Changed 9 years ago by
Okay, the reviewer patch looks good to me.
comment:12 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:13 Changed 8 years ago by
- Merged in set to sage-5.1.beta5
- Resolution set to fixed
- Status changed from positive_review to closed
- Stopgaps todo deleted
Looks like a simple type error somewhere. Fails for integers, works for rationals:
but
Will see if I can track it down.