# Iterators over finite submodules of a $$\ZZ$$-module#

We iterate over the elements of a finite $$\ZZ$$-module. The action of $$\ZZ$$ must be the natural one.

This class is intended to provide optimizations for the sage.free_module.FreeModule_generic:__iter__() method.

AUTHORS:

• Thomas Feulner (2012-08-31): initial version

• Punarbasu Purkayastha (2012-11-09): replaced the loop with recursion

• Thomas Feulner (2012-11-09): added functionality to enumerate cosets, FiniteFieldsubspace_projPoint_iterator

EXAMPLES:

sage: from sage.modules.finite_submodule_iter import FiniteZZsubmodule_iterator
sage: F.<x,y,z> = FreeAlgebra(GF(3),3)
sage: iter = FiniteZZsubmodule_iterator([x,y], [3,3])
sage: list(iter)
[0, x, 2*x, y, x + y, 2*x + y, 2*y, x + 2*y, 2*x + 2*y]

>>> from sage.all import *
>>> from sage.modules.finite_submodule_iter import FiniteZZsubmodule_iterator
>>> F = FreeAlgebra(GF(Integer(3)),Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3)
>>> iter = FiniteZZsubmodule_iterator([x,y], [Integer(3),Integer(3)])
>>> list(iter)
[0, x, 2*x, y, x + y, 2*x + y, 2*y, x + 2*y, 2*x + 2*y]


There is a specialization for subspaces over finite fields:

sage: from sage.modules.finite_submodule_iter import FiniteFieldsubspace_iterator
sage: A = random_matrix(GF(4, 'a'), 5, 100)
sage: iter = FiniteFieldsubspace_iterator(A)
sage: len(list(iter))
1024

>>> from sage.all import *
>>> from sage.modules.finite_submodule_iter import FiniteFieldsubspace_iterator
>>> A = random_matrix(GF(Integer(4), 'a'), Integer(5), Integer(100))
>>> iter = FiniteFieldsubspace_iterator(A)
>>> len(list(iter))
1024


The module also allows the iteration over cosets:

sage: from sage.modules.finite_submodule_iter import FiniteFieldsubspace_iterator
sage: A = random_matrix(GF(4, 'a'), 5, 100)
sage: v = random_vector(GF(4, 'a'), 100)
sage: iter = FiniteFieldsubspace_iterator(A, v)
sage: len(list(iter))
1024

>>> from sage.all import *
>>> from sage.modules.finite_submodule_iter import FiniteFieldsubspace_iterator
>>> A = random_matrix(GF(Integer(4), 'a'), Integer(5), Integer(100))
>>> v = random_vector(GF(Integer(4), 'a'), Integer(100))
>>> iter = FiniteFieldsubspace_iterator(A, v)
>>> len(list(iter))
1024

class sage.modules.finite_submodule_iter.FiniteFieldsubspace_iterator[source]#

This class implements an iterator over the subspace of a vector space over a finite field. The subspace is generated by basis.

INPUT:

• basis – a list of vectors or a matrix with elements over a finite field. If a matrix is provided then it is not checked whether the matrix is full ranked. Similarly, if a list of vectors is provided, then the linear independence of the vectors is not checked.

• coset_rep (optional) – a vector in the same ambient space, if one aims to compute a coset of the vector space given by basis.

• immutable (optional; default: False) – set it to True to return immutable vectors.

EXAMPLES:

sage: from sage.modules.finite_submodule_iter import FiniteFieldsubspace_iterator
sage: A = random_matrix(GF(2), 10, 100)
sage: iter = FiniteFieldsubspace_iterator(A)
sage: len(list(iter))
1024
sage: X = random_matrix(GF(4, 'a'), 7, 100).row_space()
sage: s = list(X)  # long time (5s on sage.math, 2013)
sage: t = list(FiniteFieldsubspace_iterator(X.basis()))  # takes 0.31s
sage: sorted(t) == sorted(s)  # long time
True

>>> from sage.all import *
>>> from sage.modules.finite_submodule_iter import FiniteFieldsubspace_iterator
>>> A = random_matrix(GF(Integer(2)), Integer(10), Integer(100))
>>> iter = FiniteFieldsubspace_iterator(A)
>>> len(list(iter))
1024
>>> X = random_matrix(GF(Integer(4), 'a'), Integer(7), Integer(100)).row_space()
>>> s = list(X)  # long time (5s on sage.math, 2013)
>>> t = list(FiniteFieldsubspace_iterator(X.basis()))  # takes 0.31s
>>> sorted(t) == sorted(s)  # long time
True

class sage.modules.finite_submodule_iter.FiniteFieldsubspace_projPoint_iterator[source]#

Bases: object

This class implements an iterator over the projective points of a vector space over a finite field. The vector space is generated by basis and need not to be equal to the full ambient space.

A projective point (= one dimensional subspace) $$P$$ will be represented by a generator $$p$$. To ensure that all $$p$$ will be normalized you can set the optional argument normalize to True.

INPUT:

• basis – a list of vectors or a matrix with elements over a finite field. If a matrix is provided then it is not checked whether the matrix is full ranked. Similarly, if a list of vectors is provided, then the linear independence of the vectors is not checked.

• normalize (optional; default: False) – boolean which indicates if the returned vectors should be normalized, i.e. the first nonzero coordinate is equal to 1.

• immutable (optional; default: False) – set it to True to return immutable vectors.

EXAMPLES:

sage: from sage.modules.finite_submodule_iter import FiniteFieldsubspace_iterator, FiniteFieldsubspace_projPoint_iterator
sage: A = random_matrix(GF(4, 'a'), 5, 100)
sage: a = len(list(FiniteFieldsubspace_iterator(A)))
sage: b = len(list(FiniteFieldsubspace_projPoint_iterator(A)))
sage: b == (a-1)/3
True

>>> from sage.all import *
>>> from sage.modules.finite_submodule_iter import FiniteFieldsubspace_iterator, FiniteFieldsubspace_projPoint_iterator
>>> A = random_matrix(GF(Integer(4), 'a'), Integer(5), Integer(100))
>>> a = len(list(FiniteFieldsubspace_iterator(A)))
>>> b = len(list(FiniteFieldsubspace_projPoint_iterator(A)))
>>> b == (a-Integer(1))/Integer(3)
True


Prove that the option normalize == True will only return normalized vectors.

sage: all(x.monic() == x for x in FiniteFieldsubspace_projPoint_iterator(A, True)) True

class sage.modules.finite_submodule_iter.FiniteZZsubmodule_iterator[source]#

Bases: object

Let $$G$$ be an abelian group and suppose that $$(g_0, \ldots, g_n)$$ is a list of elements of $$G$$, whose additive orders are equal to $$m_i$$ and $$\sum_{i=0}^n x_i g_i = 0$$ for $$x_i \in \ZZ_{m_i}$$ for $$i \in \{0, \dots, n\}$$ implies $$x_i=0$$ for all $$i$$.

This class implements an iterator over the $$\ZZ$$-submodule $$M = \{\sum_{i=0}^n x_i g_i\}$$. If the independence condition from above is not fulfilled, we can still use this iterator to run over the elements. In this case the elements will occur multiple times.

Getting from one element of the submodule to another is performed by one single addition in $$G$$.

INPUT:

• basis – the elements $$(g_0, \ldots, g_n)$$

• order (optional) – the additive_orders $$m_i$$ of $$g_i$$.

• coset_rep (optional) – an element of g, if one aims to compute a coset of the $$\ZZ$$-submodule $$M$$.

• immutable (optional; default: False) – set it to True to return immutable elements. Setting this to True makes sense if the elements are vectors. See FiniteFieldsubspace_iterator for examples.

EXAMPLES:

sage: from sage.modules.finite_submodule_iter import FiniteZZsubmodule_iterator
sage: F.<x,y,z> = FreeAlgebra(GF(3),3)
sage: iter = FiniteZZsubmodule_iterator([x,y], [3,3])
sage: list(iter)
[0, x, 2*x, y, x + y, 2*x + y, 2*y, x + 2*y, 2*x + 2*y]
sage: iter = FiniteZZsubmodule_iterator([x,y], [3,3], z)
sage: list(iter)
[z, x + z, 2*x + z, y + z, x + y + z, 2*x + y + z, 2*y + z, x + 2*y + z, 2*x + 2*y + z]

>>> from sage.all import *
>>> from sage.modules.finite_submodule_iter import FiniteZZsubmodule_iterator
>>> F = FreeAlgebra(GF(Integer(3)),Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = F._first_ngens(3)
>>> iter = FiniteZZsubmodule_iterator([x,y], [Integer(3),Integer(3)])
>>> list(iter)
[0, x, 2*x, y, x + y, 2*x + y, 2*y, x + 2*y, 2*x + 2*y]
>>> iter = FiniteZZsubmodule_iterator([x,y], [Integer(3),Integer(3)], z)
>>> list(iter)
[z, x + z, 2*x + z, y + z, x + y + z, 2*x + y + z, 2*y + z, x + 2*y + z, 2*x + 2*y + z]