Finitely generated modules over a PID¶

You can use Sage to compute with finitely generated modules (FGM’s) over a principal ideal domain \(R\) presented as a quotient \(V / W\), where \(V\) and \(W\) are free.

Note

Currently this is only enabled over R=ZZ, since it has not been tested and debugged over more general PIDs. All algorithms make sense whenever there is a Hermite form implementation. In theory the obstruction to extending the implementation is only that one has to decide how elements print.

We represent \(M = V / W\) as a pair \((V, W)\) with \(W\) contained in \(V\), and we internally represent elements of \(M\) non-canonically as elements \(x\) of \(V\). We also fix independent generators g[i] for \(M\) in \(V\), and when we print out elements of \(V\) we print their coordinates with respect to the g[i]; over \(\ZZ\) this is canonical, since each coefficient is reduced modulo the additive order of g[i]. To obtain the vector in \(V\) corresponding to \(x\) in \(M\), use x.lift().

Morphisms between finitely generated \(R\)-modules are well supported. You create a homomorphism by simply giving the images of generators of \(M_0\) in \(M_1\). Given a morphism \(\phi: M_0 \to M_1\), you can compute the image of \(\phi\), the kernel of \(\phi\), and using y = phi.lift(x) you can lift an element \(x\) in \(M_1\) to an element \(y\) in \(M_0\), if such a \(y\) exists.

TECHNICAL NOTE: For efficiency, we introduce a notion of optimized representation for quotient modules. The optimized representation of \(M=V/W\) is the quotient \(V'/W'\) where \(V'\) has as basis lifts of the generators g[i] for \(M\). We internally store a morphism from \(M_0=V_0/W_0\) to \(M_1=V_1/W_1\) by giving a morphism from the optimized representation \(V_0'\) of \(M_0\) to \(V_1\) that sends \(W_0\) into \(W_1\).

The following TUTORIAL illustrates several of the above points.

First we create free modules \(V_0\) and \(W_0\) and the quotient module \(M_0\). Notice that everything works fine even though \(V_0\) and \(W_0\) are not contained inside \(\ZZ^n\), which is extremely convenient.

Sage

sage: V0 = span([[1/2,0,0], [3/2,2,1], [0,0,1]], ZZ)
sage: W0 = V0.span([V0.0 + 2*V0.1, 9*V0.0 + 2*V0.1, 4*V0.2])
sage: M0 = V0/W0; M0
Finitely generated module V/W over Integer Ring with invariants (4, 16)

Python

>>> from sage.all import *
>>> V0 = span([[Integer(1)/Integer(2),Integer(0),Integer(0)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W0 = V0.span([V0.gen(0) + Integer(2)*V0.gen(1), Integer(9)*V0.gen(0) + Integer(2)*V0.gen(1), Integer(4)*V0.gen(2)])
>>> M0 = V0/W0; M0
Finitely generated module V/W over Integer Ring with invariants (4, 16)

The invariants are computed using the Smith normal form algorithm, and determine the structure of this finitely generated module.

You can get the \(V\) and \(W\) used in constructing the quotient module using the methods V() and W():

Sage

sage: M0.V()
Free module of degree 3 and rank 3 over Integer Ring
Echelon basis matrix:
[1/2   0   0]
[  0   2   0]
[  0   0   1]
sage: M0.W()
Free module of degree 3 and rank 3 over Integer Ring
Echelon basis matrix:
[1/2   4   0]
[  0  32   0]
[  0   0   4]

Python

>>> from sage.all import *
>>> M0.V()
Free module of degree 3 and rank 3 over Integer Ring
Echelon basis matrix:
[1/2   0   0]
[  0   2   0]
[  0   0   1]
>>> M0.W()
Free module of degree 3 and rank 3 over Integer Ring
Echelon basis matrix:
[1/2   4   0]
[  0  32   0]
[  0   0   4]

We note that the optimized representation of \(M_0\), mentioned above in the technical note, has a \(V\) that need not be equal to \(V_0\), in general.

Sage

sage: M0.optimized()[0].V()
Free module of degree 3 and rank 2 over Integer Ring
User basis matrix:
[ 0  8  1]
[ 0 -2  0]

Python

>>> from sage.all import *
>>> M0.optimized()[Integer(0)].V()
Free module of degree 3 and rank 2 over Integer Ring
User basis matrix:
[ 0  8  1]
[ 0 -2  0]

Create elements of \(M_0\) either by coercing in elements of \(V_0\), getting generators, or coercing in a list or tuple or coercing in 0. Finally, one can express an element as a linear combination of the Smith form generators

Sage

sage: M0(V0.0)
(0, 2)
sage: M0(V0.0 + W0.0)  # no difference modulo W0
(0, 2)
sage: M0.linear_combination_of_smith_form_gens([3,20])
(3, 4)
sage: 3*M0.0 + 20*M0.1
(3, 4)

Python

>>> from sage.all import *
>>> M0(V0.gen(0))
(0, 2)
>>> M0(V0.gen(0) + W0.gen(0))  # no difference modulo W0
(0, 2)
>>> M0.linear_combination_of_smith_form_gens([Integer(3),Integer(20)])
(3, 4)
>>> Integer(3)*M0.gen(0) + Integer(20)*M0.gen(1)
(3, 4)

We make an element of \(M_0\) by taking a difference of two generators, and lift it. We also illustrate making an element from a list, which coerces to \(V_0\), then take the equivalence class modulo \(W_0\).

Sage

sage: x = M0.0 - M0.1; x
(1, 15)
sage: x.lift()
(0, 10, 1)
sage: M0(vector([1/2,0,0]))
(0, 2)
sage: x.additive_order()
16

Python

>>> from sage.all import *
>>> x = M0.gen(0) - M0.gen(1); x
(1, 15)
>>> x.lift()
(0, 10, 1)
>>> M0(vector([Integer(1)/Integer(2),Integer(0),Integer(0)]))
(0, 2)
>>> x.additive_order()
16

Similarly, we construct \(V_1\) and \(W_1\), and the quotient \(M_1\), in a completely different 2-dimensional ambient space.

Sage

sage: V1 = span([[1/2,0], [3/2,2]], ZZ); W1 = V1.span([2*V1.0, 3*V1.1])
sage: M1 = V1/W1; M1
Finitely generated module V/W over Integer Ring with invariants (6)

Python

>>> from sage.all import *
>>> V1 = span([[Integer(1)/Integer(2),Integer(0)], [Integer(3)/Integer(2),Integer(2)]], ZZ); W1 = V1.span([Integer(2)*V1.gen(0), Integer(3)*V1.gen(1)])
>>> M1 = V1/W1; M1
Finitely generated module V/W over Integer Ring with invariants (6)

We create the homomorphism from \(M_0\) to \(M_1\) that sends both generators of \(M_0\) to 3 times the generator of \(M_1\). This is well-defined since 3 times the generator has order 2.

Sage

sage: f = M0.hom([3*M1.0, 3*M1.0]); f
Morphism from module over Integer Ring with invariants (4, 16)
 to module with invariants (6,) that sends the generators to [(3), (3)]

Python

>>> from sage.all import *
>>> f = M0.hom([Integer(3)*M1.gen(0), Integer(3)*M1.gen(0)]); f
Morphism from module over Integer Ring with invariants (4, 16)
 to module with invariants (6,) that sends the generators to [(3), (3)]

We evaluate the homomorphism on our element \(x\) of the domain, and on the first generator of the domain. We also evaluate at an element of \(V_0\), which is coerced into \(M_0\).

Sage

sage: f(x)
(0)
sage: f(M0.0)
(3)
sage: f(V0.1)
(3)

Python

>>> from sage.all import *
>>> f(x)
(0)
>>> f(M0.gen(0))
(3)
>>> f(V0.gen(1))
(3)

Here we illustrate lifting an element of the image of \(f\), i.e., finding an element of \(M_0\) that maps to a given element of \(M_1\):

Sage

sage: y = f.lift(3*M1.0)
sage: y # random
(0, 13)
sage: f(y)
(3)

Python

>>> from sage.all import *
>>> y = f.lift(Integer(3)*M1.gen(0))
>>> y # random
(0, 13)
>>> f(y)
(3)

We compute the kernel of \(f\), i.e., the submodule of elements of \(M_0\) that map to 0. Note that the kernel is not explicitly represented as a submodule, but as another quotient \(V/W\) where \(V\) is contained in \(V_0\). You can explicitly coerce elements of the kernel into \(M_0\) though.

Sage

sage: K = f.kernel(); K
Finitely generated module V/W over Integer Ring with invariants (2, 16)

sage: M0(K.0)
(2, 8)
sage: M0(K.1)
(1, 5)
sage: f(M0(K.0))
(0)
sage: f(M0(K.1))
(0)

Python

>>> from sage.all import *
>>> K = f.kernel(); K
Finitely generated module V/W over Integer Ring with invariants (2, 16)

>>> M0(K.gen(0))
(2, 8)
>>> M0(K.gen(1))
(1, 5)
>>> f(M0(K.gen(0)))
(0)
>>> f(M0(K.gen(1)))
(0)

We compute the image of \(f\).

Sage

sage: f.image()
Finitely generated module V/W over Integer Ring with invariants (2)

Python

>>> from sage.all import *
>>> f.image()
Finitely generated module V/W over Integer Ring with invariants (2)

Notice how the elements of the image are written as (0) and (1), despite the image being naturally a submodule of \(M_1\), which has elements (0), (1), (2), (3), (4), (5). However, below we coerce the element (1) of the image into the codomain, and get (3):

Sage

sage: list(f.image())
[(0), (1)]
sage: list(M1)
[(0), (1), (2), (3), (4), (5)]
sage: x = f.image().0; x
(1)
sage: M1(x)
(3)

Python

>>> from sage.all import *
>>> list(f.image())
[(0), (1)]
>>> list(M1)
[(0), (1), (2), (3), (4), (5)]
>>> x = f.image().gen(0); x
(1)
>>> M1(x)
(3)

AUTHOR:

William Stein, 2009

sage.modules.fg_pid.fgp_module.FGP_Module(V, W, check=True)[source]¶

INPUT:

V – a free \(R\)-module
W – a free \(R\)-submodule of \(V\)
check – boolean (default: True); if True, more checks on correctness are performed. In particular, we check the data types of V and W, and that \(W\) is a submodule of \(V\) with the same base ring.

OUTPUT: the quotient \(V/W\) as a finitely generated \(R\)-module

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: import sage.modules.fg_pid.fgp_module
sage: Q = sage.modules.fg_pid.fgp_module.FGP_Module(V, W)
sage: type(Q)
<class 'sage.modules.fg_pid.fgp_module.FGP_Module_class_with_category'>
sage: Q is sage.modules.fg_pid.fgp_module.FGP_Module(V, W, check=False)
True

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> import sage.modules.fg_pid.fgp_module
>>> Q = sage.modules.fg_pid.fgp_module.FGP_Module(V, W)
>>> type(Q)
<class 'sage.modules.fg_pid.fgp_module.FGP_Module_class_with_category'>
>>> Q is sage.modules.fg_pid.fgp_module.FGP_Module(V, W, check=False)
True

class sage.modules.fg_pid.fgp_module.FGP_Module_class(V, W, check=True)[source]¶

Bases: Module

A finitely generated module over a PID presented as a quotient \(V/W\).

INPUT:

V – an \(R\)-module
W – an \(R\)-submodule of \(V\)
check – boolean (default: True)

EXAMPLES:

Sage

sage: A = (ZZ^1)/span([[100]], ZZ); A
Finitely generated module V/W over Integer Ring with invariants (100)
sage: A.V()
Ambient free module of rank 1 over the principal ideal domain Integer Ring
sage: A.W()
Free module of degree 1 and rank 1 over Integer Ring
Echelon basis matrix:
[100]

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (4, 12)
sage: type(Q)
<class 'sage.modules.fg_pid.fgp_module.FGP_Module_class_with_category'>

Python

>>> from sage.all import *
>>> A = (ZZ**Integer(1))/span([[Integer(100)]], ZZ); A
Finitely generated module V/W over Integer Ring with invariants (100)
>>> A.V()
Ambient free module of rank 1 over the principal ideal domain Integer Ring
>>> A.W()
Free module of degree 1 and rank 1 over Integer Ring
Echelon basis matrix:
[100]

>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (4, 12)
>>> type(Q)
<class 'sage.modules.fg_pid.fgp_module.FGP_Module_class_with_category'>

Element[source]¶: alias of FGP_Element

V()[source]¶

If this module was constructed as a quotient V/W, return V.

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W
sage: Q.V()
Free module of degree 3 and rank 3 over Integer Ring
Echelon basis matrix:
[1/2   0   0]
[  0   1   0]
[  0   0   1]

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W
>>> Q.V()
Free module of degree 3 and rank 3 over Integer Ring
Echelon basis matrix:
[1/2   0   0]
[  0   1   0]
[  0   0   1]

W()[source]¶

If this module was constructed as a quotient \(V/W\), return \(W\).

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W
sage: Q.W()
Free module of degree 3 and rank 3 over Integer Ring
Echelon basis matrix:
[1/2   8   0]
[  0  12   0]
[  0   0   4]

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W
>>> Q.W()
Free module of degree 3 and rank 3 over Integer Ring
Echelon basis matrix:
[1/2   8   0]
[  0  12   0]
[  0   0   4]

annihilator()[source]¶

Return the ideal of the base ring that annihilates self. This is precisely the ideal generated by the LCM of the invariants of self if self is finite, and is 0 otherwise.

EXAMPLES:

Sage

sage: V = span([[1/2,0,0], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([V.0 + 2*V.1, 9*V.0 + 2*V.1, 4*V.2])
sage: Q = V/W; Q.annihilator()
Principal ideal (16) of Integer Ring
sage: Q.annihilator().gen()
16

sage: Q = V / V.span([V.0]); Q
Finitely generated module V/W over Integer Ring with invariants (0, 0)
sage: Q.annihilator()
Principal ideal (0) of Integer Ring

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(0),Integer(0)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([V.gen(0) + Integer(2)*V.gen(1), Integer(9)*V.gen(0) + Integer(2)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W; Q.annihilator()
Principal ideal (16) of Integer Ring
>>> Q.annihilator().gen()
16

>>> Q = V / V.span([V.gen(0)]); Q
Finitely generated module V/W over Integer Ring with invariants (0, 0)
>>> Q.annihilator()
Principal ideal (0) of Integer Ring

We check that Issue #22720 is resolved:

Sage

sage: H = AdditiveAbelianGroup([])
sage: H.annihilator()
Principal ideal (1) of Integer Ring

Python

>>> from sage.all import *
>>> H = AdditiveAbelianGroup([])
>>> H.annihilator()
Principal ideal (1) of Integer Ring

base_ring()[source]¶

Return the base ring of self.

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W
sage: Q.base_ring()
Integer Ring

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W
>>> Q.base_ring()
Integer Ring

cardinality()[source]¶

Return the cardinality of this module as a set.

EXAMPLES:

Sage

sage: V = ZZ^2; W = V.span([[1,2], [3,4]]); A = V/W; A
Finitely generated module V/W over Integer Ring with invariants (2)
sage: A.cardinality()
2
sage: V = ZZ^2; W = V.span([[1,2]]); A = V/W; A
Finitely generated module V/W over Integer Ring with invariants (0)
sage: A.cardinality()
+Infinity
sage: V = QQ^2; W = V.span([[1,2]]); A = V/W; A
Vector space quotient V/W of dimension 1 over Rational Field where
  V: Vector space of dimension 2 over Rational Field
  W: Vector space of degree 2 and dimension 1 over Rational Field
     Basis matrix:
     [1 2]
sage: A.cardinality()
+Infinity

Python

>>> from sage.all import *
>>> V = ZZ**Integer(2); W = V.span([[Integer(1),Integer(2)], [Integer(3),Integer(4)]]); A = V/W; A
Finitely generated module V/W over Integer Ring with invariants (2)
>>> A.cardinality()
2
>>> V = ZZ**Integer(2); W = V.span([[Integer(1),Integer(2)]]); A = V/W; A
Finitely generated module V/W over Integer Ring with invariants (0)
>>> A.cardinality()
+Infinity
>>> V = QQ**Integer(2); W = V.span([[Integer(1),Integer(2)]]); A = V/W; A
Vector space quotient V/W of dimension 1 over Rational Field where
  V: Vector space of dimension 2 over Rational Field
  W: Vector space of degree 2 and dimension 1 over Rational Field
     Basis matrix:
     [1 2]
>>> A.cardinality()
+Infinity

construction()[source]¶

The construction functor and ambient module for self.

EXAMPLES:

Sage

sage: W = ZZ^2
sage: A1 = W.submodule([[1,0]])
sage: B1 = W.submodule([[2,0]])
sage: T1 = A1 / B1
sage: T1.construction()
(QuotientModuleFunctor,
 Free module of degree 2 and rank 1 over Integer Ring
 Echelon basis matrix:
 [1 0])

Python

>>> from sage.all import *
>>> W = ZZ**Integer(2)
>>> A1 = W.submodule([[Integer(1),Integer(0)]])
>>> B1 = W.submodule([[Integer(2),Integer(0)]])
>>> T1 = A1 / B1
>>> T1.construction()
(QuotientModuleFunctor,
 Free module of degree 2 and rank 1 over Integer Ring
 Echelon basis matrix:
 [1 0])

coordinate_vector(x, reduce=False)[source]¶

Return coordinates of x with respect to the optimized representation of self.

INPUT:

x – element of self
reduce – (default: False) if True, reduce coefficients modulo invariants; this is ignored if the base ring is not ZZ

OUTPUT:

The coordinates as a vector. That is, the same type as self.V(), but in general with fewer entries.

EXAMPLES:

Sage

sage: V = span([[1/4,0,0], [3/4,4,2], [0,0,2]], ZZ)
sage: W = V.span([4*V.0 + 12*V.1])
sage: Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (4, 0, 0)
sage: Q.coordinate_vector(-Q.0)
(-1, 0, 0)
sage: Q.coordinate_vector(-Q.0, reduce=True)
(3, 0, 0)

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(4),Integer(0),Integer(0)], [Integer(3)/Integer(4),Integer(4),Integer(2)], [Integer(0),Integer(0),Integer(2)]], ZZ)
>>> W = V.span([Integer(4)*V.gen(0) + Integer(12)*V.gen(1)])
>>> Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (4, 0, 0)
>>> Q.coordinate_vector(-Q.gen(0))
(-1, 0, 0)
>>> Q.coordinate_vector(-Q.gen(0), reduce=True)
(3, 0, 0)

If x is not in self, it is coerced in:

Sage

sage: Q.coordinate_vector(V.0)
(1, -3, 0)
sage: Q.coordinate_vector(Q(V.0))
(1, -3, 0)

Python

>>> from sage.all import *
>>> Q.coordinate_vector(V.gen(0))
(1, -3, 0)
>>> Q.coordinate_vector(Q(V.gen(0)))
(1, -3, 0)

cover()[source]¶

If this module was constructed as \(V/W\), return the cover module \(V\).

This is the same as self.V().

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W
sage: Q.V()
Free module of degree 3 and rank 3 over Integer Ring
Echelon basis matrix:
[1/2   0   0]
[  0   1   0]
[  0   0   1]

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W
>>> Q.V()
Free module of degree 3 and rank 3 over Integer Ring
Echelon basis matrix:
[1/2   0   0]
[  0   1   0]
[  0   0   1]

gen(i)[source]¶

Return the i-th generator of self.

INPUT:

i – integer

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (4, 12)
sage: Q.gen(0)
(1, 0)
sage: Q.gen(1)
(0, 1)
sage: Q.gen(2)
Traceback (most recent call last):
...
ValueError: Generator 2 not defined
sage: Q.gen(-1)
Traceback (most recent call last):
...
ValueError: Generator -1 not defined

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (4, 12)
>>> Q.gen(Integer(0))
(1, 0)
>>> Q.gen(Integer(1))
(0, 1)
>>> Q.gen(Integer(2))
Traceback (most recent call last):
...
ValueError: Generator 2 not defined
>>> Q.gen(-Integer(1))
Traceback (most recent call last):
...
ValueError: Generator -1 not defined

gens()[source]¶

Return tuple of elements \(g_0,...,g_n\) of self such that the module generated by the \(g_i\) is isomorphic to the direct sum of \(R/e_i R\), where \(e_i\) are the invariants of self and \(R\) is the base ring.

Note that these are not generally uniquely determined, and depending on how Smith normal form is implemented for the base ring, they may not even be deterministic.

This can safely be overridden in all derived classes.

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W
sage: Q.gens()
((1, 0), (0, 1))
sage: Q.0
(1, 0)

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W
>>> Q.gens()
((1, 0), (0, 1))
>>> Q.gen(0)
(1, 0)

gens_to_smith()[source]¶

Return the transformation matrix from the user to Smith form generators.

To go in the other direction, use smith_to_gens().

OUTPUT: a matrix over the base ring

EXAMPLES:

Sage

sage: L2 = IntegralLattice(3 * matrix([[-2,0,0], [0,1,0], [0,0,-4]]))
sage: D = L2.discriminant_group().normal_form(); D                          # needs sage.libs.pari sage.rings.padics
Finite quadratic module over Integer Ring with invariants (3, 6, 12)
Gram matrix of the quadratic form with values in Q/Z:
[1/2   0   0   0   0]
[  0 1/4   0   0   0]
[  0   0 1/3   0   0]
[  0   0   0 1/3   0]
[  0   0   0   0 2/3]
sage: D.gens_to_smith()                                                     # needs sage.libs.pari sage.rings.padics
[0 3 0]
[0 0 3]
[0 4 0]
[1 2 0]
[0 0 4]
sage: T = D.gens_to_smith() * D.smith_to_gens(); T                          # needs sage.libs.pari sage.rings.padics
[ 3  0  3  0  0]
[ 0 33  0  0  3]
[ 4  0  4  0  0]
[ 2  0  3  1  0]
[ 0 44  0  0  4]

Python

>>> from sage.all import *
>>> L2 = IntegralLattice(Integer(3) * matrix([[-Integer(2),Integer(0),Integer(0)], [Integer(0),Integer(1),Integer(0)], [Integer(0),Integer(0),-Integer(4)]]))
>>> D = L2.discriminant_group().normal_form(); D                          # needs sage.libs.pari sage.rings.padics
Finite quadratic module over Integer Ring with invariants (3, 6, 12)
Gram matrix of the quadratic form with values in Q/Z:
[1/2   0   0   0   0]
[  0 1/4   0   0   0]
[  0   0 1/3   0   0]
[  0   0   0 1/3   0]
[  0   0   0   0 2/3]
>>> D.gens_to_smith()                                                     # needs sage.libs.pari sage.rings.padics
[0 3 0]
[0 0 3]
[0 4 0]
[1 2 0]
[0 0 4]
>>> T = D.gens_to_smith() * D.smith_to_gens(); T                          # needs sage.libs.pari sage.rings.padics
[ 3  0  3  0  0]
[ 0 33  0  0  3]
[ 4  0  4  0  0]
[ 2  0  3  1  0]
[ 0 44  0  0  4]

The matrix \(T\) now satisfies a certain congruence:

Sage

sage: for i in range(T.nrows()):                                            # needs sage.libs.pari sage.rings.padics
....:     T[:,i] = T[:,i] % D.gens()[i].order()
sage: T                                                                     # needs sage.libs.pari sage.rings.padics
[1 0 0 0 0]
[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]

Python

>>> from sage.all import *
>>> for i in range(T.nrows()):                                            # needs sage.libs.pari sage.rings.padics
...     T[:,i] = T[:,i] % D.gens()[i].order()
>>> T                                                                     # needs sage.libs.pari sage.rings.padics
[1 0 0 0 0]
[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]

gens_vector(x, reduce=False)[source]¶

Return coordinates of x with respect to the generators.

INPUT:

x – element of self
reduce – (default: False) if True, reduce coefficients modulo invariants; this is ignored if the base ring is not \(\ZZ\)

EXAMPLES:

We create a derived class and overwrite gens():

Sage

sage: from sage.modules.fg_pid.fgp_module import FGP_Module_class
sage: W = ZZ^3
sage: V = W.span(matrix.diagonal([1/6, 1/3, 1/12]))
sage: class FGP_with_gens(FGP_Module_class):
....:     def __init__(self, V, W, gens):
....:         FGP_Module_class.__init__(self, V, W)
....:         self._gens = tuple([self(g) for g in gens])
....:     def gens(self):
....:         return self._gens
sage: gens = [(1/2, 0, 0), (0, 0, 1/4), (1/3, 0, 0), (0, 1/3, 0), (0, 0, 2/3)]
sage: gens = [V(g) for g in gens]
sage: D = FGP_with_gens(V, W, gens)
sage: D.gens()
((0, 3, 0), (0, 0, 3), (0, 4, 0), (1, 2, 0), (0, 0, 8))

Python

>>> from sage.all import *
>>> from sage.modules.fg_pid.fgp_module import FGP_Module_class
>>> W = ZZ**Integer(3)
>>> V = W.span(matrix.diagonal([Integer(1)/Integer(6), Integer(1)/Integer(3), Integer(1)/Integer(12)]))
>>> class FGP_with_gens(FGP_Module_class):
...     def __init__(self, V, W, gens):
...         FGP_Module_class.__init__(self, V, W)
...         self._gens = tuple([self(g) for g in gens])
...     def gens(self):
...         return self._gens
>>> gens = [(Integer(1)/Integer(2), Integer(0), Integer(0)), (Integer(0), Integer(0), Integer(1)/Integer(4)), (Integer(1)/Integer(3), Integer(0), Integer(0)), (Integer(0), Integer(1)/Integer(3), Integer(0)), (Integer(0), Integer(0), Integer(2)/Integer(3))]
>>> gens = [V(g) for g in gens]
>>> D = FGP_with_gens(V, W, gens)
>>> D.gens()
((0, 3, 0), (0, 0, 3), (0, 4, 0), (1, 2, 0), (0, 0, 8))

We create some element of D:

Sage

sage: x = D.linear_combination_of_smith_form_gens((1,2,3)); x
(1, 2, 3)

Python

>>> from sage.all import *
>>> x = D.linear_combination_of_smith_form_gens((Integer(1),Integer(2),Integer(3))); x
(1, 2, 3)

In our generators:

Sage

sage: v = D.gens_vector(x); v                                               # needs sage.libs.pari
(2, 9, 3, 1, 33)

Python

>>> from sage.all import *
>>> v = D.gens_vector(x); v                                               # needs sage.libs.pari
(2, 9, 3, 1, 33)

The output can be further reduced:

Sage

sage: D.gens_vector(x, reduce=True)                                         # needs sage.libs.pari
(0, 1, 0, 1, 0)

Python

>>> from sage.all import *
>>> D.gens_vector(x, reduce=True)                                         # needs sage.libs.pari
(0, 1, 0, 1, 0)

Let us check:

Sage

sage: x == sum(v[i]*D.gen(i) for i in range(len(D.gens())))                 # needs sage.libs.pari
True

Python

>>> from sage.all import *
>>> x == sum(v[i]*D.gen(i) for i in range(len(D.gens())))                 # needs sage.libs.pari
True

has_canonical_map_to(A)[source]¶

Return True if self has a canonical map to A, relative to the given presentation of A.

This means that A is a finitely generated quotient module, self.V() is a submodule of A.V() and self.W() is a submodule of A.W(), i.e., that there is a natural map induced by inclusion of the V’s. Note that we do not require that this natural map be injective; for this use is_submodule().

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (4, 12)
sage: A = Q.submodule((Q.0, Q.0 + 3*Q.1)); A
Finitely generated module V/W over Integer Ring with invariants (4, 4)
sage: A.has_canonical_map_to(Q)
True
sage: Q.has_canonical_map_to(A)
False

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (4, 12)
>>> A = Q.submodule((Q.gen(0), Q.gen(0) + Integer(3)*Q.gen(1))); A
Finitely generated module V/W over Integer Ring with invariants (4, 4)
>>> A.has_canonical_map_to(Q)
True
>>> Q.has_canonical_map_to(A)
False

hom(im_gens, codomain=None, check=True)[source]¶

Homomorphism defined by giving the images of self.gens() in some fixed finitely generated \(R\)-module.

Note

We do not assume that the generators given by self.gens() are the same as the Smith form generators, since this may not be true for a general derived class.

INPUT:

im_gens – list of the images of self.gens() in some \(R\)-module

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W
sage: phi = Q.hom([3*Q.1, Q.0])
sage: phi
Morphism from module over Integer Ring with invariants (4, 12)
           to module with invariants (4, 12)
  that sends the generators to [(0, 3), (1, 0)]
sage: phi(Q.0)
(0, 3)
sage: phi(Q.1)
(1, 0)
sage: Q.0 == phi(Q.1)
True

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W
>>> phi = Q.hom([Integer(3)*Q.gen(1), Q.gen(0)])
>>> phi
Morphism from module over Integer Ring with invariants (4, 12)
           to module with invariants (4, 12)
  that sends the generators to [(0, 3), (1, 0)]
>>> phi(Q.gen(0))
(0, 3)
>>> phi(Q.gen(1))
(1, 0)
>>> Q.gen(0) == phi(Q.gen(1))
True

This example illustrates creating a morphism to a free module. The free module is turned into an FGP module (i.e., quotient \(V/W\) with \(W=0\)), and the morphism is constructed:

Sage

sage: V = span([[1/2,0,0], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1])
sage: Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (2, 0, 0)
sage: phi = Q.hom([0, V.0, V.1]); phi
Morphism from module over Integer Ring with invariants (2, 0, 0)
           to module with invariants (0, 0, 0)
  that sends the generators to [(0, 0, 0), (1, 0, 0), (0, 1, 0)]
sage: phi.domain()
Finitely generated module V/W over Integer Ring with invariants (2, 0, 0)
sage: phi.codomain()
Finitely generated module V/W over Integer Ring with invariants (0, 0, 0)
sage: phi(Q.0)
(0, 0, 0)
sage: phi(Q.1)
(1, 0, 0)
sage: phi(Q.2) == V.1
True

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(0),Integer(0)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1)])
>>> Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (2, 0, 0)
>>> phi = Q.hom([Integer(0), V.gen(0), V.gen(1)]); phi
Morphism from module over Integer Ring with invariants (2, 0, 0)
           to module with invariants (0, 0, 0)
  that sends the generators to [(0, 0, 0), (1, 0, 0), (0, 1, 0)]
>>> phi.domain()
Finitely generated module V/W over Integer Ring with invariants (2, 0, 0)
>>> phi.codomain()
Finitely generated module V/W over Integer Ring with invariants (0, 0, 0)
>>> phi(Q.gen(0))
(0, 0, 0)
>>> phi(Q.gen(1))
(1, 0, 0)
>>> phi(Q.gen(2)) == V.gen(1)
True

Constructing two zero maps from the zero module:

Sage

sage: A = (ZZ^2)/(ZZ^2); A
Finitely generated module V/W over Integer Ring with invariants ()
sage: A.hom([])
Morphism from module over Integer Ring with invariants ()
           to module with invariants ()
  that sends the generators to []
sage: A.hom([]).codomain() is A
True
sage: B = (ZZ^3)/(ZZ^3)
sage: phi = A.hom([], codomain=B); phi
Morphism from module over Integer Ring with invariants ()
           to module with invariants ()
  that sends the generators to []
sage: phi(A(0))
()
sage: phi(A(0)) == B(0)
True

Python

>>> from sage.all import *
>>> A = (ZZ**Integer(2))/(ZZ**Integer(2)); A
Finitely generated module V/W over Integer Ring with invariants ()
>>> A.hom([])
Morphism from module over Integer Ring with invariants ()
           to module with invariants ()
  that sends the generators to []
>>> A.hom([]).codomain() is A
True
>>> B = (ZZ**Integer(3))/(ZZ**Integer(3))
>>> phi = A.hom([], codomain=B); phi
Morphism from module over Integer Ring with invariants ()
           to module with invariants ()
  that sends the generators to []
>>> phi(A(Integer(0)))
()
>>> phi(A(Integer(0))) == B(Integer(0))
True

A degenerate case:

Sage

sage: A = (ZZ^2)/(ZZ^2)
sage: phi = A.hom([]); phi
Morphism from module over Integer Ring with invariants ()
           to module with invariants ()
  that sends the generators to []
sage: phi(A(0))
()

Python

>>> from sage.all import *
>>> A = (ZZ**Integer(2))/(ZZ**Integer(2))
>>> phi = A.hom([]); phi
Morphism from module over Integer Ring with invariants ()
           to module with invariants ()
  that sends the generators to []
>>> phi(A(Integer(0)))
()

The code checks that the morphism is valid. In the example below we try to send a generator of order 2 to an element of order 14:

Sage

sage: V = span([[1/14,3/14], [0,1/2]], ZZ); W = ZZ^2
sage: Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (2, 14)
sage: Q.linear_combination_of_smith_form_gens([1,11]).additive_order()
14
sage: f = Q.hom([Q.linear_combination_of_smith_form_gens([1,11]),
....:            Q.linear_combination_of_smith_form_gens([1,3])]); f
Traceback (most recent call last):
...
ValueError: phi must send optimized submodule of M.W() into N.W()

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(14),Integer(3)/Integer(14)], [Integer(0),Integer(1)/Integer(2)]], ZZ); W = ZZ**Integer(2)
>>> Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (2, 14)
>>> Q.linear_combination_of_smith_form_gens([Integer(1),Integer(11)]).additive_order()
14
>>> f = Q.hom([Q.linear_combination_of_smith_form_gens([Integer(1),Integer(11)]),
...            Q.linear_combination_of_smith_form_gens([Integer(1),Integer(3)])]); f
Traceback (most recent call last):
...
ValueError: phi must send optimized submodule of M.W() into N.W()

invariants(include_ones=False)[source]¶

Return the diagonal entries of the Smith form of the relative matrix that defines self (see _relative_matrix()) padded with zeros, excluding 1s by default. Thus if v is the list of integers returned, then self is abstractly isomorphic to the product of cyclic groups \(\ZZ/n\ZZ\) where \(n\) is in v.

INPUT:

include_ones – boolean (default: False); if True, also include 1s in the output list

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W
sage: Q.invariants()
(4, 12)

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W
>>> Q.invariants()
(4, 12)

An example with 1 and 0 rows:

Sage

sage: V = ZZ^3; W = V.span([[1,2,0], [0,1,0], [0,2,0]]); Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (0)
sage: Q.invariants()
(0,)
sage: Q.invariants(include_ones=True)
(1, 1, 0)

Python

>>> from sage.all import *
>>> V = ZZ**Integer(3); W = V.span([[Integer(1),Integer(2),Integer(0)], [Integer(0),Integer(1),Integer(0)], [Integer(0),Integer(2),Integer(0)]]); Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (0)
>>> Q.invariants()
(0,)
>>> Q.invariants(include_ones=True)
(1, 1, 0)

is_finite()[source]¶

Return True if self is finite and False otherwise.

EXAMPLES:

Sage

sage: V = span([[1/2,0,0], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([V.0 + 2*V.1, 9*V.0 + 2*V.1, 4*V.2])
sage: Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (4, 16)
sage: Q.is_finite()
True
sage: Q = V / V.zero_submodule(); Q
Finitely generated module V/W over Integer Ring with invariants (0, 0, 0)
sage: Q.is_finite()
False

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(0),Integer(0)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([V.gen(0) + Integer(2)*V.gen(1), Integer(9)*V.gen(0) + Integer(2)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (4, 16)
>>> Q.is_finite()
True
>>> Q = V / V.zero_submodule(); Q
Finitely generated module V/W over Integer Ring with invariants (0, 0, 0)
>>> Q.is_finite()
False

is_submodule(A)[source]¶

Return True if self is a submodule of A.

More precisely, this returns True if self.V() is a submodule of A.V(), with self.W() equal to A.W().

Compare has_canonical_map_to().

EXAMPLES:

Sage

sage: V = ZZ^2; W = V.span([[1,2]]); W2 = W.scale(2)
sage: A = V/W; B = W/W2
sage: B.is_submodule(A)
False
sage: A = V/W2; B = W/W2
sage: B.is_submodule(A)
True

Python

>>> from sage.all import *
>>> V = ZZ**Integer(2); W = V.span([[Integer(1),Integer(2)]]); W2 = W.scale(Integer(2))
>>> A = V/W; B = W/W2
>>> B.is_submodule(A)
False
>>> A = V/W2; B = W/W2
>>> B.is_submodule(A)
True

This example illustrates that this command works in a subtle cases.:

Sage

sage: A = ZZ^1
sage: Q3 = A / A.span([[3]])
sage: Q6 = A / A.span([[6]])
sage: Q6.is_submodule(Q3)
False
sage: Q6.has_canonical_map_to(Q3)
True
sage: Q = A.span([[2]]) / A.span([[6]])
sage: Q.is_submodule(Q6)
True

Python

>>> from sage.all import *
>>> A = ZZ**Integer(1)
>>> Q3 = A / A.span([[Integer(3)]])
>>> Q6 = A / A.span([[Integer(6)]])
>>> Q6.is_submodule(Q3)
False
>>> Q6.has_canonical_map_to(Q3)
True
>>> Q = A.span([[Integer(2)]]) / A.span([[Integer(6)]])
>>> Q.is_submodule(Q6)
True

linear_combination_of_smith_form_gens(x)[source]¶

Compute a linear combination of the optimised generators of this module as returned by smith_form_gens().

EXAMPLES:

Sage

sage: X = ZZ**2 / span([[3,0], [0,2]], ZZ)
sage: X.linear_combination_of_smith_form_gens([1])
(1)

Python

>>> from sage.all import *
>>> X = ZZ**Integer(2) / span([[Integer(3),Integer(0)], [Integer(0),Integer(2)]], ZZ)
>>> X.linear_combination_of_smith_form_gens([Integer(1)])
(1)

list()[source]¶

Return a list of the elements of self.

EXAMPLES:

Sage

sage: V = ZZ^2; W = V.span([[1,2],[3,4]])
sage: list(V/W)
[(0), (1)]

Python

>>> from sage.all import *
>>> V = ZZ**Integer(2); W = V.span([[Integer(1),Integer(2)],[Integer(3),Integer(4)]])
>>> list(V/W)
[(0), (1)]

ngens()[source]¶

Return the number of generators of self.

(Note for developers: This is just the length of gens(), rather than of the minimal set of generators as returned by smith_form_gens(); these are the same in the FGP_Module_class, but not necessarily in derived classes.)

EXAMPLES:

Sage

sage: A = (ZZ**2) / span([[4,0], [0,3]], ZZ)
sage: A.ngens()
1

Python

>>> from sage.all import *
>>> A = (ZZ**Integer(2)) / span([[Integer(4),Integer(0)], [Integer(0),Integer(3)]], ZZ)
>>> A.ngens()
1

This works (but please do not do it in production code!)

Sage

sage: A.gens = lambda: [1,2,"Barcelona!"]
sage: A.ngens()
3

Python

>>> from sage.all import *
>>> A.gens = lambda: [Integer(1),Integer(2),"Barcelona!"]
>>> A.ngens()
3

optimized()[source]¶

Return a module isomorphic to this one, but with \(V\) replaced by a submodule of \(V\) such that the generators of self all lift trivially to generators of \(V\). Replace \(W\) by the intersection of \(V\) and \(W\). This has the advantage that \(V\) has small dimension and any homomorphism from self trivially extends to a homomorphism from \(V\).

OUTPUT:

Q – an optimized quotient \(V_0/W_0\) with \(V_0\) a submodule of \(V\) such that \(\phi: V_0/W_0 \to V/W\) is an isomorphism
Z – matrix such that if \(x\) is in self.V() and c gives the coordinates of \(x\) in terms of the basis for self.V(), then c*Z is in \(V_0\) and c*Z maps to \(x\) via \(\phi\) above.

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W
sage: O, X = Q.optimized(); O
Finitely generated module V/W over Integer Ring with invariants (4, 12)
sage: O.V()
Free module of degree 3 and rank 2 over Integer Ring
User basis matrix:
[ 0  3  1]
[ 0 -1  0]
sage: O.W()
Free module of degree 3 and rank 2 over Integer Ring
Echelon basis matrix:
[ 0 12  0]
[ 0  0  4]
sage: X         # random
[0 4 0]
[0 1 0]
[0 0 1]
sage: OV = O.V()
sage: Q(OV([0,-8,0])) == V.0
True
sage: Q(OV([0,1,0])) == V.1
True
sage: Q(OV([0,0,1])) == V.2
True

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W
>>> O, X = Q.optimized(); O
Finitely generated module V/W over Integer Ring with invariants (4, 12)
>>> O.V()
Free module of degree 3 and rank 2 over Integer Ring
User basis matrix:
[ 0  3  1]
[ 0 -1  0]
>>> O.W()
Free module of degree 3 and rank 2 over Integer Ring
Echelon basis matrix:
[ 0 12  0]
[ 0  0  4]
>>> X         # random
[0 4 0]
[0 1 0]
[0 0 1]
>>> OV = O.V()
>>> Q(OV([Integer(0),-Integer(8),Integer(0)])) == V.gen(0)
True
>>> Q(OV([Integer(0),Integer(1),Integer(0)])) == V.gen(1)
True
>>> Q(OV([Integer(0),Integer(0),Integer(1)])) == V.gen(2)
True

quotient_map()[source]¶

Given this quotient space \(Q = V / W\), return the natural quotient map from \(V\) to \(Q\).

EXAMPLES:

Sage

sage: A = (ZZ**2) / span([[4,0],[0,3]], ZZ)
sage: A.quotient_map()
Coercion map:
  From: Ambient free module of rank 2 over the principal ideal domain Integer Ring
  To:   Finitely generated module V/W over Integer Ring with invariants (12)

Python

>>> from sage.all import *
>>> A = (ZZ**Integer(2)) / span([[Integer(4),Integer(0)],[Integer(0),Integer(3)]], ZZ)
>>> A.quotient_map()
Coercion map:
  From: Ambient free module of rank 2 over the principal ideal domain Integer Ring
  To:   Finitely generated module V/W over Integer Ring with invariants (12)

random_element(*args, **kwds)[source]¶

Create a random element of self = \(V/W\), by creating a random element of \(V\) and reducing it modulo \(W\).

All arguments are passed on to the method random_element() of \(V\).

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W
sage: Q.random_element().parent() is Q
True
sage: Q.cardinality()
48
sage: S = set()
sage: while len(S) < 48:
....:     S.add(Q.random_element())

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W
>>> Q.random_element().parent() is Q
True
>>> Q.cardinality()
48
>>> S = set()
>>> while len(S) < Integer(48):
...     S.add(Q.random_element())

relations()[source]¶

If self was constructed as \(V / W\), return the relations module \(W\).

This is the same as self.W().

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V / W
sage: Q.relations()
Free module of degree 3 and rank 3 over Integer Ring
Echelon basis matrix:
[1/2   8   0]
[  0  12   0]
[  0   0   4]

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V / W
>>> Q.relations()
Free module of degree 3 and rank 3 over Integer Ring
Echelon basis matrix:
[1/2   8   0]
[  0  12   0]
[  0   0   4]

smith_form_gen(i)[source]¶

Return the i-th generator of self.

This is a separate method so we can freely override gen() in derived classes.

INPUT:

i – integer

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (4, 12)
sage: Q.smith_form_gen(0)
(1, 0)
sage: Q.smith_form_gen(1)
(0, 1)

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (4, 12)
>>> Q.smith_form_gen(Integer(0))
(1, 0)
>>> Q.smith_form_gen(Integer(1))
(0, 1)

smith_form_gens()[source]¶

Return a set of generators for self which are in Smith normal form.

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W
sage: Q.smith_form_gens()
((1, 0), (0, 1))
sage: [x.lift() for x in Q.smith_form_gens()]
[(0, 3, 1), (0, -1, 0)]

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W
>>> Q.smith_form_gens()
((1, 0), (0, 1))
>>> [x.lift() for x in Q.smith_form_gens()]
[(0, 3, 1), (0, -1, 0)]

smith_to_gens()[source]¶

Return the transformation matrix from Smith form to user generators.

To go in the other direction, use gens_to_smith().

OUTPUT: a matrix over the base ring

EXAMPLES:

Sage

sage: L2 = IntegralLattice(3 * matrix([[-2,0,0], [0,1,0], [0,0,-4]]))
sage: D = L2.discriminant_group().normal_form(); D                          # needs sage.libs.pari sage.rings.padics
Finite quadratic module over Integer Ring with invariants (3, 6, 12)
Gram matrix of the quadratic form with values in Q/Z:
[1/2   0   0   0   0]
[  0 1/4   0   0   0]
[  0   0 1/3   0   0]
[  0   0   0 1/3   0]
[  0   0   0   0 2/3]
sage: D.smith_to_gens()                                                     # needs sage.libs.pari sage.rings.padics
[ 0  0  1  1  0]
[ 1  0  1  0  0]
[ 0 11  0  0  1]
sage: T = D.smith_to_gens() * D.gens_to_smith(); T                          # needs sage.libs.pari sage.rings.padics
[ 1  6  0]
[ 0  7  0]
[ 0  0 37]

Python

>>> from sage.all import *
>>> L2 = IntegralLattice(Integer(3) * matrix([[-Integer(2),Integer(0),Integer(0)], [Integer(0),Integer(1),Integer(0)], [Integer(0),Integer(0),-Integer(4)]]))
>>> D = L2.discriminant_group().normal_form(); D                          # needs sage.libs.pari sage.rings.padics
Finite quadratic module over Integer Ring with invariants (3, 6, 12)
Gram matrix of the quadratic form with values in Q/Z:
[1/2   0   0   0   0]
[  0 1/4   0   0   0]
[  0   0 1/3   0   0]
[  0   0   0 1/3   0]
[  0   0   0   0 2/3]
>>> D.smith_to_gens()                                                     # needs sage.libs.pari sage.rings.padics
[ 0  0  1  1  0]
[ 1  0  1  0  0]
[ 0 11  0  0  1]
>>> T = D.smith_to_gens() * D.gens_to_smith(); T                          # needs sage.libs.pari sage.rings.padics
[ 1  6  0]
[ 0  7  0]
[ 0  0 37]

This matrix satisfies the congruence:

Sage

sage: for i in range(T.ncols()):                                            # needs sage.libs.pari sage.rings.padics
....:     T[:, i] = T[:, i] % D.smith_form_gens()[i].order()
sage: T                                                                     # needs sage.libs.pari sage.rings.padics
[1 0 0]
[0 1 0]
[0 0 1]

Python

>>> from sage.all import *
>>> for i in range(T.ncols()):                                            # needs sage.libs.pari sage.rings.padics
...     T[:, i] = T[:, i] % D.smith_form_gens()[i].order()
>>> T                                                                     # needs sage.libs.pari sage.rings.padics
[1 0 0]
[0 1 0]
[0 0 1]

We create some element of our FGP module:

Sage

sage: x = D.linear_combination_of_smith_form_gens((1,2,3)); x               # needs sage.libs.pari sage.rings.padics
(1, 2, 3)

Python

>>> from sage.all import *
>>> x = D.linear_combination_of_smith_form_gens((Integer(1),Integer(2),Integer(3))); x               # needs sage.libs.pari sage.rings.padics
(1, 2, 3)

and want to know some (it is not unique) linear combination of the user defined generators that is x:

Sage

sage: x.vector() * D.smith_to_gens()                                        # needs sage.libs.pari sage.rings.padics
(2, 33, 3, 1, 3)

Python

>>> from sage.all import *
>>> x.vector() * D.smith_to_gens()                                        # needs sage.libs.pari sage.rings.padics
(2, 33, 3, 1, 3)

submodule(x)[source]¶

Return the submodule defined by x.

INPUT:

x – list, tuple, or FGP module

EXAMPLES:

Sage

sage: V = span([[1/2,1,1], [3/2,2,1], [0,0,1]], ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2])
sage: Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (4, 12)
sage: Q.gens()
((1, 0), (0, 1))

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)], [Integer(3)/Integer(2),Integer(2),Integer(1)], [Integer(0),Integer(0),Integer(1)]], ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)])
>>> Q = V/W; Q
Finitely generated module V/W over Integer Ring with invariants (4, 12)
>>> Q.gens()
((1, 0), (0, 1))

We create submodules generated by a list or tuple of elements:

Sage

sage: Q.submodule([Q.0])
Finitely generated module V/W over Integer Ring with invariants (4)
sage: Q.submodule([Q.1])
Finitely generated module V/W over Integer Ring with invariants (12)
sage: Q.submodule((Q.0, Q.0 + 3*Q.1))
Finitely generated module V/W over Integer Ring with invariants (4, 4)

Python

>>> from sage.all import *
>>> Q.submodule([Q.gen(0)])
Finitely generated module V/W over Integer Ring with invariants (4)
>>> Q.submodule([Q.gen(1)])
Finitely generated module V/W over Integer Ring with invariants (12)
>>> Q.submodule((Q.gen(0), Q.gen(0) + Integer(3)*Q.gen(1)))
Finitely generated module V/W over Integer Ring with invariants (4, 4)

A submodule defined by a submodule:

Sage

sage: A = Q.submodule((Q.0, Q.0 + 3*Q.1)); A
Finitely generated module V/W over Integer Ring with invariants (4, 4)
sage: Q.submodule(A)
Finitely generated module V/W over Integer Ring with invariants (4, 4)

Python

>>> from sage.all import *
>>> A = Q.submodule((Q.gen(0), Q.gen(0) + Integer(3)*Q.gen(1))); A
Finitely generated module V/W over Integer Ring with invariants (4, 4)
>>> Q.submodule(A)
Finitely generated module V/W over Integer Ring with invariants (4, 4)

Inclusion is checked:

Sage

sage: A.submodule(Q)
Traceback (most recent call last):
...
ValueError: x.V() must be contained in self's V.

Python

>>> from sage.all import *
>>> A.submodule(Q)
Traceback (most recent call last):
...
ValueError: x.V() must be contained in self's V.

sage.modules.fg_pid.fgp_module.is_FGP_Module(x)[source]¶

Return True if x is an FGP module, i.e., a finitely generated module over a PID represented as a quotient of finitely generated free modules over a PID.

EXAMPLES:

Sage

sage: V = span([[1/2,1,1],[3/2,2,1],[0,0,1]],ZZ)
sage: W = V.span([2*V.0 + 4*V.1, 9*V.0 + 12*V.1, 4*V.2]); Q = V/W
sage: sage.modules.fg_pid.fgp_module.is_FGP_Module(V)
doctest:warning...
DeprecationWarning: the function is_FGP_Module is deprecated;
use 'isinstance(..., FGP_Module_class)' instead
See https://github.com/sagemath/sage/issues/37924 for details.
False
sage: sage.modules.fg_pid.fgp_module.is_FGP_Module(Q)
True

Python

>>> from sage.all import *
>>> V = span([[Integer(1)/Integer(2),Integer(1),Integer(1)],[Integer(3)/Integer(2),Integer(2),Integer(1)],[Integer(0),Integer(0),Integer(1)]],ZZ)
>>> W = V.span([Integer(2)*V.gen(0) + Integer(4)*V.gen(1), Integer(9)*V.gen(0) + Integer(12)*V.gen(1), Integer(4)*V.gen(2)]); Q = V/W
>>> sage.modules.fg_pid.fgp_module.is_FGP_Module(V)
doctest:warning...
DeprecationWarning: the function is_FGP_Module is deprecated;
use 'isinstance(..., FGP_Module_class)' instead
See https://github.com/sagemath/sage/issues/37924 for details.
False
>>> sage.modules.fg_pid.fgp_module.is_FGP_Module(Q)
True

sage.modules.fg_pid.fgp_module.random_fgp_module(n, R=Integer Ring, finite=False)[source]¶

Return a random FGP module inside a rank n free module over R.

INPUT:

n – nonnegative integer
R – base ring (default: ZZ)
finite – boolean (default: True); if True, make the random module finite

EXAMPLES:

Sage

sage: import sage.modules.fg_pid.fgp_module as fgp
sage: fgp.random_fgp_module(4)
Finitely generated module V/W over Integer Ring with invariants (...)

Python

>>> from sage.all import *
>>> import sage.modules.fg_pid.fgp_module as fgp
>>> fgp.random_fgp_module(Integer(4))
Finitely generated module V/W over Integer Ring with invariants (...)

In most cases the cardinality is small or infinite:

Sage

sage: for g in (1, 2, 3, +Infinity):
....:     while fgp.random_fgp_module(4).cardinality() != 1:
....:         pass

Python

>>> from sage.all import *
>>> for g in (Integer(1), Integer(2), Integer(3), +Infinity):
...     while fgp.random_fgp_module(Integer(4)).cardinality() != Integer(1):
...         pass

One can force a finite module:

Sage

sage: fgp.random_fgp_module(4, finite=True).is_finite()
True

Python

>>> from sage.all import *
>>> fgp.random_fgp_module(Integer(4), finite=True).is_finite()
True

Larger finite modules appear:

Sage

sage: while fgp.random_fgp_module(4, finite=True).cardinality() < 100:
....:     pass

Python

>>> from sage.all import *
>>> while fgp.random_fgp_module(Integer(4), finite=True).cardinality() < Integer(100):
...     pass

sage.modules.fg_pid.fgp_module.random_fgp_morphism_0(*args, **kwds)[source]¶

Construct a random fgp module using random_fgp_module(), then construct a random morphism that sends each generator to a random multiple of itself.

Inputs are the same as to random_fgp_module().

EXAMPLES:

Sage

sage: import sage.modules.fg_pid.fgp_module as fgp
sage: mor = fgp.random_fgp_morphism_0(4)
sage: mor.domain() == mor.codomain()
True
sage: isinstance(mor.domain(), fgp.FGP_Module_class)
True

Python

>>> from sage.all import *
>>> import sage.modules.fg_pid.fgp_module as fgp
>>> mor = fgp.random_fgp_morphism_0(Integer(4))
>>> mor.domain() == mor.codomain()
True
>>> isinstance(mor.domain(), fgp.FGP_Module_class)
True

Each generator is sent to a random multiple of itself:

Sage

sage: gens = mor.domain().gens()
sage: im_gens = mor.im_gens()
sage: all(im_gens[i] == sum(im_gens[i])*gens[i] for i in range(len(gens)))
True

Python

>>> from sage.all import *
>>> gens = mor.domain().gens()
>>> im_gens = mor.im_gens()
>>> all(im_gens[i] == sum(im_gens[i])*gens[i] for i in range(len(gens)))
True