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: :class:`FreeModule` and :class:`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 :class:`FreeModule`. In the mean time, we focus here on :class:`CombinatorialFreeModule`. We recommend to start by browsing the documentation.

{{{id=0| CombinatorialFreeModule? /// }}}

We begin with a minimal example. What does this give us?

{{{id=1| G = Zmod(5) A = CombinatorialFreeModule(ZZ, G) A.an_element() /// 2*B[0] + 2*B[1] + 3*B[2] }}}

We can use any set whose elements are immutable to index the basis. Here are some $ZZ$-free modules; what is the indexing set for the basis in each case?

sage: A = CombinatorialFreeModule(ZZ, CC); A.an_element() B[1.00000000000000*I] sage: A = CombinatorialFreeModule(ZZ, Partitions(NonNegativeIntegers(), max_part=3)); A.an_element() B[[]] + 2*B[[1]] + 3*B[[2]] sage: A = CombinatorialFreeModule(ZZ, ['spam', 'eggs', 42]); A.an_element() 2*B['eggs'] + 2*B['spam'] + 3*B[42]
{{{id=2| A = CombinatorialFreeModule(ZZ, ([1],[2],[3])); A.an_element() /// Traceback (most recent call last): TypeError: unhashable type: 'list' }}}

We can customize the name of the basis however we want:

{{{id=3| A = CombinatorialFreeModule(ZZ, Zmod(5), prefix='a'); A.an_element() /// a[0] + 3*a[1] + 3*a[2] }}}

Let us do some arithmetic with elements of $A$:

{{{id=4| f = A.an_element(); f /// a[0] + 3*a[1] + 3*a[2] }}} {{{id=5| 2*f /// 2*a[0] + 6*a[1] + 6*a[2] }}} {{{id=6| 2*f - f /// a[0] + 3*a[1] + 3*a[2] }}}

This does not work yet:

{{{id=7| a[0] + 3*a[1] /// Traceback (most recent call last): NameError: name 'a' is not defined }}}

To construct elements directly, we must first get the basis for the module:

{{{id=8| a = A.basis() a[0] + 3*a[1] /// a[0] + 3*a[1] }}}

Copy-pasting works if the prefix matches the name of the basis:

{{{id=9| a[0] + 3*a[1] + 3*a[2] == f /// True }}}

Be careful, that the input is currently not checked:

{{{id=10| a['is'] + a['this'] + a['a'] + a['bug'] /// a['a'] + a['bug'] + a['is'] + a['this'] }}} {{{id=11| 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} }}}

A.basis() models the family $(B_i)_{i in ZZ_5}$. See the documentation for :class:`Family` for more information:

{{{id=12| Family? /// }}}

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

{{{id=13| f. /// }}}

Some notation:

Note that elements are printed starting with the least index (for lexicographic order by default). Leading/trailing refers to the greatest/least index, respectively:

{{{id=14| f /// a[0] + 3*a[1] + 3*a[2] }}} {{{id=15| "Leading term: ",f.leading_term() /// Leading term: 3*a[2] }}} {{{id=16| print "Leading monomial: ",f.leading_monomial() /// Leading monomial: a[2] }}} {{{id=17| print "Leading support: ",f.leading_support() /// Leading support: 2 }}} {{{id=18| print "Leading coefficient: ",f.leading_coefficient() /// Leading coefficient: 3 }}} {{{id=19| print "Leading item: ",f.leading_item() /// Leading item: (2, 3) }}} {{{id=20| f.leading_term print "Support: ",f.support() /// Support: [0, 1, 2] }}} {{{id=21| print "Monomials: ",f.monomials() /// Monomials: [a[0], a[1], a[2]] }}} {{{id=22| print "Coefficients: ",f.coefficients() /// Coefficients: [1, 3, 3] }}}

We can iterate through the items in an element:

{{{id=23| for index, coeff in f: print "The coefficient of a_{%s} is %s"%(index, coeff) /// The coefficient of a_{0} is 1The coefficient of a_{1} is 3The coefficient of a_{2} is 3 }}} {{{id=24| # This uses the fact that f can be thought of as a dictionary index-->coefficient print f[0], f[1], f[2] /// 1 3 3 }}} {{{id=25| # This dictionary can be accessed explicitly with the monomial_coefficients method f.monomial_coefficients() /// {0: 1, 1: 3, 2: 3} }}}

The parent ($A$ in our example) has several utility methods for constructing elements:

{{{id=26| A. A.zero() /// 0 }}} {{{id=27| A.sum_of_monomials(i for i in Zmod(5) if i > 2) /// a[3] + a[4] }}} {{{id=28| A.sum_of_terms((i+1,i) for i in Zmod(5) if i > 2) /// 4*a[0] + 3*a[4] }}} {{{id=29| A.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] }}}

Note that it is safer to use A.sum() than to use sum(), in case the input is an empty iterable:

{{{id=30| print A.sum([]),':', parent(A.sum([])) /// 0 : Free module generated by Ring of integers modulo 5 over Integer Ring }}} {{{id=31| print sum([]),':', parent(sum([])) /// 0 : }}}

The map methods are useful to transform elements:

{{{id=32| f.map_ print f,"-->", f.map_support (lambda i : i+3) /// a[0] + 3*a[1] + 3*a[2] --> 3*a[0] + a[3] + 3*a[4] }}} {{{id=33| print f,"-->", f.map_coefficients(lambda c : c-1) /// a[0] + 3*a[1] + 3*a[2] --> 2*a[1] + 2*a[2] }}} {{{id=34| print f,"-->", f.map_term (lambda i,c: (i+3,c-1)) /// a[0] + 3*a[1] + 3*a[2] --> 2*a[0] + 2*a[4] }}}

f.map_mc is a deprecated synonym for f.map_term.

Note that term and item are not yet used completely consistently.