Modules With Basis

AUTHORS:

• Nicolas M. Thiery (2008-2014): initial revision, axiomatization
• Jason Bandlow and Florent Hivert (2010): Triangular Morphisms
• Christian Stump (2010): trac ticket #9648 module_morphism’s to a wider class of codomains

class sage.categories.modules_with_basis.DiagonalModuleMorphism(diagonal, domain, codomain=None, category=None)

Bases: sage.categories.modules_with_basis.ModuleMorphismByLinearity

A class for diagonal module morphisms.

See ModulesWithBasis.ParentMethods.module_morphism().

INPUT:

• domain, codomain – two modules with basis \(F\) and \(G\), respectively
• diagonal – a function \(d\)

Assumptions:

• domain and codomain have the same base ring \(R\),
• their respective bases \(F\) and \(G\) have the same index set \(I\),
• \(d\) is a function \(I \to R\).

Return the diagonal module morphism from domain to codomain sending \(F(i) \mapsto d(i) G(i)\) for all \(i \in I\).

By default, codomain is currently assumed to be domain. (Todo: make a consistent choice with *ModuleMorphism.)

Todo

• Implement an optimized _call_() function.
• Generalize to a mapcoeffs.
• Generalize to a mapterms.

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X")
sage: phi = X.module_morphism(diagonal = factorial, codomain = X)
sage: x = X.basis()
sage: phi(x[1]), phi(x[2]), phi(x[3])
(B[1], 2*B[2], 6*B[3])

class sage.categories.modules_with_basis.ModuleMorphismByLinearity(domain, on_basis=None, position=0, zero=None, codomain=None, category=None)

Bases: sage.categories.morphism.Morphism

A class for module morphisms obtained by extending a function by linearity.

on_basis()

Return the action of this morphism on basis elements, as per ModulesWithBasis.Homsets.ElementMethods.on_basis().

OUTPUT:

• a function from the indices of the basis of the domain to the codomain

EXAMPLES:

sage: X = CombinatorialFreeModule(ZZ, [-2, -1, 1, 2])
sage: Y = CombinatorialFreeModule(ZZ, [1, 2])
sage: phi_on_basis = Y.monomial * abs
sage: phi = sage.categories.modules_with_basis.ModuleMorphismByLinearity(X, on_basis = phi_on_basis, codomain = Y)
sage: x = X.basis()
sage: phi.on_basis()(-2)
B[2]
sage: phi.on_basis() == phi_on_basis
True

class sage.categories.modules_with_basis.ModulesWithBasis(base_category)

Bases: sage.categories.category_with_axiom.CategoryWithAxiom_over_base_ring

The category of modules with a distinguished basis.

The elements are represented by expanding them in the distinguished basis. The morphisms are not required to respect the distinguished basis.

EXAMPLES:

sage: ModulesWithBasis(ZZ)
Category of modules with basis over Integer Ring
sage: ModulesWithBasis(ZZ).super_categories()
[Category of modules over Integer Ring]

If the base ring is actually a field, this constructs instead the category of vector spaces with basis:

sage: ModulesWithBasis(QQ)
Category of vector spaces with basis over Rational Field

sage: ModulesWithBasis(QQ).super_categories()
[Category of modules with basis over Rational Field,
 Category of vector spaces over Rational Field]

Let \(X\) and \(Y\) be two modules with basis. We can build \(Hom(X,Y)\):

sage: X = CombinatorialFreeModule(QQ, [1,2]); X.__custom_name = "X"
sage: Y = CombinatorialFreeModule(QQ, [3,4]); Y.__custom_name = "Y"
sage: H = Hom(X, Y); H
Set of Morphisms from X to Y in Category of vector spaces with basis over Rational Field

The simplest morphism is the zero map:

sage: H.zero()         # todo: move this test into module once we have an example
Generic morphism:
  From: X
  To:   Y

which we can apply to elements of \(X\):

sage: x = X.monomial(1) + 3 * X.monomial(2)
sage: H.zero()(x)
0

TESTS:

sage: f = H.zero().on_basis()
sage: f(1)
0
sage: f(2)
0

EXAMPLES:

We now construct a more interesting morphism by extending a function by linearity:

sage: phi = H(on_basis = lambda i: Y.monomial(i+2)); phi
Generic morphism:
  From: X
  To:   Y
sage: phi(x)
B[3] + 3*B[4]

We can retrieve the function acting on indices of the basis:

sage: f = phi.on_basis()
sage: f(1), f(2)
(B[3], B[4])

\(Hom(X,Y)\) has a natural module structure (except for the zero, the operations are not yet implemented though). However since the dimension is not necessarily finite, it is not a module with basis; but see FiniteDimensionalModulesWithBasis and GradedModulesWithBasis:

sage: H in ModulesWithBasis(QQ), H in Modules(QQ)
(False, True)

Some more playing around with categories and higher order homsets:

sage: H.category()
Category of homsets of modules with basis over Rational Field
sage: Hom(H, H).category()
Category of endsets of homsets of modules with basis over Rational Field

Todo

End(X) is an algebra.

TESTS:

sage: TestSuite(ModulesWithBasis(ZZ)).run()

class CartesianProducts(category, *args)

Bases: sage.categories.cartesian_product.CartesianProductsCategory

The category of modules with basis constructed by cartesian products of modules with basis.

class ParentMethods

ModulesWithBasis.CartesianProducts.extra_super_categories()

EXAMPLES:

sage: ModulesWithBasis(QQ).CartesianProducts().extra_super_categories()
[Category of vector spaces with basis over Rational Field]
sage: ModulesWithBasis(QQ).CartesianProducts().super_categories()
[Category of Cartesian products of modules with basis over Rational Field,
 Category of vector spaces with basis over Rational Field,
 Category of Cartesian products of vector spaces over Rational Field]

class ModulesWithBasis.DualObjects(category, *args)

Bases: sage.categories.dual.DualObjectsCategory

TESTS:

sage: from sage.categories.covariant_functorial_construction import CovariantConstructionCategory
sage: class FooBars(CovariantConstructionCategory):
...       _functor_category = "FooBars"
sage: Category.FooBars = lambda self: FooBars.category_of(self)
sage: C = FooBars(ModulesWithBasis(ZZ))
sage: C
Category of foo bars of modules with basis over Integer Ring
sage: C.base_category()
Category of modules with basis over Integer Ring
sage: latex(C)
\mathbf{FooBars}(\mathbf{ModulesWithBasis}_{\Bold{Z}})
sage: import __main__; __main__.FooBars = FooBars # Fake FooBars being defined in a python module
sage: TestSuite(C).run()

extra_super_categories()

EXAMPLES:

sage: ModulesWithBasis(ZZ).DualObjects().extra_super_categories()
[Category of modules over Integer Ring]
sage: ModulesWithBasis(QQ).DualObjects().super_categories()
[Category of duals of vector spaces over Rational Field, Category of duals of modules with basis over Rational Field]

class ModulesWithBasis.ElementMethods

leading_coefficient(cmp=None)

Returns the leading coefficient of self.

This is the coefficient of the term whose corresponding basis element is maximal. Note that this may not be the term which actually appears first when self is printed. If the default term ordering is not what is desired, a comparison function, cmp(x,y), can be provided. This should return a negative value if x < y, 0 if x == y and a positive value if x > y.

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X")
sage: x = 3*X.monomial(1) + 2*X.monomial(2) + X.monomial(3)
sage: x.leading_coefficient()
1
sage: def cmp(x,y): return y-x
sage: x.leading_coefficient(cmp=cmp)
3

sage: s = SymmetricFunctions(QQ).schur()
sage: f = 2*s[1] + 3*s[2,1] - 5*s[3]
sage: f.leading_coefficient()
-5

leading_item(cmp=None)

Return the pair (k, c) where

\[c \cdot (\mbox{the basis element indexed by } k)\]

is the leading term of self.

Here ‘leading term’ means that the corresponding basis element is maximal. Note that this may not be the term which actually appears first when self is printed. If the default term ordering is not what is desired, a comparison function, cmp(x,y), can be provided. This should return a negative value if x < y, 0 if x == y and a positive value if x > y.

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X"); x = X.basis()
sage: x = 3*X.monomial(1) + 2*X.monomial(2) + 4*X.monomial(3)
sage: x.leading_item()
(3, 4)
sage: def cmp(x,y): return y-x
sage: x.leading_item(cmp=cmp)
(1, 3)

sage: s = SymmetricFunctions(QQ).schur()
sage: f = 2*s[1] + 3*s[2,1] - 5*s[3]
sage: f.leading_item()
([3], -5)

leading_monomial(cmp=None)

Return the leading monomial of self.

This is the monomial whose corresponding basis element is maximal. Note that this may not be the term which actually appears first when self is printed. If the default term ordering is not what is desired, a comparison function, cmp(x,y), can be provided. This should return a negative value if x < y, 0 if x == y and a positive value if x > y.

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X"); x = X.basis()
sage: x = 3*X.monomial(1) + 2*X.monomial(2) + X.monomial(3)
sage: x.leading_monomial()
B[3]
sage: def cmp(x,y): return y-x
sage: x.leading_monomial(cmp=cmp)
B[1]

sage: s = SymmetricFunctions(QQ).schur()
sage: f = 2*s[1] + 3*s[2,1] - 5*s[3]
sage: f.leading_monomial()
s[3]

leading_support(cmp=None)

Return the maximal element of the support of self. Note that this may not be the term which actually appears first when self is printed.

If the default ordering of the basis elements is not what is desired, a comparison function, cmp(x,y), can be provided. This should return a negative value if x < y, 0 if x == y and a positive value if x > y.

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X"); x = X.basis()
sage: x = 3*X.monomial(1) + 2*X.monomial(2) + 4*X.monomial(3)
sage: x.leading_support()
3
sage: def cmp(x,y): return y-x
sage: x.leading_support(cmp=cmp)
1

sage: s = SymmetricFunctions(QQ).schur()
sage: f = 2*s[1] + 3*s[2,1] - 5*s[3]
sage: f.leading_support()
[3]

leading_term(cmp=None)

Return the leading term of self.

This is the term whose corresponding basis element is maximal. Note that this may not be the term which actually appears first when self is printed. If the default term ordering is not what is desired, a comparison function, cmp(x,y), can be provided. This should return a negative value if x < y, 0 if x == y and a positive value if x > y.

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X"); x = X.basis()
sage: x = 3*X.monomial(1) + 2*X.monomial(2) + X.monomial(3)
sage: x.leading_term()
B[3]
sage: def cmp(x,y): return y-x
sage: x.leading_term(cmp=cmp)
3*B[1]

sage: s = SymmetricFunctions(QQ).schur()
sage: f = 2*s[1] + 3*s[2,1] - 5*s[3]
sage: f.leading_term()
-5*s[3]

map_coefficients(f)

Mapping a function on coefficients.

INPUT:

• f – an endofunction on the coefficient ring of the free module

Return a new element of self.parent() obtained by applying the function f to all of the coefficients of self.

EXAMPLES:

sage: F = CombinatorialFreeModule(QQ, ['a','b','c'])
sage: B = F.basis()
sage: f = B['a'] - 3*B['c']
sage: f.map_coefficients(lambda x: x+5)
6*B['a'] + 2*B['c']

Killed coefficients are handled properly:

sage: f.map_coefficients(lambda x: 0)
0
sage: list(f.map_coefficients(lambda x: 0))
[]

sage: s = SymmetricFunctions(QQ).schur()
sage: a = s([2,1])+2*s([3,2])
sage: a.map_coefficients(lambda x: x*2)
2*s[2, 1] + 4*s[3, 2]

map_item(f)

Mapping a function on items.

INPUT:

• f – a function mapping pairs (index, coeff) to other such pairs

Return a new element of self.parent() obtained by applying the function \(f\) to all items (index, coeff) of self.

EXAMPLES:

sage: B = CombinatorialFreeModule(ZZ, [-1, 0, 1])
sage: x = B.an_element(); x
2*B[-1] + 2*B[0] + 3*B[1]
sage: x.map_item(lambda i, c: (-i, 2*c))
6*B[-1] + 4*B[0] + 4*B[1]

f needs not be injective:

sage: x.map_item(lambda i, c: (1, 2*c))
14*B[1]

sage: s = SymmetricFunctions(QQ).schur()
sage: f = lambda m,c: (m.conjugate(), 2*c)
sage: a = s([2,1]) + s([1,1,1])
sage: a.map_item(f)
2*s[2, 1] + 2*s[3]

map_support(f)

Mapping a function on the support.

INPUT:

• f – an endofunction on the indices of the free module

Return a new element of self.parent() obtained by applying the function f to all of the objects indexing the basis elements.

EXAMPLES:

sage: B = CombinatorialFreeModule(ZZ, [-1, 0, 1])
sage: x = B.an_element(); x
2*B[-1] + 2*B[0] + 3*B[1]
sage: x.map_support(lambda i: -i)
3*B[-1] + 2*B[0] + 2*B[1]

f needs not be injective:

sage: x.map_support(lambda i: 1)
7*B[1]

sage: s = SymmetricFunctions(QQ).schur()
sage: a = s([2,1])+2*s([3,2])
sage: a.map_support(lambda x: x.conjugate())
s[2, 1] + 2*s[2, 2, 1]

TESTS:

sage: B.zero()      # This actually failed at some point!!! See #8890
0

sage: y = B.zero().map_support(lambda i: i/0); y
0
sage: y.parent() is B
True

map_support_skip_none(f)

Mapping a function on the support.

INPUT:

• f – an endofunction on the indices of the free module

Returns a new element of self.parent() obtained by applying the function \(f\) to all of the objects indexing the basis elements.

EXAMPLES:

sage: B = CombinatorialFreeModule(ZZ, [-1, 0, 1])
sage: x = B.an_element(); x
2*B[-1] + 2*B[0] + 3*B[1]
sage: x.map_support_skip_none(lambda i: -i if i else None)
3*B[-1] + 2*B[1]

f needs not be injective:

sage: x.map_support_skip_none(lambda i: 1 if i else None)
5*B[1]

TESTS:

sage: y = x.map_support_skip_none(lambda i: None); y
0
sage: y.parent() is B
True

support_of_term()

Return the support of self, where self is a monomial (possibly with coefficient).

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1,2,3,4]); X.rename("X")
sage: X.monomial(2).support_of_term()
2
sage: X.term(3, 2).support_of_term()
3

An exception is raised if self has more than one term:

sage: (X.monomial(2) + X.monomial(3)).support_of_term()
Traceback (most recent call last):
...
ValueError: B[2] + B[3] is not a single term

tensor(*elements)

Return the tensor product of its arguments, as an element of the tensor product of the parents of those elements.

EXAMPLES:

sage: C = AlgebrasWithBasis(QQ)
sage: A = C.example()
sage: (a,b,c) = A.algebra_generators()
sage: a.tensor(b, c)
B[word: a] # B[word: b] # B[word: c]

FIXME: is this a policy that we want to enforce on all parents?

trailing_coefficient(cmp=None)

Return the trailing coefficient of self.

This is the coefficient of the monomial whose corresponding basis element is minimal. Note that this may not be the term which actually appears last when self is printed. If the default term ordering is not what is desired, a comparison function cmp(x,y), can be provided. This should return a negative value if x < y, 0 if x == y and a positive value if x > y.

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X"); x = X.basis()
sage: x = 3*X.monomial(1) + 2*X.monomial(2) + X.monomial(3)
sage: x.trailing_coefficient()
3
sage: def cmp(x,y): return y-x
sage: x.trailing_coefficient(cmp=cmp)
1

sage: s = SymmetricFunctions(QQ).schur()
sage: f = 2*s[1] + 3*s[2,1] - 5*s[3]
sage: f.trailing_coefficient()
2

trailing_item(cmp=None)

Returns the pair (c, k) where c*self.parent().monomial(k) is the trailing term of self.

This is the monomial whose corresponding basis element is minimal. Note that this may not be the term which actually appears last when self is printed. If the default term ordering is not what is desired, a comparison function cmp(x,y), can be provided. This should return a negative value if x < y, 0 if x == y and a positive value if x > y.

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X"); x = X.basis()
sage: x = 3*X.monomial(1) + 2*X.monomial(2) + X.monomial(3)
sage: x.trailing_item()
(1, 3)
sage: def cmp(x,y): return y-x
sage: x.trailing_item(cmp=cmp)
(3, 1)

sage: s = SymmetricFunctions(QQ).schur()
sage: f = 2*s[1] + 3*s[2,1] - 5*s[3]
sage: f.trailing_item()
([1], 2)

trailing_monomial(cmp=None)

Return the trailing monomial of self.

This is the monomial whose corresponding basis element is minimal. Note that this may not be the term which actually appears last when self is printed. If the default term ordering is not what is desired, a comparison function cmp(x,y), can be provided. This should return a negative value if x < y, 0 if x == y and a positive value if x > y.

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X"); x = X.basis()
sage: x = 3*X.monomial(1) + 2*X.monomial(2) + X.monomial(3)
sage: x.trailing_monomial()
B[1]
sage: def cmp(x,y): return y-x
sage: x.trailing_monomial(cmp=cmp)
B[3]

sage: s = SymmetricFunctions(QQ).schur()
sage: f = 2*s[1] + 3*s[2,1] - 5*s[3]
sage: f.trailing_monomial()
s[1]

trailing_support(cmp=None)

Return the minimal element of the support of self. Note that this may not be the term which actually appears last when self is printed.

If the default ordering of the basis elements is not what is desired, a comparison function, cmp(x,y), can be provided. This should return a negative value if x < y, \(0\) if x == y and a positive value if x > y.

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X"); x = X.basis()
sage: x = 3*X.monomial(1) + 2*X.monomial(2) + 4*X.monomial(3)
sage: x.trailing_support()
1
sage: def cmp(x,y): return y-x
sage: x.trailing_support(cmp=cmp)
3

sage: s = SymmetricFunctions(QQ).schur()
sage: f = 2*s[1] + 3*s[2,1] - 5*s[3]
sage: f.trailing_support()
[1]

trailing_term(cmp=None)

Return the trailing term of self.

This is the term whose corresponding basis element is minimal. Note that this may not be the term which actually appears last when self is printed. If the default term ordering is not what is desired, a comparison function cmp(x,y), can be provided. This should return a negative value if x < y, 0 if x == y and a positive value if x > y.

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X"); x = X.basis()
sage: x = 3*X.monomial(1) + 2*X.monomial(2) + X.monomial(3)
sage: x.trailing_term()
3*B[1]
sage: def cmp(x,y): return y-x
sage: x.trailing_term(cmp=cmp)
B[3]

sage: s = SymmetricFunctions(QQ).schur()
sage: f = 2*s[1] + 3*s[2,1] - 5*s[3]
sage: f.trailing_term()
2*s[1]

ModulesWithBasis.FiniteDimensional

alias of FiniteDimensionalModulesWithBasis

ModulesWithBasis.Graded

alias of GradedModulesWithBasis

class ModulesWithBasis.Homsets(category, *args)

Bases: sage.categories.homsets.HomsetsCategory

TESTS:

sage: from sage.categories.covariant_functorial_construction import CovariantConstructionCategory
sage: class FooBars(CovariantConstructionCategory):
...       _functor_category = "FooBars"
sage: Category.FooBars = lambda self: FooBars.category_of(self)
sage: C = FooBars(ModulesWithBasis(ZZ))
sage: C
Category of foo bars of modules with basis over Integer Ring
sage: C.base_category()
Category of modules with basis over Integer Ring
sage: latex(C)
\mathbf{FooBars}(\mathbf{ModulesWithBasis}_{\Bold{Z}})
sage: import __main__; __main__.FooBars = FooBars # Fake FooBars being defined in a python module
sage: TestSuite(C).run()

class ParentMethods

class ModulesWithBasis.MorphismMethods

on_basis()

Return the action of this morphism on basis elements.

OUTPUT:

• a function from the indices of the basis of the domain to the codomain

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1,2,3]);   X.rename("X")
sage: Y = CombinatorialFreeModule(QQ, [1,2,3,4]); Y.rename("Y")
sage: H = Hom(X, Y)
sage: x = X.basis()

sage: f = H(lambda x: Y.zero()).on_basis()
sage: f(2)
0

sage: f = lambda i: Y.monomial(i) + 2*Y.monomial(i+1)
sage: g = H(on_basis = f).on_basis()
sage: g(2)
B[2] + 2*B[3]
sage: g == f
True

class ModulesWithBasis.ParentMethods

basis()

Return the basis of self.

EXAMPLES:

sage: F = CombinatorialFreeModule(QQ, ['a','b','c'])
sage: F.basis()
Finite family {'a': B['a'], 'c': B['c'], 'b': B['b']}

sage: QS3 = SymmetricGroupAlgebra(QQ,3)
sage: list(QS3.basis())
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

module_morphism(on_basis=None, diagonal=None, triangular=None, **keywords)

Construct a morphism from self to codomain by linearity from its restriction on_basis to the basis of self.

Let self be the module \(X\) with a basis indexed by \(I\). This constructs a morphism \(f: X \to Y\) by linearity from a map \(I \to Y\) which is to be its restriction to the basis \((x_i)_{i \in I}\) of \(X\).

INPUT:

• codomain – the codomain \(Y\) of \(f\): defaults to f.codomain() if the latter is defined
• zero – the zero of the codomain; defaults to codomain.zero(); can be used (with care) to define affine maps
• position – a non-negative integer; defaults to 0
• on_basis – a function \(f\) which accepts elements of \(I\) (the indexing set of the basis of \(X\)) as position-th argument and returns elements of \(Y\)
• diagonal – a function \(d\) from \(I\) to \(R\) (the base ring of self and codomain)
• triangular – (default: None) "upper" or "lower" or None:
  • "upper" - if the leading_support() of the image of the basis vector \(x_i\) is \(i\), or
  • "lower" - if the trailing_support() of the image of the basis vector \(x_i\) is \(i\)
• category – a category; by default, this is ModulesWithBasis(R) if \(Y\) is in this category, and otherwise this lets \(Hom(X,Y)\) decide

Exactly one of on_basis and diagonal options should be specified.

With the on_basis option, this returns a function \(g\) obtained by extending \(f\) by linearity on the position-th positional argument. For example, for position == 1 and a ternary function \(f\), one has:

\[g\left( a,\ \sum_i \lambda_i x_i,\ c \right) = \sum_i \lambda_i f(a, i, c).\]

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1,2,3]);   X.rename("X")
sage: Y = CombinatorialFreeModule(QQ, [1,2,3,4]); Y.rename("Y")
sage: phi = X.module_morphism(lambda i: Y.monomial(i) + 2*Y.monomial(i+1), codomain = Y)
sage: phi
Generic morphism:
From: X
To:   Y
sage: phi.category_for()
Category of vector spaces with basis over Rational Field
sage: x = X.basis(); y = Y.basis()
sage: phi(x[1] + x[3])
B[1] + 2*B[2] + B[3] + 2*B[4]

With the zero argument, one can define affine morphisms:

sage: phi = X.module_morphism(lambda i: Y.monomial(i) + 2*Y.monomial(i+1), codomain = Y, zero = 10*y[1])
sage: phi(x[1] + x[3])
11*B[1] + 2*B[2] + B[3] + 2*B[4]
sage: phi.category_for()
Category of sets

One can construct morphisms with the base ring as codomain:

sage: X = CombinatorialFreeModule(ZZ,[1,-1])
sage: phi = X.module_morphism( on_basis=lambda i: i, codomain=ZZ )
sage: phi( 2 * X.monomial(1) + 3 * X.monomial(-1) )
-1
sage: phi.category_for()
Category of commutative additive semigroups
sage: phi.category_for() # todo: not implemented (ZZ is currently not in Modules(ZZ))
Category of modules over Integer Ring

Or more generaly any ring admitting a coercion map from the base ring:

sage: phi = X.module_morphism(on_basis= lambda i: i, codomain=RR )
sage: phi( 2 * X.monomial(1) + 3 * X.monomial(-1) )
-1.00000000000000
sage: phi.category_for()
Category of commutative additive semigroups
sage: phi.category_for() # todo: not implemented (RR is currently not in Modules(ZZ))
Category of modules over Integer Ring

sage: phi = X.module_morphism(on_basis= lambda i: i, codomain=Zmod(4) )
sage: phi( 2 * X.monomial(1) + 3 * X.monomial(-1) )
3

sage: phi = Y.module_morphism(on_basis= lambda i: i, codomain=Zmod(4) )
Traceback (most recent call last):
...
ValueError: codomain(=Ring of integers modulo 4) should be a module over the base ring of the domain(=Y)

On can also define module morphisms between free modules over different base rings; here we implement the natural map from \(X = \RR^2\) to \(Y = \CC\):

sage: X = CombinatorialFreeModule(RR,['x','y'])
sage: Y = CombinatorialFreeModule(CC,['z'])
sage: x = X.monomial('x')
sage: y = X.monomial('y')
sage: z = Y.monomial('z')
sage: def on_basis( a ):
....:     if a == 'x':
....:         return CC(1) * z
....:     elif a == 'y':
....:         return CC(I) * z
sage: phi = X.module_morphism( on_basis=on_basis, codomain=Y )
sage: v = 3 * x + 2 * y; v
3.00000000000000*B['x'] + 2.00000000000000*B['y']
sage: phi(v)
(3.00000000000000+2.00000000000000*I)*B['z']
sage: phi.category_for()
Category of commutative additive semigroups
sage: phi.category_for() # todo: not implemented (CC is currently not in Modules(RR)!)
Category of vector spaces over Real Field with 53 bits of precision

sage: Y = CombinatorialFreeModule(CC['q'],['z'])
sage: z = Y.monomial('z')
sage: phi = X.module_morphism( on_basis=on_basis, codomain=Y )
sage: phi(v)
(3.00000000000000+2.00000000000000*I)*B['z']

Of course, there should be a coercion between the respective base rings of the domain and the codomain for this to be meaningful:

sage: Y = CombinatorialFreeModule(QQ,['z'])
sage: phi = X.module_morphism( on_basis=on_basis, codomain=Y )
Traceback (most recent call last):
...
ValueError: codomain(=Free module generated by {'z'} over Rational Field) should be a module over the base ring of the domain(=Free module generated by {'x', 'y'} over Real Field with 53 bits of precision)

sage: Y = CombinatorialFreeModule(RR['q'],['z'])
sage: phi = Y.module_morphism( on_basis=on_basis, codomain=X )
Traceback (most recent call last):
...
ValueError: codomain(=Free module generated by {'x', 'y'} over Real Field with 53 bits of precision) should be a module over the base ring of the domain(=Free module generated by {'z'} over Univariate Polynomial Ring in q over Real Field with 53 bits of precision)

With the diagonal argument, this returns the module morphism \(g\) such that:

\(g(x_i) = d(i) y_i\)

This assumes that the respective bases \(x\) and \(y\) of \(X\) and \(Y\) have the same index set \(I\).

With triangular = upper, the constructed module morphism is assumed to be upper triangular; that is its matrix in the distinguished basis of \(X\) and \(Y\) would be upper triangular with invertible elements on its diagonal. This is used to compute preimages and inverting the morphism:

sage: I = range(1,200)
sage: X = CombinatorialFreeModule(QQ, I); X.rename("X"); x = X.basis()
sage: Y = CombinatorialFreeModule(QQ, I); Y.rename("Y"); y = Y.basis()
sage: f = Y.sum_of_monomials * divisors
sage: phi = X.module_morphism(f, triangular="upper", codomain = Y)
sage: phi(x[2])
B[1] + B[2]
sage: phi(x[6])
B[1] + B[2] + B[3] + B[6]
sage: phi(x[30])
B[1] + B[2] + B[3] + B[5] + B[6] + B[10] + B[15] + B[30]
sage: phi.preimage(y[2])
-B[1] + B[2]
sage: phi.preimage(y[6])
B[1] - B[2] - B[3] + B[6]
sage: phi.preimage(y[30])
-B[1] + B[2] + B[3] + B[5] - B[6] - B[10] - B[15] + B[30]
sage: (phi^-1)(y[30])
-B[1] + B[2] + B[3] + B[5] - B[6] - B[10] - B[15] + B[30]

For details and further optional arguments, see sage.categories.modules_with_basis.TriangularModuleMorphism.

Caveat: the returned element is in Hom(codomain, domain, category). This is only correct for unary functions.

Todo

Should codomain be self by default in the diagonal and triangular cases?

tensor(*parents)

Return the tensor product of the parents.

EXAMPLES:

sage: C = AlgebrasWithBasis(QQ)
sage: A = C.example(); A.rename("A")
sage: A.tensor(A,A)
A # A # A
sage: A.rename(None)

class ModulesWithBasis.TensorProducts(category, *args)

Bases: sage.categories.tensor.TensorProductsCategory

The category of modules with basis constructed by tensor product of modules with basis.

class ElementMethods

Implements operations on elements of tensor products of modules with basis.

apply_multilinear_morphism(f, codomain=None)

Return the result of applying the morphism induced by f to self.

INPUT:

• f – a multilinear morphism from the component modules of the parent tensor product to any module
• codomain – the codomain of f (optional)

By the universal property of the tensor product, f induces a linear morphism from \(self.parent()\) to the target module. Returns the result of applying that morphism to self.

The codomain is used for optimizations purposes only. If it’s not provided, it’s recovered by calling f on the zero input.

EXAMPLES:

We start with simple (admittedly not so interesting) examples, with two modules \(A\) and \(B\):

sage: A = CombinatorialFreeModule(ZZ, [1,2], prefix="A"); A.rename("A")
sage: B = CombinatorialFreeModule(ZZ, [3,4], prefix="B"); B.rename("B")

and \(f\) the bilinear morphism \((a,b) \mapsto b \otimes a\) from \(A \times B\) to \(B \otimes A\):

sage: def f(a,b):
....:     return tensor([b,a])

Now, calling applying \(f\) on \(a \otimes b\) returns the same as \(f(a,b)\):

sage: a = A.monomial(1) + 2 * A.monomial(2); a
A[1] + 2*A[2]
sage: b = B.monomial(3) - 2 * B.monomial(4); b
B[3] - 2*B[4]
sage: f(a,b)
B[3] # A[1] + 2*B[3] # A[2] - 2*B[4] # A[1] - 4*B[4] # A[2]
sage: tensor([a,b]).apply_multilinear_morphism(f)
B[3] # A[1] + 2*B[3] # A[2] - 2*B[4] # A[1] - 4*B[4] # A[2]

\(f\) may be a bilinear morphism to any module over the base ring of \(A\) and \(B\). Here the codomain is \(\ZZ\):

sage: def f(a,b):
....:     return sum(a.coefficients(), 0) * sum(b.coefficients(), 0)
sage: f(a,b)
-3
sage: tensor([a,b]).apply_multilinear_morphism(f)
-3

Mind the \(0\) in the sums above; otherwise \(f\) would not return \(0\) in \(\ZZ\):

sage: def f(a,b):
....:     return sum(a.coefficients()) * sum(b.coefficients())
sage: type(f(A.zero(), B.zero()))
<type 'int'>

Which would be wrong and break this method:

sage: tensor([a,b]).apply_multilinear_morphism(f)
Traceback (most recent call last):
...
AttributeError: 'int' object has no attribute 'parent'

Here we consider an example where the codomain is a module with basis with a different base ring:

   sage: C = CombinatorialFreeModule(QQ, [(1,3),(2,4)], prefix="C"); C.rename("C")
   sage: def f(a,b):
   ....:     return C.sum_of_terms( [((1,3), QQ(a[1]*b[3])), ((2,4), QQ(a[2]*b[4]))] )
   sage: f(a,b)
   C[(1, 3)] - 4*C[(2, 4)]
   sage: tensor([a,b]).apply_multilinear_morphism(f)
   C[(1, 3)] - 4*C[(2, 4)]

We conclude with a real life application, where we
check that the antipode of the Hopf algebra of
Symmetric functions on the Schur basis satisfies its
defining formula::

   sage: Sym = SymmetricFunctions(QQ)
   sage: s = Sym.schur()
   sage: def f(a,b): return a*b.antipode()
   sage: x = 4*s.an_element(); x
   8*s[] + 8*s[1] + 12*s[2]
   sage: x.coproduct().apply_multilinear_morphism(f)
   8*s[]
   sage: x.coproduct().apply_multilinear_morphism(f) == x.counit()
   True

We recover the constant term of \(x\), as desired.

Todo

Extract a method to linearize a multilinear morphism, and delegate the work there.

class ModulesWithBasis.TensorProducts.ParentMethods

Implements operations on tensor products of modules with basis.

ModulesWithBasis.TensorProducts.extra_super_categories()

EXAMPLES:

sage: ModulesWithBasis(QQ).TensorProducts().extra_super_categories()
[Category of vector spaces with basis over Rational Field]
sage: ModulesWithBasis(QQ).TensorProducts().super_categories()
[Category of tensor products of modules with basis over Rational Field,
 Category of vector spaces with basis over Rational Field,
 Category of tensor products of vector spaces over Rational Field]

ModulesWithBasis.is_abelian()

Returns whether this category is abelian.

This is the case if and only if the base ring is a field.

EXAMPLES:

sage: ModulesWithBasis(QQ).is_abelian()
True
sage: ModulesWithBasis(ZZ).is_abelian()
False

class sage.categories.modules_with_basis.PointwiseInverseFunction(f)

Bases: sage.structure.sage_object.SageObject

A class for pointwise inverse functions.

The pointwise inverse function of a function \(f\) is the function sending every \(x\) to \(1 / f(x)\).

EXAMPLES:

sage: from sage.categories.modules_with_basis import PointwiseInverseFunction
sage: f = PointwiseInverseFunction(factorial)
sage: f(0), f(1), f(2), f(3)
(1, 1, 1/2, 1/6)

pointwise_inverse()

TESTS:

sage: from sage.categories.modules_with_basis import PointwiseInverseFunction
sage: g = PointwiseInverseFunction(operator.mul)
sage: g.pointwise_inverse() is operator.mul
True

class sage.categories.modules_with_basis.TriangularModuleMorphism(on_basis, domain, triangular='upper', unitriangular=False, codomain=None, category=None, cmp=None, inverse=None, inverse_on_support=None, invertible=None)

Bases: sage.categories.modules_with_basis.ModuleMorphismByLinearity

A class for triangular module morphisms; that is, module morphisms from \(X\) to \(Y\) whose representing matrix in the distinguished bases of \(X\) and \(Y\) is upper triangular with invertible elements on its diagonal.

See ModulesWithBasis.ParentMethods.module_morphism()

INPUT:

• domain – a module \(X\) with basis \(F\)
• codomain – a module \(Y\) with basis \(G\) (defaults to \(X\))
• on_basis – a function from the index set of the basis \(F\) to the module \(Y\) which determines the morphism by linearity
• unitriangular – boolean (default: False)
• triangular – (default: "upper") "upper" or "lower":
  • "upper" - if the leading_support() of the image of \(F(i)\) is \(i\), or
  • "lower" - if the trailing_support() of the image of \(F(i)\) is \(i\)
• cmp – an optional comparison function on the index set \(J\) of the basis \(G\) of the codomain.
• invertible – boolean or None (default: None); should be set to True if Sage is to compute an inverse for self. Automatically set to True if the domain and codomain share the same indexing set and to False otherwise.
• inverse_on_support - compute the inverse on the support if the codomain and domain have different index sets. See assumptions below.

Assumptions:

• \(X\) and \(Y\) have the same base ring \(R\).
• Let \(I\) and \(J\) be the respective index sets of the bases \(F\) and \(G\). Either \(I = J\), or inverse_on_support is a function \(r : J \to I\) with the following property: for any \(j \in J\), \(r(j)\) should return an \(i \in I\) such that the leading term (or trailing term, if triangular is set to "lower") of on_basis(i) (with respect to the comparison cmp, if the latter is set, or just the default comparison otherwise) is \(j\) if there exists such an \(i\), or None if not.

OUTPUT:

The triangular module morphism from \(X\) to \(Y\) which maps \(F(i)\) to on_basis(i) and is extended by linearity.

EXAMPLES:

We construct and invert an upper unitriangular module morphism between two free \(\QQ\)-modules:

sage: I = range(1,200)
sage: X = CombinatorialFreeModule(QQ, I); X.rename("X"); x = X.basis()
sage: Y = CombinatorialFreeModule(QQ, I); Y.rename("Y"); y = Y.basis()
sage: f = Y.sum_of_monomials * divisors   # This * is map composition.
sage: phi = X.module_morphism(f, triangular="upper", unitriangular = True, codomain = Y)
sage: phi(x[2])
B[1] + B[2]
sage: phi(x[6])
B[1] + B[2] + B[3] + B[6]
sage: phi(x[30])
B[1] + B[2] + B[3] + B[5] + B[6] + B[10] + B[15] + B[30]
sage: phi.preimage(y[2])
-B[1] + B[2]
sage: phi.preimage(y[6])
B[1] - B[2] - B[3] + B[6]
sage: phi.preimage(y[30])
-B[1] + B[2] + B[3] + B[5] - B[6] - B[10] - B[15] + B[30]
sage: (phi^-1)(y[30])
-B[1] + B[2] + B[3] + B[5] - B[6] - B[10] - B[15] + B[30]

A lower triangular (but not unitriangular) morphism:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X"); x = X.basis()
sage: def ut(i): return sum(j*x[j] for j in range(i,4))
sage: phi = X.module_morphism(ut, triangular="lower", codomain = X)
sage: phi(x[2])
2*B[2] + 3*B[3]
sage: phi.preimage(x[2])
1/2*B[2] - 1/2*B[3]
sage: phi(phi.preimage(x[2]))
B[2]

Using the cmp keyword, we can use triangularity even if the map becomes triangular only after a permutation of the basis:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X"); x = X.basis()
sage: def vt(i): return (x[1] + x[2] if i == 1 else x[2] + (x[3] if i == 3 else 0))
sage: perm = [0, 2, 1, 3]
sage: phi = X.module_morphism(vt, triangular="upper", codomain = X,
....:                         cmp=lambda a, b: cmp(perm[a], perm[b]))
sage: [phi(x[i]) for i in range(1, 4)]
[B[1] + B[2], B[2], B[2] + B[3]]
sage: [phi.preimage(x[i]) for i in range(1, 4)]
[B[1] - B[2], B[2], -B[2] + B[3]]

The same works in the lower-triangular case:

sage: def wt(i): return (x[1] + x[2] + x[3] if i == 2 else x[i])
sage: phi = X.module_morphism(wt, triangular="lower", codomain = X,
....:                         cmp=lambda a, b: cmp(perm[a], perm[b]))
sage: [phi(x[i]) for i in range(1, 4)]
[B[1], B[1] + B[2] + B[3], B[3]]
sage: [phi.preimage(x[i]) for i in range(1, 4)]
[B[1], -B[1] + B[2] - B[3], B[3]]

An injective but not surjective morphism cannot be inverted, but the inverse_on_support keyword allows Sage to find a partial inverse:

sage: X = CombinatorialFreeModule(QQ, [1,2,3]); x = X.basis()
sage: Y = CombinatorialFreeModule(QQ, [1,2,3,4,5]); y = Y.basis()
sage: uut = lambda i: sum(  y[j] for j in range(i+1,6)  )
sage: phi = X.module_morphism(uut, codomain = Y,
....:        triangular=True, unitriangular=True,
....:        inverse_on_support=lambda i: i-1 if i in [2,3,4] else None)
sage: phi(x[2])
B[3] + B[4] + B[5]
sage: phi.preimage(y[3])
B[2] - B[3]

The inverse_on_support keyword can also be used if the bases of the domain and the codomain are identical but one of them has to be permuted in order to render the morphism triangular. For example:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X"); x = X.basis()
sage: def zt(i):
....:     return (x[3] if i == 1 else x[1] if i == 2
....:             else x[1] + x[2])
sage: def perm(i):
....:     return (2 if i == 1 else 3 if i == 2 else 1)
sage: phi = X.module_morphism(zt, triangular="upper", codomain = X,
....:                         inverse_on_support=perm)
sage: [phi(x[i]) for i in range(1, 4)]
[B[3], B[1], B[1] + B[2]]
sage: [phi.preimage(x[i]) for i in range(1, 4)]
[B[2], -B[2] + B[3], B[1]]

The same works if the permutation induces lower triangularity:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X"); x = X.basis()
sage: def zt(i):
....:     return (x[3] if i == 1 else x[2] if i == 2
....:             else x[1] + x[2])
sage: def perm(i):
....:     return 4 - i
sage: phi = X.module_morphism(zt, triangular="lower", codomain = X,
....:                         inverse_on_support=perm)
sage: [phi(x[i]) for i in range(1, 4)]
[B[3], B[2], B[1] + B[2]]
sage: [phi.preimage(x[i]) for i in range(1, 4)]
[-B[2] + B[3], B[2], B[1]]

The inverse_on_basis and cmp keywords can be combined:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); X.rename("X"); x = X.basis()
sage: def zt(i):
....:     return (2*x[2] + 3*x[3] if i == 1
....:             else x[1] + x[2] + x[3] if i == 2
....:             else 4*x[2])
sage: def perm(i):
....:     return (2 if i == 1 else 3 if i == 2 else 1)
sage: perverse_cmp = lambda a, b: cmp((a-2) % 3, (b-2) % 3)
sage: phi = X.module_morphism(zt, triangular="upper", codomain = X,
....:                         inverse_on_support=perm, cmp=perverse_cmp)
sage: [phi(x[i]) for i in range(1, 4)]
[2*B[2] + 3*B[3], B[1] + B[2] + B[3], 4*B[2]]
sage: [phi.preimage(x[i]) for i in range(1, 4)]
[-1/3*B[1] + B[2] - 1/12*B[3], 1/4*B[3], 1/3*B[1] - 1/6*B[3]]

co_kernel_projection(category=None)

Return a projection on the co-kernel of self.

INPUT:

• category – the category of the result

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1,2,3]); x = X.basis()
sage: Y = CombinatorialFreeModule(QQ, [1,2,3,4,5]); y = Y.basis()
sage: uut = lambda i: sum(  y[j] for j in range(i+1,6)  ) # uni-upper
sage: phi = X.module_morphism(uut, triangular=True, codomain = Y,
....:      inverse_on_support=lambda i: i-1 if i in [2,3,4] else None)
sage: phipro = phi.co_kernel_projection()
sage: phipro(y[1] + y[2])
B[1]
sage: all(phipro(phi(x)).is_zero() for x in X.basis())
True
sage: phipro(y[1])
B[1]
sage: phipro(y[4])
-B[5]
sage: phipro(y[5])
B[5]

co_reduced(y)

Reduce element \(y\) of codomain of self w.r.t. the image of self.

Suppose that self is a morphism from \(X\) to \(Y\). Then for any \(y \in Y\), the call self.co_reduced(y) returns a normal form for \(y\) in the quotient \(Y / I\) where \(I\) is the image of self.

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); x = X.basis()
sage: Y = CombinatorialFreeModule(QQ, [1, 2, 3]); y = Y.basis()
sage: uut = lambda i: sum(  y[j] for j in range(i,4)  ) # uni-upper
sage: phi = X.module_morphism(uut, triangular=True, codomain = Y)
sage: phi.co_reduced(y[1] + y[2])
0

preimage(f)

Return the preimage of \(f\) under self.

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); x = X.basis()
sage: Y = CombinatorialFreeModule(QQ, [1, 2, 3]); y = Y.basis()
sage: uut = lambda i: sum(  y[j] for j in range(i,4)  ) # uni-upper
sage: phi = X.module_morphism(uut, triangular=True, codomain = Y)
sage: phi.preimage(y[1] + y[2])
B[1] - B[3]

sage: X = CombinatorialFreeModule(QQ, [1, 2, 3]); x = X.basis()
sage: Y = CombinatorialFreeModule(QQ, [1, 2, 3, 4]); y = Y.basis()
sage: uut = lambda i: sum(  y[j] for j in range(i,5)  ) # uni-upper
sage: phi = X.module_morphism(uut, triangular=True, codomain = Y)
sage: phi.preimage(y[1] + y[2])
B[1] - B[3]

sage: X = CombinatorialFreeModule(QQ, [1,2,3]); x = X.basis()
sage: X.rename("X")
sage: Y = CombinatorialFreeModule(QQ, [1,2,3,4,5]); y = Y.basis()
sage: uut = lambda i: sum(  y[j] for j in range(i+1,6)  ) # uni-upper
sage: phi = X.module_morphism(uut, triangular=True, codomain = Y,
....:         inverse_on_support=lambda i: i-1 if i in [2,3,4] else None)
sage: phi.preimage(y[2] + y[3])
B[1] - B[3]
sage: phi(phi.preimage(y[2] + y[3])) == y[2] + y[3]
True
sage: el = x[1] + 3*x[2] + 2*x[3]
sage: phi.preimage(phi(el)) == el
True

sage: phi = X.module_morphism(uut, triangular=True, codomain = Y,
....:         inverse_on_support=lambda i: i-1 if i in [2,3,4] else None)
sage: phi.preimage(y[1])
Traceback (most recent call last):
...
ValueError: B[1] is not in the image

section()

Return the section (partial inverse) of self.

Return a partial triangular morphism which is a section of self. The section morphism raise a ValueError if asked to apply on an element which is not in the image of self.

EXAMPLES:

sage: X = CombinatorialFreeModule(QQ, [1,2,3]); x = X.basis()
sage: X.rename('X')
sage: Y = CombinatorialFreeModule(QQ, [1,2,3,4,5]); y = Y.basis()
sage: uut = lambda i: sum(  y[j] for j in range(i+1,6)  ) # uni-upper
sage: phi = X.module_morphism(uut, triangular=True, codomain = Y,
....:      inverse_on_support=lambda i: i-1 if i in [2,3,4] else None)
sage: ~phi
Traceback (most recent call last):
...
ValueError: Non invertible morphism
sage: phiinv = phi.section()
sage: map(phiinv*phi, X.basis().list()) == X.basis().list()
True
sage: phiinv(Y.basis()[1])
Traceback (most recent call last):
...
ValueError: B[1] is not in the image

sage.categories.modules_with_basis.pointwise_inverse_function(f)

Return the function \(x \mapsto 1 / f(x)\).

INPUT:

• f – a function

EXAMPLES:

sage: from sage.categories.modules_with_basis import pointwise_inverse_function
sage: def f(x): return x
....:
sage: g = pointwise_inverse_function(f)
sage: g(1), g(2), g(3)
(1, 1/2, 1/3)

pointwise_inverse_function() is an involution:

sage: f is pointwise_inverse_function(g)
True

Todo

This has nothing to do here!!! Should there be a library for pointwise operations on functions somewhere in Sage?