Basis-dependent isomorphism from FiniteRankFreeModule to an object in the category ModulesWithBasis

[mkoeppe]

(This ticket has been narrowed to the topic mainly discussed in the comments. The topic originally in title and ticket description has been moved to #30174)

There are multiple incompatible protocols for dealing with bases of a free module in Sage (#19346).

One such protocol is defined by the category ModulesWithBasis. CombinatorialFreeModule is one of the parent classes in this category.

Another such protocol is defined by the parent class FiniteRankFreeModule, which is in the category Modules.
A FiniteRankFreeModule can be equipped with a finite list of bases (each represented by an instance of FreeModuleBasis), none of which are considered distinguished. FiniteRankFreeModules are unique parents; the operation of equipping a FiniteRankFreeModule does not change the identity of the parent.

We define a method FiniteRankFreeModule. isomorphism_with_fixed_basis that establishes, given a basis, an isomorphism with a CombinatorialFreeModule (and thus a parent in the category ModulesWithBasis.

Depends on #30180

CC: @egourgoulhon @tscrim @mjungmath

Component: categories

Author: Matthias Koeppe, Michael Jung

Branch/Commit: 8a800cc

Reviewer: Michael Jung, Matthias Koeppe, Eric Gourgoulhon, Travis Scrimshaw

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

[mkoeppe]

comment:2

Also it seems various maps are missing.

sage: Q3.has_coerce_map_from(QQ^3)
False
sage: Q3((QQ^3).an_element())
ValueError: the None has not been defined on the 3-dimensional vector space over the Rational Field

[tscrim]

comment:4

These are incompatible objects since QQ^3 has a distinguished basis (the standard Euclidean basis) whereas Q3 does not. So there should not be a map between them.

My 2 cents for the error reported in the ticket is to first check that the object is not in the category. The other option is to lift the vector_space method up to the category of modules and then implement a change_ring method for Q3.

[mkoeppe]

comment:5

Replying to @tscrim:

These are incompatible objects since QQ^3 has a distinguished basis (the standard Euclidean basis) whereas Q3 does not. So there should not be a map between them.

Shouldn't there be a map in one direction that forgets the distinguished basis?

[tscrim]

comment:6

Replying to @mkoeppe:

Replying to @tscrim:

These are incompatible objects since QQ^3 has a distinguished basis (the standard Euclidean basis) whereas Q3 does not. So there should not be a map between them.

Shouldn't there be a map in one direction that forgets the distinguished basis?

No, because where would you send the point (1,3,1) to? How would you know how it is expressed in one of the bases of Q3?

[mkoeppe]

comment:7

Ok, I feel we had this discussion before

[mkoeppe]

comment:8

Should FreeModuleBasis get a method that creates the identity map from self.free_module() to a free module with that basis?

[mjungmath]

comment:9

Replying to @mkoeppe:

Should FreeModuleBasis get a method that creates the identity map from self.free_module() to a free module with that basis?

No, I don't think it should. The identity map (like any other automorphism) is a basis independent object.

[tscrim]

comment:10

Replying to @mjungmath:

Replying to @mkoeppe:

Should FreeModuleBasis get a method that creates the identity map from self.free_module() to a free module with that basis?

No, I don't think it should. The identity map (like any other automorphism) is a basis independent object.

I might even go further to say that it would not be the identity map, but an isomorphism of free modules. We have to be careful about distinguishing things up to equality and up to isomorphism. For example, if I have V = span_R{x,y,z}, this is not equal to W = R^3. So there is no identity map from V -> W because I am not looking at End(V), but Mor(V, W). Yes, they are isomorphic, but there is no canonical isomorphism until I choose a distinguished basis for V and W.

[mkoeppe]

comment:11

Replying to @tscrim:

Replying to @mjungmath:

Replying to @mkoeppe:

Should FreeModuleBasis get a method that creates the identity map from self.free_module() to a free module with that basis?

No, I don't think it should. The identity map (like any other automorphism) is a basis independent object.

I might even go further to say that it would not be the identity map, but an isomorphism of free modules.

Of course, that's what I meant.

[mkoeppe]

comment:12

Replying to @tscrim:

Replying to @mkoeppe:

Should FreeModuleBasis get a method that creates the identity map from self.free_module() to a free module with that basis?

We have to be careful about distinguishing things up to equality and up to isomorphism. For example, if I have V = span_R{x,y,z}, this is not equal to W = R^3.
... there is no canonical isomorphism until I choose a distinguished basis for V and W.

In my question above, this would be a method of FreeModuleBasis - so there is a particular basis. And RR^3 also has a distinguished basis.

[tscrim]

comment:13

Replying to @mkoeppe:

Replying to @tscrim:

Replying to @mkoeppe:

Should FreeModuleBasis get a method that creates the identity map from self.free_module() to a free module with that basis?

We have to be careful about distinguishing things up to equality and up to isomorphism. For example, if I have V = span_R{x,y,z}, this is not equal to W = R^3.
... there is no canonical isomorphism until I choose a distinguished basis for V and W.

In my question above, this would be a method of FreeModuleBasis - so there is a particular basis. And RR^3 also has a distinguished basis.

You were asking for a map from self.free_module(), which is the free module without a distinguished basis. If you want to go from a FreeModuleBasis, then that might be a good method as there is a canonical isomorphism of the homspace with the endspace and an identity map. Although I am not sure how much the basis is intended as a basis as a set or the span of the basis elements. I suspect the former, so such a method would not make sense. I would have to see what Eric and Michal say.

[egourgoulhon]

comment:14

Replying to @tscrim:

Replying to @mkoeppe:

Replying to @tscrim:

Replying to @mkoeppe:

Should FreeModuleBasis get a method that creates the identity map from self.free_module() to a free module with that basis?

We have to be careful about distinguishing things up to equality and up to isomorphism. For example, if I have V = span_R{x,y,z}, this is not equal to W = R^3.
... there is no canonical isomorphism until I choose a distinguished basis for V and W.

In my question above, this would be a method of FreeModuleBasis - so there is a particular basis. And RR^3 also has a distinguished basis.

You were asking for a map from self.free_module(), which is the free module without a distinguished basis. If you want to go from a FreeModuleBasis, then that might be a good method as there is a canonical isomorphism of the homspace with the endspace and an identity map. Although I am not sure how much the basis is intended as a basis as a set or the span of the basis elements. I suspect the former, so such a method would not make sense. I would have to see what Eric and Michal say.

I of course agree that one may implement a method in FreeModuleBasis that returns an isomorphism between Q3 and QQ^3, but for which purpose? Such an isomorphism cannot be used for a coercion since a coercion must be unique and cannot depend on a extra parameter such as a
basis-dependent isomorphism.

Coming back to the issue mentioned in the ticket title and description, I would say that the problem arises because "vector spaces" as they are implemented in Sage are not really vector spaces in all their generality but only Cartesian powers F^n, where F is the base field.

[mkoeppe]

comment:15

Replying to @egourgoulhon:

Coming back to the issue mentioned in the ticket title and description, I would say that the problem arises because "vector spaces" as they are implemented in Sage are not really vector spaces in all their generality but only Cartesian powers F^n, where F is the base field.

OK, I think we are getting closer.

When you say, '"vector spaces" as they are implemented in Sage', I assume you mean the ones implemented in sage.modules.free_module and constructed by the function VectorSpace, and then I agree with what you wrote.

What I was asking for in comment 8 is, given a basis, a map from a FiniteRankFreeModule (which is in the category of finite dimensional modules) to a parent that is in the category of finite dimensional modules with basis.

[mjungmath]

comment:16

Replying to @tscrim:

I might even go further to say that it would not be the identity map, but an isomorphism of free modules.

Well, yes. It is a special kind of automorphism. However, I wouldn't see it as an isomorphism between any two free modules of the same rank, in case this is what you are referring to.

Replying to @tscrim:

Although I am not sure how much the basis is intended as a basis as a set or the span of the basis elements. I suspect the former, so such a method would not make sense. I would have to see what Eric and Michal say.

I am not sure what you mean with "the span of the basis elements". This does not make any sense to me because the span is always the free module again. Anyway, I would see an instance of FreeModuleBasis as a representation of a (finite) subset of the corresponding free module which is linearly independent and generates the module (possibly in the sense of formal linear combinations).

[mjungmath]

comment:17

Replying to @tscrim:

These are incompatible objects since QQ^3 has a distinguished basis (the standard Euclidean basis) whereas Q3 does not. So there should not be a map between them.

Agreed.

My 2 cents for the error reported in the ticket is to first check that the object is not in the category. The other option is to lift the vector_space method up to the category of modules and then implement a change_ring method for Q3.

Sounds good. Who goes for it?

[egourgoulhon]

comment:18

Replying to @mkoeppe:

Replying to @egourgoulhon:

Coming back to the issue mentioned in the ticket title and description, I would say that the problem arises because "vector spaces" as they are implemented in Sage are not really vector spaces in all their generality but only Cartesian powers F^n, where F is the base field.

OK, I think we are getting closer.

When you say, '"vector spaces" as they are implemented in Sage', I assume you mean the ones implemented in sage.modules.free_module and constructed by the function VectorSpace,

Yes.

and then I agree with what you wrote.

What I was asking for in comment 8 is, given a basis, a map from a FiniteRankFreeModule (which is in the category of finite dimensional modules) to a parent that is in the category of finite dimensional modules with basis.

Yes, this is the basis-dependent isomorphism I was referring to comment:14, but my concern, and that of Travis if I understand correctly, is that such an isomorphism cannot be used for a coercion, because it is not canonical (by definition, it depends on a choice of basis).

[mkoeppe]

Branch: u/mkoeppe/unable_to_coerce_x___3_dimensional_vector_space_over_the_rational_field__into_category_of_vector_spaces_over_rational_field

[mkoeppe]

comment:20

Replying to @egourgoulhon:

Yes, this is the basis-dependent isomorphism I was referring to comment:14, but my concern, and that of Travis if I understand correctly, is that such an isomorphism cannot be used for a coercion, because it is not canonical (by definition, it depends on a choice of basis).

I've pushed a rough implementation of this to the ticket.

Sure, I don't need this to be a coercion. Just a module morphism.

---

New commits:

91e44f4

sage.tensor.modules.FiniteRankFreeModule.basis_fixing_map: New

[mkoeppe]

Commit: 91e44f4

[tscrim]

comment:21

Replying to @mjungmath:

Replying to @tscrim:

Although I am not sure how much the basis is intended as a basis as a set or the span of the basis elements. I suspect the former, so such a method would not make sense. I would have to see what Eric and Michal say.

I am not sure what you mean with "the span of the basis elements". This does not make any sense to me because the span is always the free module again. Anyway, I would see an instance of FreeModuleBasis as a representation of a (finite) subset of the corresponding free module which is linearly independent and generates the module (possibly in the sense of formal linear combinations).

The question is what does this class represent:

1. The basis itself, which is a finite set.
2. The span of the basis elements, which is a vector space where we can represent the points in terms of the chosen basis elements.

These are very different objects. One is finite, one is infinite (well, |R|ⁿ, where R is the base ring). Since you want to think of it as 1, then you are saying there should not be a morphism. However, most of the points of the free module should not be elements of this parent. The actual implementation is really treating it like 2, and its elements are the points of the free module represented using the chosen basis.

---

I like the proposed method overall. I have some suggestions:

1 - Change the name to something like morphism_with_fixed_basis as right now it sounds like it is constructing a map that happens to fix a basis.
2 - Allow the codomain of the map to be passed to the function. Then you can have the map be defined as

        if codomain.dimension() != self.dimension():
            raise ValueError
        B = list(codomain.basis())
        def function(x):
            return codomain.sum(x[basis, i] * B[i] for i in self.irange())

This should be implementation independent (if it is not, then it is a bug IMO).

[mkoeppe]

comment:22

Replying to @tscrim:

Replying to @mjungmath:

Replying to @tscrim:

Although I am not sure how much the basis is intended as a basis as a set or the span of the basis elements. I suspect the former, so such a method would not make sense. I would have to see what Eric and Michal say.

I am not sure what you mean with "the span of the basis elements". This does not make any sense to me because the span is always the free module again. Anyway, I would see an instance of FreeModuleBasis as a representation of a (finite) subset of the corresponding free module which is linearly independent and generates the module (possibly in the sense of formal linear combinations).

The question is what does this class represent:

1. The basis itself, which is a finite set.
2. The span of the basis elements, which is a vector space where we can represent the points in terms of the chosen basis elements.

I think it's clear that 1 is intended:

sage: V = FiniteRankFreeModule(QQ, 3)
sage: e = V.basis("e")
sage: e[0] in e
True
sage: e[1] in e
True
sage: e[0] + e[1] in e
False

[sagetrac-git]

Changed commit from 91e44f4 to 7366741

[sagetrac-git]

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

7366741

Rename, generalize

[tscrim]

comment:24

Ah, right. Yes, it is clear that it is 1. I got myself confused.

[mjungmath]

comment:25

Replying to @sagetrac-git:

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

7366741

Rename, generalize

I must agree Eric in comment:14, I don't see the use of such a method isomorphism_with_fixed_basis, not even in FiniteRankFreeModule.

I see no problem in implementing the coercion on the level of modules right away. There is no need for such method either in this case. The vector space QQ^3 forgets about the basis we have chosen, anyway (i.e. there is no going back). The important thing is that we are able to choose a basis. But this is ensured due to the definition of a free module.

I have to admit, I am not sure what's the problem is we're still discussing; apart from the error reported in the description. Is it still all about comment:2? As reported in this ticket, we want to coerce the free modules themselves and not their elements.

[mjungmath]

comment:54

I don't think the prefix is even necessary, but I can live with that.

[mkoeppe]

Reviewer: Michael Jung, Matthias Koeppe, ...

[egourgoulhon]

Changed reviewer from Michael Jung, Matthias Koeppe, ... to Michael Jung, Matthias Koeppe, Eric Gourgoulhon

[egourgoulhon]

comment:56

LGTM. Thanks!

[egourgoulhon]

comment:57

Shouldn't the code of this ticket use #30180 (cf. comment 1 in that ticket)? Then #30180 should be added as a dependency.

[mjungmath]

comment:58

Replying to @egourgoulhon:

Shouldn't the code of this ticket use #30180 (cf. comment 1 in that ticket)? Then #30180 should be added as a dependency.

I think, the independence should be the other way around, right Matthias?

[egourgoulhon]

comment:59

Replying to @mjungmath:

Replying to @egourgoulhon:

Shouldn't the code of this ticket use #30180 (cf. comment 1 in that ticket)? Then #30180 should be added as a dependency.

I think, the independence should be the other way around, right Matthias?

No, if the code in this ticket makes use of #30180's code, the dependency shall be set here to #30180.

[mjungmath]

comment:60

Replying to @egourgoulhon:

Replying to @mjungmath:

Replying to @egourgoulhon:

Shouldn't the code of this ticket use #30180 (cf. comment 1 in that ticket)? Then #30180 should be added as a dependency.

I think, the independence should be the other way around, right Matthias?

No, if the code in this ticket makes use of #30180's code, the dependency shall be set here to #30180.

This code works independently of #30180 and I don't see any snippets from #30180 used here.

[mkoeppe]

comment:61

Both of you are right.

[mkoeppe]

comment:62

Thanks to the speedy review of #30180, I will use it now to simplify the code on the present ticket.

[sagetrac-git]

Changed commit from affd0c9 to 8a800cc

[sagetrac-git]

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

0afa01c	Modules: Add parent method module_morphism
3c8d080	Fix docstring markup
e2fc5d5	Make sure that we only create a module morphism
68da24c	Merge branch 't/30180/category_modules_should_provide_a_parent_method_module_morphism_compatible_with_moduleswithbasis_module_morphism' into t/30094/public/tensor/basis_dependent_isomorphism_free_modules
8a800cc	FiniteRankFreeModule.isomorphism_with_fixed_basis: Simplify using self.module_morphism

[mkoeppe]

Dependencies: #30180

[tscrim]

comment:65

Morally green patchbot.

[egourgoulhon]

Changed reviewer from Michael Jung, Matthias Koeppe, Eric Gourgoulhon to Michael Jung, Matthias Koeppe, Eric Gourgoulhon, Travis Scrimshaw

[egourgoulhon]

comment:66

Thanks for the update!

[mkoeppe]

comment:67

Thanks!

[vbraun]

Changed branch from public/tensor/basis_dependent_isomorphism_free_modules to 8a800cc