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: 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)
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: 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]
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: M0.optimized()[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: 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)
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: 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
Similarly, we construct \(V_1\) and \(W_1\), and the quotient \(M_1\), in a completely different 2-dimensional ambient space.
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)
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: 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)]
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: f(x)
(0)
sage: f(M0.0)
(3)
sage: f(V0.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: y = f.lift(3*M1.0)
sage: y # random
(0, 13)
sage: 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: 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)
We compute the image of \(f\).
sage: 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: 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)
AUTHOR:
William Stein, 2009
- sage.modules.fg_pid.fgp_module.FGP_Module(V, W, check=True)#
INPUT:
V
– a free \(R\)-moduleW
– a free \(R\)-submodule of \(V\)check
– bool (default:True
); ifTrue
, more checks on correctness are performed; in particular, we check the data types ofV
andW
, 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: 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
- class sage.modules.fg_pid.fgp_module.FGP_Module_class(V, W, check=True)#
Bases:
Module
A finitely generated module over a PID presented as a quotient \(V/W\).
INPUT:
V
– an \(R\)-moduleW
– an \(R\)-submodule of \(V\)check
– bool (default:True
)
EXAMPLES:
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'>
- Element#
alias of
FGP_Element
- V()#
If this module was constructed as a quotient V/W, return V.
EXAMPLES:
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]
- W()#
If this module was constructed as a quotient \(V/W\), return \(W\).
EXAMPLES:
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]
- annihilator()#
Return the ideal of the base ring that annihilates
self
. This is precisely the ideal generated by the LCM of the invariants ofself
ifself
is finite, and is 0 otherwise.EXAMPLES:
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
We check that github issue #22720 is resolved:
sage: H = AdditiveAbelianGroup([]) sage: H.annihilator() Principal ideal (1) of Integer Ring
- base_ring()#
Return the base ring of
self
.EXAMPLES:
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
- cardinality()#
Return the cardinality of this module as a set.
EXAMPLES:
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
- construction()#
The construction functor and ambient module for
self
.EXAMPLES:
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])
- coordinate_vector(x, reduce=False)#
Return coordinates of
x
with respect to the optimized representation ofself
.INPUT:
x
– element ofself
reduce
– (default: False); ifTrue
, reduce coefficients modulo invariants; this is ignored if the base ring is notZZ
.
OUTPUT:
The coordinates as a vector. That is, the same type as
self.V()
, but in general with fewer entries.EXAMPLES:
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)
If x is not in self, it is coerced in:
sage: Q.coordinate_vector(V.0) (1, -3, 0) sage: Q.coordinate_vector(Q(V.0)) (1, -3, 0)
- cover()#
If this module was constructed as \(V/W\), return the cover module \(V\).
This is the same as
self.V()
.EXAMPLES:
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]
- gen(i)#
Return the
i
-th generator ofself
.INPUT:
i
– integer
EXAMPLES:
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
- gens()#
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 ofself
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: 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)
- gens_to_smith()#
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: L2 = IntegralLattice(3 * matrix([[-2,0,0], [0,1,0], [0,0,-4]])) sage: D = L2.discriminant_group().normal_form(); D # optional - 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() # optional - 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 # optional - 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: for i in range(T.nrows()): # optional - sage.libs.pari sage.rings.padics ....: T[:,i] = T[:,i] % D.gens()[i].order() sage: T # optional - 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)#
Return coordinates of
x
with respect to the generators.INPUT:
x
– element ofself
reduce
– (default:False
); ifTrue
, reduce coefficients modulo invariants; this is ignored if the base ring is not \(\ZZ\)
EXAMPLES:
We create a derived class and overwrite
gens()
: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))
We create some element of
D
:sage: x = D.linear_combination_of_smith_form_gens((1,2,3)); x (1, 2, 3)
In our generators:
sage: v = D.gens_vector(x); v (2, 9, 3, 1, 33)
The output can be further reduced:
sage: D.gens_vector(x, reduce=True) (0, 1, 0, 1, 0)
Let us check:
sage: x == sum(v[i]*D.gen(i) for i in range(len(D.gens()))) True
- has_canonical_map_to(A)#
Return
True
ifself
has a canonical map toA
, relative to the given presentation ofA
.This means that
A
is a finitely generated quotient module,self.V()
is a submodule ofA.V()
andself.W()
is a submodule ofA.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 useis_submodule()
.EXAMPLES:
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
- hom(im_gens, codomain=None, check=True)#
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
– a list of the images ofself.gens()
in some \(R\)-module
EXAMPLES:
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
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: 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
Constructing two zero maps from the zero module:
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
A degenerate case:
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)) ()
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: 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()
- invariants(include_ones=False)#
Return the diagonal entries of the Smith form of the relative matrix that defines
self
(see_relative_matrix()
) padded with zeros, excluding 1’s by default. Thus ifv
is the list of integers returned, then self is abstractly isomorphic to the product of cyclic groups \(\ZZ/n\ZZ\) where \(n\) is inv
.INPUT:
include_ones
– bool (default:False
); ifTrue
, also include 1’s in the output list.
EXAMPLES:
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)
An example with 1 and 0 rows:
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)
- is_finite()#
Return
True
ifself
is finite andFalse
otherwise.EXAMPLES:
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
- is_submodule(A)#
Return
True
ifself
is a submodule ofA
.More precisely, this returns
True
ifself.V()
is a submodule ofA.V()
, withself.W()
equal toA.W()
.Compare
has_canonical_map_to()
.EXAMPLES:
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
This example illustrates that this command works in a subtle cases.:
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
- linear_combination_of_smith_form_gens(x)#
Compute a linear combination of the optimised generators of this module as returned by
smith_form_gens()
.EXAMPLES:
sage: X = ZZ**2 / span([[3,0], [0,2]], ZZ) sage: X.linear_combination_of_smith_form_gens([1]) (1)
- list()#
Return a list of the elements of
self
.EXAMPLES:
sage: V = ZZ^2; W = V.span([[1,2],[3,4]]) sage: list(V/W) [(0), (1)]
- ngens()#
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 bysmith_form_gens()
; these are the same in theFGP_Module_class
, but not necessarily in derived classes.)EXAMPLES:
sage: A = (ZZ**2) / span([[4,0], [0,3]], ZZ) sage: A.ngens() 1
This works (but please do not do it in production code!)
sage: A.gens = lambda: [1,2,"Barcelona!"] sage: A.ngens() 3
- optimized()#
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 fromself
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 isomorphismZ
– matrix such that if \(x\) is inself.V()
andc
gives the coordinates of \(x\) in terms of the basis forself.V()
, thenc*Z
is in \(V_0\) andc*Z
maps to \(x\) via \(\phi\) above.
EXAMPLES:
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
- quotient_map()#
Given this quotient space \(Q = V / W\), return the natural quotient map from \(V\) to \(Q\).
EXAMPLES:
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)
- random_element(*args, **kwds)#
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: 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())
- relations()#
If
self
was constructed as \(V / W\), return the relations module \(W\).This is the same as
self.W()
.EXAMPLES:
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]
- smith_form_gen(i)#
Return the
i
-th generator ofself
.This is a separate method so we can freely override
gen()
in derived classes.INPUT:
i
– integer
EXAMPLES:
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)
- smith_form_gens()#
Return a set of generators for
self
which are in Smith normal form.EXAMPLES:
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)]
- smith_to_gens()#
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: L2 = IntegralLattice(3 * matrix([[-2,0,0], [0,1,0], [0,0,-4]])) sage: D = L2.discriminant_group().normal_form(); D # optional - 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() # optional - 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 # optional - sage.libs.pari sage.rings.padics [ 1 6 0] [ 0 7 0] [ 0 0 37]
This matrix satisfies the congruence:
sage: for i in range(T.ncols()): # optional - sage.libs.pari sage.rings.padics ....: T[:, i] = T[:, i] % D.smith_form_gens()[i].order() sage: T # optional - sage.libs.pari sage.rings.padics [1 0 0] [0 1 0] [0 0 1]
We create some element of our FGP module:
sage: x = D.linear_combination_of_smith_form_gens((1,2,3)); x # optional - 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: x.vector() * D.smith_to_gens() # optional - sage.libs.pari sage.rings.padics (2, 33, 3, 1, 3)
- submodule(x)#
Return the submodule defined by
x
.INPUT:
x
– list, tuple, or FGP module
EXAMPLES:
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))
We create submodules generated by a list or tuple of elements:
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)
A submodule defined by a submodule:
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)
Inclusion is checked:
sage: 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)#
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: 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) False sage: 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)#
Return a random FGP module inside a rank n free module over R.
INPUT:
n
– nonnegative integerR
– base ring (default:ZZ
)finite
– bool (default:True
); if True, make the random module finite
EXAMPLES:
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 (...)
In most cases the cardinality is small or infinite:
sage: for g in (1, 2, 3, +Infinity): ....: while fgp.random_fgp_module(4).cardinality() != 1: ....: pass
One can force a finite module:
sage: fgp.random_fgp_module(4, finite=True).is_finite() True
Larger finite modules appear:
sage: while fgp.random_fgp_module(4, finite=True).cardinality() < 100: ....: pass
- sage.modules.fg_pid.fgp_module.random_fgp_morphism_0(*args, **kwds)#
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: import sage.modules.fg_pid.fgp_module as fgp sage: mor = fgp.random_fgp_morphism_0(4) sage: mor.domain() == mor.codomain() True sage: fgp.is_FGP_Module(mor.domain()) True
Each generator is sent to a random multiple of itself:
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