Tutorial: Using Free Modules and Vector Spaces

In this tutorial, we show how to construct and manipulate free modules and vector spaces and their elements.

Sage currently provides two implementations of free modules: FreeModule and CombinatorialFreeModule. The distinction between the two is mostly an accident in history. The later allows for the basis to be indexed by any kind of objects, instead of just \(0,1,2,...\). They also differ by feature set and efficiency. Eventually, both implementations will be merged under the name FreeModule. In the mean time, we focus here on CombinatorialFreeModule. We recommend to start by browsing its documentation:

sage: CombinatorialFreeModule?                # not tested

Construction, arithmetic, and basic usage

We begin with a minimal example:

sage: G = Zmod(5)
sage: F = CombinatorialFreeModule(ZZ, G)
sage: F.an_element()
2*B[0] + 2*B[1] + 3*B[2]

\(F\) is the free module over the ring integers \(\ZZ\) whose canonical basis is indexed by the set of integers modulo 5.

We can use any set, finite or not, to index the basis, as long as its elements are immutable. Here are some \(\ZZ\)-free modules; what is the indexing set for the basis in each example below?

sage: F = CombinatorialFreeModule(ZZ, CC); F.an_element()
B[1.00000000000000*I]
sage: F = CombinatorialFreeModule(ZZ, Partitions(NonNegativeIntegers(), max_part=3)); F.an_element()
2*B[[]] + 2*B[[1]] + 3*B[[2]]
sage: F = CombinatorialFreeModule(ZZ, ['spam', 'eggs', '42']); F.an_element()
3*B['42'] + 2*B['eggs'] + 2*B['spam']

Note that we use ‘42’ (and not the number 42) in order to ensure that all objects are comparable in a deterministic way, which allows the elements to be printed in a predictable manner. It is not mandatory that indices have such a stable ordering, but if they do not, then the elements may be displayed in some random order.

Lists are not hashable, and thus cannot be used to index the basis; instead one can use tuples:

sage: F = CombinatorialFreeModule(ZZ, ([1],[2],[3])); F.an_element()
Traceback (most recent call last):
...
TypeError: unhashable type: 'list'

sage: F = CombinatorialFreeModule(ZZ, ((1,), (2,), (3,))); F.an_element()
2*B[(1,)] + 2*B[(2,)] + 3*B[(3,)]

The name of the basis can be customized:

sage: F = CombinatorialFreeModule(ZZ, Zmod(5), prefix='a'); F.an_element()
2*a[0] + 2*a[1] + 3*a[2]

Let us do some arithmetic with elements of \(A\):

sage: f = F.an_element(); f
2*a[0] + 2*a[1] + 3*a[2]

sage: 2*f
4*a[0] + 4*a[1] + 6*a[2]

sage: 2*f - f
2*a[0] + 2*a[1] + 3*a[2]

Inputing elements as they are output does not work by default:

sage: a[0] + 3*a[1]
Traceback (most recent call last):
...
NameError: name 'a' is not defined

To enable this, we must first get the canonical basis for the module:

sage: a = F.basis(); a
Lazy family (Term map from Ring of integers modulo 5 to Free module generated by Ring of integers modulo 5 over Integer Ring(i))_{i in Ring of integers modulo 5}

This gadget models the family \((B_i)_{i \in \ZZ_5}\). In particular, one can run through its elements:

sage: list(a)
[a[0], a[1], a[2], a[3], a[4]]

recover its indexing set:

sage: a.keys()
Ring of integers modulo 5

or construct an element from the corresponding index:

sage: a[2]
a[2]

So now we can do:

sage: a[0] + 3*a[1]
a[0] + 3*a[1]

which enables copy-pasting outputs as long as the prefix matches the name of the basis:

sage: 2*a[0] + 2*a[1] + 3*a[2] == f
True

Be careful that the input is currently not checked:

sage: a['is'] + a['this'] + a['a'] + a['bug']
a['a'] + a['bug'] + a['is'] + a['this']

Manipulating free module elements

The elements of our module come with many methods for exploring and manipulating them:

sage: f.<tab>                                 # not tested

Some definitions:

  • A monomial is an element of the basis \(B_i\);
  • A term is an element of the basis multiplied by a non zero coefficient: \(c B_i\);
  • The support of that term is \(i\).
  • The corresponding item is the tuple (i, c).
  • The support of an element \(f\) is the collection of indices \(i\) such that \(B_i\) appears in \(f\) with non zero coefficient.
  • The monomials, terms, items, and coefficients of an element \(f\) are defined accordingly.
  • Leading/trailing refers to the greatest/least index. Elements are printed starting with the least index (for lexicographic order by default).

Let us investigate those definitions on our example:

sage: f
2*a[0] + 2*a[1] + 3*a[2]
sage: f.leading_term()
3*a[2]
sage: f.leading_monomial()
a[2]
sage: f.leading_support()
2
sage: f.leading_coefficient()
3
sage: f.leading_item()
(2, 3)

sage: f.support()
[0, 1, 2]
sage: f.monomials()
[a[0], a[1], a[2]]
sage: f.coefficients()
[2, 2, 3]

We can iterate through the items of an element:

sage: for index, coeff in f:
....:     print("The coefficient of a_{%s} is %s"%(index, coeff))
The coefficient of a_{0} is 2
The coefficient of a_{1} is 2
The coefficient of a_{2} is 3

This element can be thought of as a dictionary index–>coefficient:

sage: f[0], f[1], f[2]
(2, 2, 3)

This dictionary can be accessed explicitly with the monomial_coefficients method:

sage: f.monomial_coefficients()
{0: 2, 1: 2, 2: 3}

The map methods are useful to transform elements:

sage: f
2*a[0] + 2*a[1] + 3*a[2]
sage: f.map_support(lambda i: i+1)
2*a[1] + 2*a[2] + 3*a[3]
sage: f.map_coefficients(lambda c: c-3)
-a[0] - a[1]
sage: f.map_item(lambda i,c: (i+1,c-3))
-a[1] - a[2]

Note: the later function should be called map_items!

Manipulating free modules

The free module itself (\(A\) in our example) has several utility methods for constructing elements:

sage: F.zero()
0
sage: F.sum_of_monomials(i for i in Zmod(5) if i > 2)
a[3] + a[4]
sage: F.sum_of_terms((i+1,i) for i in Zmod(5) if i > 2)
4*a[0] + 3*a[4]
sage: F.sum(ZZ(i)*a[i+1] for i in Zmod(5) if i > 2)  # Note coeff is not (currently) implicitly coerced
4*a[0] + 3*a[4]

Is safer to use F.sum() than to use sum(): in case the input is an empty iterable, it makes sure the zero of \(A\) is returned, and not a plain \(0\):

sage: F.sum([]), parent(F.sum([])) (0, Free module generated by Ring of integers modulo 5 over Integer Ring) sage: sum([]), parent(sum([])) (0, <type ‘int’>)

Todo

Introduce echelon forms, submodules, quotients in the finite dimensional case

Review

In this tutorial we have seen how to construct vector spaces and free modules with a basis indexed by any kind of objects.

To learn how to endow such free modules with additional structure, define morphisms, or implement modules with several distinguished basis, see the Implementing Algebraic Structures thematic tutorial.