Opened 9 years ago

Closed 9 years ago

#6942 closed defect (fixed)

jordan_form with transformation=true returns non-invertible transformation

Reported by: syazdani Owned by: tbd
Priority: critical Milestone: sage-4.3.3
Component: linear algebra Keywords: jordan_form, transformation
Cc: jason Merged in: sage-4.3.3.alpha0
Authors: Sebastian Pancratz Reviewers: Rob Beezer, Minh Van Nguyen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

The following code returns an incorrect result:

mm=Matrix(GF(2),[[1,0,1,0,0,0,1],[1,0,0,1,1,1,0],[1,1,0,1,1,1,1],[1,1,1,0,1,1,1],[1,1,1,0,0,1,0],[1,1,1,0,1,0,0],[1,1,1,1,1,1,0]])
_,S = mm.jordan_form(transformation=True)
S.rank()

S should be invertible, so the rank should be 7, but the rank of the above is 5.

Attachments (3)

trac6942_jordan.patch (16.4 KB) - added by spancratz 9 years ago.
trac6942_jordan_tests.patch (8.7 KB) - added by spancratz 9 years ago.
Additional doctests
trac_6942-reviewer.patch (774 bytes) - added by rbeezer 9 years ago.
One-character reviewer doctest fix

Download all attachments as: .zip

Change History (16)

comment:1 Changed 9 years ago by jason

  • Cc jason added

comment:2 Changed 9 years ago by AlexGhitza

  • Component changed from algebra to linear algebra
  • Milestone set to sage-4.3

comment:3 Changed 9 years ago by jason

  • Report Upstream set to N/A

According to Magma:

u,v:=JordanForm(Matrix(GF(2),7,7,StringToIntegerSequence("1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 0")));

print "jordan form:";
u;
print "transformation";
v;

gives

Magma V2.15-14    Tue Nov 24 2009 10:36:58    [Seed = 4156006409]
   -------------------------------------

jordan form:
[1 0 0 0 0 0 0]
[0 1 1 0 0 0 0]
[0 0 1 0 0 0 0]
[0 0 0 1 1 0 0]
[0 0 0 0 1 0 0]
[0 0 0 0 0 1 1]
[0 0 0 0 0 0 1]
transformation
[0 0 0 0 1 1 0]
[0 0 0 0 0 0 1]
[1 1 1 1 1 1 1]
[0 0 0 0 0 1 0]
[1 1 1 0 1 1 0]
[1 0 1 0 0 0 0]
[1 1 0 1 1 1 0]

Total time: 0.180 seconds, Total memory usage: 7.27MB

comment:4 Changed 9 years ago by jason

Or more verbosely:

m:=Matrix(GF(2),7,7,StringToIntegerSequence("1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 0"));
jor,trans:=JordanForm(m);

print "jordan form:";
jor;
print "transformation";
trans;
print "m*transformation";
trans*m;
print "transformation*jordan form";
jor*trans; 

gives

Magma V2.15-14    Tue Nov 24 2009 10:41:01    [Seed = 3482294566]
   -------------------------------------

jordan form:
[1 0 0 0 0 0 0]
[0 1 1 0 0 0 0]
[0 0 1 0 0 0 0]
[0 0 0 1 1 0 0]
[0 0 0 0 1 0 0]
[0 0 0 0 0 1 1]
[0 0 0 0 0 0 1]
transformation
[0 0 0 0 1 1 0]
[0 0 0 0 0 0 1]
[1 1 1 1 1 1 1]
[0 0 0 0 0 1 0]
[1 1 1 0 1 1 0]
[1 0 1 0 0 0 0]
[1 1 0 1 1 1 0]
m*transformation
[0 0 0 0 1 1 0]
[1 1 1 1 1 1 0]
[1 1 1 1 1 1 1]
[1 1 1 0 1 0 0]
[1 1 1 0 1 1 0]
[0 1 1 1 1 1 0]
[1 1 0 1 1 1 0]
transformation*jordan form
[0 0 0 0 1 1 0]
[1 1 1 1 1 1 0]
[1 1 1 1 1 1 1]
[1 1 1 0 1 0 0]
[1 1 1 0 1 1 0]
[0 1 1 1 1 1 0]
[1 1 0 1 1 1 0]

Total time: 0.170 seconds, Total memory usage: 7.27MB

Changed 9 years ago by spancratz

comment:5 Changed 9 years ago by spancratz

  • Status changed from new to needs_review

The above patch fixes this problem, and also resolves ticket #6932.

Changed 9 years ago by spancratz

Additional doctests

comment:6 Changed 9 years ago by spancratz

The second patch adds additional doctests. There are three of them, all for 10 by 10 matrices over the rationals and with only one eigenvalue. The Jordan blocks are of sizes (a) 3,3,3,1, (b) 3,3,2,2, and (c) 3,2,2,2,1.

Sebastian

comment:7 Changed 9 years ago by rbeezer

This is looking pretty good. But I'll have to spend some more time with it. Until then, here's another 10x10 matrix with a nice Jordan form and nearly no fractions in the transformation matrix.

matrix(QQ, [
[-6,  9,  -7,  -5,  5,  12,  -22,  14,  8,  21 ],
[ -3,  5,  -3,  -1,  2,  7,  -12,  9,  1,  12 ],
[8,  -9,  8,  6,  0,  -14,  25,  -13,  -4,  -26 ],
[-7,  9,  -7,  -5,  0,  13,  -23,  13,  2,  24 ],
[0,  -1,  0,  -1,  -3,  -2,  3,  -4,  -2,  -3 ],
[3,  2,  1,  2,  9,  -1,  1,  5,  5,  -5 ],
[-1,  3,  -3,  -2,  4,  3,  -6,  4,  4,  3 ],
[3,  -4,  3,  2,  1,  -5,  9,  -5,  1,  -9 ],
[0,  2,  0,  0,  2,  2,  -4,  4,  2,  4 ],
[-4,  4,  -5,  -4,  -1,  6,  -11,  4,  1, 10]
])

Changed 9 years ago by rbeezer

One-character reviewer doctest fix

comment:8 Changed 9 years ago by rbeezer

  • Authors set to Sebastian Pancratz
  • Reviewers set to Rob Beezer
  • Status changed from needs_review to needs_info

Hi Sebastian,

Very nice!

  1. One line in a list indented one-too-many characters. Fix in reviewer patch for your convenience. Accept or not.
  1. Most of the linear algebra matrix decompositions return all the pieces, all the time. I've always thought it inconsistent Jordan form has this transformation switch, sometimes returning one matrix, other times two. Now would be a good time to change this behavior. But I see that the form is almost a combinatorial routine (once you have the spectrum), while the basis vectors require a whole lot more work, so maybe best not to compute it unless it is asked for?
  1. The list Vsmall+Y ends up in a span() in the "vector_in_difference" routine. The span has an already_echelonized switch, so I spent a lot of time trying to decide how (or if it was possible) to somehow "keep" Vsmall+Y echelonized, since Vsmall will start that way. Couldn't see a reasonable way to do anything too clever, though.
  1. Do you want the 10x10 matrix above for the doctests? I'd be happy to package it up with the one-character patch. ;-)

Other than the doctest fix, this is ready to go. If you want to accept the doctest fix, then go ahead and mark this as "positive review" - everything else is just for your consideration.

Great to see all your good work since the summer, including this.

Rob

comment:9 Changed 9 years ago by rbeezer

  • Status changed from needs_info to needs_review

I've marked this as "needs review" in hopes it will get merged soon. The questions above could be addressed on a new ticket.

comment:10 Changed 9 years ago by mvngu

  • Reviewers changed from Rob Beezer to Rob Beezer, Minh Van Nguyen
  • Status changed from needs_review to positive_review

The reviewer patch trac_6942-reviewer.patch looks good to me.

comment:11 follow-up: Changed 9 years ago by spancratz

Dear Rob,

I am sorry that I am only looking at this again now. Of course, the reviewer patch looks fine. Thanks again for reviewing this! About your other points...

3) Yes, that is a good observation. I am almost sure that if one looked closer at the linear algebra operations then this code could easily be improved. There are currently two reasons why I won't look at this, though. (a) The previous code was broken, so I think it's important to first have something that "obviously" works, in the sense that it is moderately easy to review since the code only uses "high-level" operations. (b) I've got my first year interview this coming Monday.

4) This is completely up to you. The matrix looks quite intriguing and more examples certainly couldn't hurt. Since this ticket will probably be closed soon, if you decide to include this new example, feel free to let me know (via email or sage-devel) and I'll review it right away.

Also, Minh, thank you for picking up the slack and completing the review process!

Kind regards,

Sebastian

comment:12 in reply to: ↑ 11 Changed 9 years ago by jason

Replying to spancratz:

Also, Minh, thank you for picking up the slack and completing the review process!

Minh and Rob---thank you both of you for reviewing this!

comment:13 Changed 9 years ago by mpatel

  • Merged in set to sage-4.3.3.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.