Added image and kernel methods to morphisms of finite-dimensional modules with basis

[tscrim]

It is useful to have these, and we can do these at the category level.

CC: @sagetrac-sage-combinat @nthiery @darijgr @avirmaux @simon-king-jena

Component: linear algebra

Keywords: kernel, image, module morphism

Author: Travis Scrimshaw

Branch/Commit: 13d988b

Reviewer: Darij Grinberg

Issue created by migration from https://trac.sagemath.org/ticket/19609

[tscrim]

New commits:

55a5aac

Added image and kernel to finite-dimensional modules with basis.

[tscrim]

Commit: 55a5aac

[tscrim]

Branch: public/categories/image_kernel_module_morphism-19609

[bc9eee3a-171b-423e-8ec5-1c11eaa42e98]

comment:2

It is definitely very usefull! Just a few (maybe useless) remarks. The basis method usually returns a Family (Finite, Lazy or ...), may we want to do the same for the kernel instead of a tuple? Also, we may want to document the choice of right kernel versus left kernel.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

0010ab5

Better `__eq__` tests for module morphisms and removing cached_method.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 55a5aac to 0010ab5

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0010ab5 to 289d8c2

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

c13fbd2	Fixing an __eq__.
289d8c2	Making the output of cached methods immutable.

[tscrim]

comment:5

Replying to @avirmaux:

It is definitely very usefull! Just a few (maybe useless) remarks. The basis method usually returns a Family (Finite, Lazy or ...), may we want to do the same for the kernel instead of a tuple?

All of the other *_basis (like radical_basis) returned lists. I changed these to tuples because the output is cached (so should be immutable) and for consistency.

There was also an issue that I could not use cached methods on the morphisms because the equality test used __dict__. However, I decided to not make the results cached because if the basis order changed, then one can get different bases for the kernel/image, which may be desirable.

Also, we may want to document the choice of right kernel versus left kernel.

I think there is only the right kernel because I chose to use the right matrix version and there is no ambiguity. Perhaps I'm not thinking of something...

[bc9eee3a-171b-423e-8ec5-1c11eaa42e98]

comment:6

Replying to @tscrim:

I think there is only the right kernel because I chose to use the right matrix version and there is no ambiguity. Perhaps I'm not thinking of something...

Maybe saying it in the documentation; I often check the code to know whether it is done on the right or left :P

[tscrim]

comment:7

Replying to @avirmaux:

Replying to @tscrim:

I think there is only the right kernel because I chose to use the right matrix version and there is no ambiguity. Perhaps I'm not thinking of something...

Maybe saying it in the documentation; I often check the code to know whether it is done on the right or left :P

I guess that wasn't very clear. What I meant to say is that there is no right vs left because, obstinately, there is no matrix and the kernel is well defined in terms of the morphism. Also, for matrices, the left version would be the kernel of the dual map (under the convention that vector spaces are represented by column vectors). So I'm not sure what you would want me to say in the doc.

[bc9eee3a-171b-423e-8ec5-1c11eaa42e98]

comment:8

Indeed, forget what I said before then, I don't see any problem anymore.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 289d8c2 to 1f010ec

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

85cb356	Merge branch 'public/categories/image_kernel_module_morphism-19609' of git://trac.sagemath.org/sage into ker
8519f19	annihilator_basis already returns a tuple, right?
61425ee	trivial doc fixes
6939c5d	fix subtle glitch in orthogonal idempotent checking (repeated entries) and document it
10dbbce	doc fixes in matrix2.pyx
6ee1d41	change kernel_basis
1f010ec	document echelon form requirements, since these are relied upon

[darijgr]

comment:10

Travis, could you explain your __eq__ methods? Are they intended to fix some issues where e.g. module morphisms were claimed to be equal because they matched on algebra generators?

(I've reviewed the other edits, although arguably the __eq__ ones are the main part of the branch.)

[tscrim]

comment:11

Replying to @darijgr:

Travis, could you explain your __eq__ methods? Are they intended to fix some issues where e.g. module morphisms were claimed to be equal because they matched on algebra generators?

I expanded out the __dict__ comparison. I had at one point used a @cached_method for the kernel basis, which adds stuff to the __dict__ and causes problems because of this. (However, because this might depend on the basis order, I decided to make it non-cached.)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1f010ec to fd8d546

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

fd8d546

more doctests

[darijgr]

comment:13

Hmm, I'm not sure I'm happy with this -- but once again, this seems to be a Sage design flaw, not an error of your branch. Now that we are overriding __eq__, everyone implementing a new class of module morphism will have to override __eq__ as well or risk distinct morphisms comparing as equal. Maybe we should also compare on_basis() and _inverse on triangular module morphisms?

Nicolas, Simon, or whoever else understands these matters: any chance you could look over the __eq__ definitions?

The rest of the code LGTMs to me.

[tscrim]

comment:14

Replying to @darijgr:

Hmm, I'm not sure I'm happy with this -- but once again, this seems to be a Sage design flaw, not an error of your branch. Now that we are overriding __eq__, everyone implementing a new class of module morphism will have to override __eq__ as well or risk distinct morphisms comparing as equal.

That is how you should write code in good OOP, inherit and use the parent class methods and override if necessary. I certainly understand why comparing the __dict__ was done and it was a good solution at the time.

Maybe we should also compare on_basis() and _inverse on triangular module morphisms?

_inverse is completely dependent on the other attributes, so I think that is a wasted test. However, the current inheritance scheme does not explicitly have an on_basis in TriangularModuleMorphism. Strictly speaking, I'm not opposed to doing this, but by the current class hierarchy, it would get double-checked because TriangularModuleMorphism is an ABC and the actual concrete implementations will end up checking that. So on that, I would say your test:

TriangularModuleMorphism.__eq__(phi, phi2) # I don't like this :/

is misleading. It is the correct result because as far as that class is concerned, they are equal (in fact, IMO the call to on_basis in the __init__ should be moved into the if inverse_on_support == "compute": block since that is the only place it is used).

Actually, it might be better to remove the inheritance from ModuleMorphism and have TriangularModuleMorphism as a mixin class. However all of this should be on a separate ticket. I can also split the __eq__ part off to said ticket as it is not needed for the features I was originally after.

Nicolas, Simon, or whoever else understands these matters: any chance you could look over the __eq__ definitions?

I would appreciate your (Nicolas and/or Simon) comments on these classes and what you think we should do moving forward. On a somewhat related question, do you think we should spend time to Cythonize these classes?

[darijgr]

comment:15

Oops, I forgot to CC Simon!

I am OK with splitting this ticket into two -- if your __eq__ changes are not necessary for the image and kernel, then there isn't much reason for them to be together. I can't really make a judgment call on the __eq__, so this issue will keep me from finishing the review for as long as the ticket stays joined; but if Nicolas, Simon or someone else from the OOP department steps in to finish the review, that won't be an issue.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

13d988b

Reverting `__eq__` changes for triangular module morphisms.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from fd8d546 to 13d988b

[tscrim]

comment:18

I've split off the __eq__ to #19820. So can I take comment:15 as a positive review?

[darijgr]

comment:19

Yes!

[darijgr]

comment:20

(Provided that my code LGTYs.)

[vbraun]

comment:21

Reviewer name missing

[darijgr]

comment:22

OK, Travis, can you add our both names if you agree to my changes?

[tscrim]

Reviewer: Darij Grinberg

[tscrim]

comment:23

Did you push changes to this part of the ticket? The only commit I saw was to the doctests of the __eq__.

[darijgr]

comment:24

I did, though only a few lines of code were changed (see https://github.com/sagemath/sagetrac-mirror/compare/036455fd4defbb003152bf283af3a629b9c49324...13d988bc57a5bc7f4ea7cb1edc64db6dc1c8cdb2 ).

[tscrim]

comment:25

Ah right. :P Thanks! Then back to positive review.

[vbraun]

Changed branch from public/categories/image_kernel_module_morphism-19609 to 13d988b