Opened 12 years ago

Closed 12 years ago

#8974 closed enhancement (fixed)

Added eigenvalues, eigenvector, eigenspaces and minpoly to vector space endomorphisms

Reported by: mmarco Owned by: jason, was
Priority: trivial Milestone: sage-4.5.2
Component: linear algebra Keywords: eigenvalues
Cc: Merged in: sage-4.5.2.alpha0
Authors: Miguel Marco Reviewers: David Loeffler
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Added the functions eigenvalues, eigenvectors, eigenspaces and minpoly to the FreeModuleMorphism? class (only for endomorphisms of vector spaces).

Attachments (5)

trac_8974_eigen_added.patch (6.4 KB) - added by mmarco 12 years ago.
trac_8974_eigen_added_2.patch (11.9 KB) - added by mmarco 12 years ago.
A Second patch with a new implementation (must be aplied after the previous one)
track_8974_added_eigenfunctions_module.patch (5.2 KB) - added by mmarco 12 years ago.
eigenvalues eigenvectors and minpoly functions for vectorspace endomorphims
track_8974_solved_nonimplemented_extfalse.patch (6.5 KB) - added by mmarco 12 years ago.
added the extend=False option for matrix eigenvalues and eigenvectors_left
trac_8974_reviewer.patch (6.6 KB) - added by davidloeffler 12 years ago.
apply over the two previous patches

Download all attachments as: .zip

Change History (18)

Changed 12 years ago by mmarco

comment:1 Changed 12 years ago by was

  • Status changed from new to needs_review

comment:2 Changed 12 years ago by davidloeffler

  • Status changed from needs_review to needs_work

Hmm. This is certainly functionality that we should have, but I don't agree with the implementation: I strongly feel that these linear-algebra methods should have *identical* behaviour for a matrix and for the corresponding morphism object. Your eigenvectors method takes an argument and returns the eigenvectors for that given eigenvalue, which isn't what the matrix one does. Similarly, eigenspaces for matrices makes a field extension if the eigenspaces aren't defined over the base field, while yours just returns the empty list.

Also, the underlying implementation should just call the existing one rather than doing the linear algebra anew. (E.g. for computing eigenvectors I think there are nasty cases with badly-conditioned matrices where just computing the kernel of X - lambda * identity blows up, and one can work around this using various devious tricks; it's not great if we have two different eigenvector methods and we have to fix them both separately.)

comment:3 Changed 12 years ago by mmarco

I agree that using the same methods for matrices and morphisms would be desiderable, but in my implementation i prefeared the mathematical correctedness. I mean, if a morphism is defined in a vector space over QQ, it doesn't make sense to say that its eigenvalues are numbers in a bigger field. Strictly speaking, they are not eigenvalues of this morphism (they are eigenvalues of a morphism defined in a bigger vector space, that can be defined in a natural way from this first morphism). If we include the functionality as a function of the vector space, i think it makes sense to be mathematically correct in this sense.

Maybe a better way to implement this would be to call the methods of the underlying matrix (avoiding thus the duplicity of code) and then select only the values that belong to the base field (keeping thus the mathematical correctedness).

comment:4 Changed 12 years ago by davidloeffler

I don't like the inconsistency. After all, matrices have base rings too, and your argument applies identically to the matrices rather than the endomorphism objects.

If you don't like the way it's currently implemented for matrices, you can start a debate on sage-devel if you want. It's perfectly possible that it could be changed, with an optional argument called something like "base_extend" to give users the option to choose whichever behaviour they want. But I absolutely insist that the behaviour should be the same for matrices and for morphisms of vector spaces represented by matrices.

David

comment:5 Changed 12 years ago by mmarco

Fine with me then. I will rewrite the functions makind them just call the methods asociated to the underlying matrices, and start the debate in sage-devel.

Just one question: would you agree to, for instance, convert the output of the eigenvectors function in an element of the vector space (instead of just the tuple that the matrix method returns)?

comment:6 Changed 12 years ago by davidloeffler

The matrix eigenvectors method returns vectors, not tuples. And so should the new one (but make sure it does the right thing in non-ambient vector spaces).

comment:7 Changed 12 years ago by mmarco

Hhmmm, the more i think about it, the less clear i see that it is a good idea to give results outside the base field (or vectorspace).

Does it really make sense to return as eigenvector some object that cannot be fed into the endomorphism procedure? That sounds like a very natural thing to do to check the correctedness of the result.

I think i will wait until the duscusion about these procedures in matrix objects to decide the best way to implement them, unless you think there is some rush.

Changed 12 years ago by mmarco

A Second patch with a new implementation (must be aplied after the previous one)

comment:8 Changed 12 years ago by mmarco

In view that the discusion about the change of the matrix functions is idle, i have implemented it.

So with this patch, the functions eigenvalues and eigenvectors can be called on matrices with the option extend=False (although i have noted that they are broken in matrices over the reals). I didn't change anything in the computation process; just parse the output to select the values in the base ring.

With that change, i have redone my implementation of these functions for homomorphism objects (an erased the eigenspaces functions, which i don't think make much sense to be translated directly from matrices such as it is). Now they just call the corresponding functions of the underlying matrices, and parse the output to convert the eigenvectors into elements of the corresponding vector space.

Changed 12 years ago by mmarco

eigenvalues eigenvectors and minpoly functions for vectorspace endomorphims

Changed 12 years ago by mmarco

added the extend=False option for matrix eigenvalues and eigenvectors_left

comment:9 Changed 12 years ago by mmarco

  • Status changed from needs_work to needs_review

Ok, this last two patches (track_8974_added_eigenfunctions_module.patch and track_8974_solved_nonimplemented_extfalse.patch) should do it. They contain respectively the new functions for endomorphisms, and the extend=False option for matrices (solving the nonimplemented error when it does not apply). They don't need any previous patches.

comment:10 Changed 12 years ago by davidloeffler

With your new patches, eigenvectors_left accepts the extend parameter but eigenvectors_right doesn't; and bases for free module morphism eigenspaces are returned as lists, while bases for matrix eigenspaces are returned as sequences. I've done a tiny patch that fixes these slight inconsistencies and tidies up the docstrings a bit. Marco: if you're happy with my changes please feel free to set this to "positive_review".

Changed 12 years ago by davidloeffler

apply over the two previous patches

comment:11 Changed 12 years ago by mmarco

  • Status changed from needs_review to positive_review

comment:12 Changed 12 years ago by davidloeffler

  • Reviewers set to David Loeffler

Apply track_8974_added_eigenfunctions_module.patch, track_8974_solved_nonimplemented_extfalse.patch and trac_8974_reviewer.patch.

comment:13 Changed 12 years ago by mpatel

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