Tutorial: Using Free Modules and Vector Spaces
system:sage


Tutorial: Using Free Modules and Vector Spaces -- Sage Reference Manual v4.4.4
system:sage

<div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index" accesskey="I">index</a></li>
        <li class="right">
          <a href="../modindex.html" title="Global Module Index" accesskey="M">modules</a> |</li>
  
    
      <a href="../../index.html"><img src="../_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="../index.html">Sage Reference v4.4.4</a> &raquo;</li>
 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body">
            
  <div class="section" id="tutorial-using-free-modules-and-vector-spaces">
<h1>Tutorial: Using Free Modules and Vector Spaces<a class="headerlink" href="#tutorial-using-free-modules-and-vector-spaces" title="Permalink to this headline">¶</a></h1>
<p>In this tutorial, we show how to construct and manipulate free modules
and vector spaces and their elements.</p>
<p>Sage currently provides two implementations of free modules:
<tt class="xref docutils literal"><span class="pre">FreeModule</span></tt> and <a title="sage.combinat.free_module.CombinatorialFreeModule" class="reference external" href="sage/combinat/free_module.html#sage.combinat.free_module.CombinatorialFreeModule"><tt class="xref docutils literal"><span class="pre">CombinatorialFreeModule</span></tt></a>. 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 <img class="math" src="../_images/math/ea3695fa2fb9c142966da2768e756c784a16c4dc.png" alt="0,1,2,...">. They also differ by feature set and
efficiency. Eventually, both implementations will be merged under the
name <tt class="xref docutils literal"><span class="pre">FreeModule</span></tt>. In the mean time, we focus here on
<a title="sage.combinat.free_module.CombinatorialFreeModule" class="reference external" href="sage/combinat/free_module.html#sage.combinat.free_module.CombinatorialFreeModule"><tt class="xref docutils literal"><span class="pre">CombinatorialFreeModule</span></tt></a>. We recommend to start by browsing
the documentation.</p>
<div class="highlight-python"><pre>sage: CombinatorialFreeModule?</pre>
</div>
<p>We begin with a minimal example. What does this give us?</p>
<div class="highlight-python">

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

</div>
<p>We can use any set whose elements are immutable to index the
basis. Here is the <img class="math" src="../_images/math/73a2f1c6167409a35e72eabec74a8561652f99b4.png" alt="\ZZ"> free module whose basis is indexed by complex
numbers:</p>
<div class="highlight-python">

{{{id=1|
A = CombinatorialFreeModule(ZZ, CC); A.an_element()
///
B[1.00000000000000*I]
}}}

{{{id=2|
A = CombinatorialFreeModule(ZZ, Partitions(NonNegativeIntegers(), max_part=3)); A.an_element()
///
B[[]] + 2*B[[1]] + 3*B[[2]]
}}}

{{{id=3|
A = CombinatorialFreeModule(ZZ, [&#39;spam&#39;, &#39;eggs&#39;, 42]); A.an_element()
///
2*B['eggs'] + 2*B['spam'] + 3*B[42]
}}}

{{{id=4|
A = CombinatorialFreeModule(ZZ, ([1],[2],[3])); A.an_element()
///
TypeError: unhashable type: 'list'
}}}

</div>
<p>We can customize the name of the basis however we want:</p>
<div class="highlight-python">

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

</div>
<p>Let us do some arithmetic with elements of <img class="math" src="../_images/math/019e9892786e493964e145e7c5cf7b700314e53b.png" alt="A">:</p>
<div class="highlight-python">

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

{{{id=7|
2*f
///
2*a[0] + 6*a[1] + 6*a[2]
}}}

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

{{{id=9|
a[0] + 3*a[1]
///
NameError: name 'a' is not defined
}}}

</div>
<p>To construct elements directly, we must first get the basis for the
module:</p>
<div class="highlight-python">

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

</div>
<p>copy-paste works if the prefix matches the name of the basis:</p>
<div class="highlight-python">

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

</div>
<p>Be careful, that the input is currently <em>not</em> checked:</p>
<div class="highlight-python">

{{{id=12|
a[&#39;is&#39;] + a[&#39;this&#39;] + a[&#39;a&#39;] + a[&#39;bug&#39;]
///
a['a'] + a['bug'] + a['is'] + a['this']
}}}

{{{id=13|
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}
}}}

</div>
<p><tt class="docutils literal"><span class="pre">A.basis()</span></tt> models the family <img class="math" src="../_images/math/f1dca72c3a7b154ebab293ab3634e400746656a6.png" alt="(B_i)_{i \in \ZZ_5}">.  See the
documentation for <a title="sage.sets.family.Family" class="reference external" href="sage/sets/family.html#sage.sets.family.Family"><tt class="xref docutils literal"><span class="pre">Family</span></tt></a> for more information:</p>
<div class="highlight-python"><pre>sage: Family?</pre>
</div>
<p>The elements of our module come with many methods for
exploring and manipulating them:</p>
<div class="highlight-python">

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

</div>
<p>Some notation:</p>
<blockquote>
<ul class="simple">
<li><em>term</em>: <tt class="docutils literal"><span class="pre">coefficient</span> <span class="pre">*</span> <span class="pre">basis_element</span></tt></li>
<li><em>monomial</em>: <tt class="docutils literal"><span class="pre">basis_element</span></tt> <em>without</em> a coefficient</li>
<li><em>support</em>: the index of a <tt class="docutils literal"><span class="pre">basis_element</span></tt></li>
<li><em>item</em> : a <a title="(in Python v2.6)" class="reference external" href="http://docs.python.org/library/functions.html#tuple"><tt class="xref docutils literal"><span class="pre">tuple</span></tt></a> <tt class="docutils literal"><span class="pre">(index,</span> <span class="pre">coefficient)</span></tt></li>
</ul>
</blockquote>
<p>Note that elements are printed starting with the (lexicographically by
default) <em>least</em> index. Leading/trailing refers to the greatest/least
index, respectively:</p>
<div class="highlight-python">

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

{{{id=16|
&quot;Leading term: &quot;,f.leading_term()
///
Leading term:  3*a[2]
}}}

{{{id=17|
print &quot;Leading monomial: &quot;,f.leading_monomial()
///
Leading monomial:  a[2]
}}}

{{{id=18|
print &quot;Leading support: &quot;,f.leading_support()
///
Leading support:  2
}}}

{{{id=19|
print &quot;Leading coefficient: &quot;,f.leading_coefficient()
///
Leading coefficient:  3
}}}

{{{id=20|
print &quot;Leading item: &quot;,f.leading_item()
///
Leading item:  (2, 3)
}}}

{{{id=21|
f.leading_term
print &quot;Support: &quot;,f.support()
///
Support:  [0, 1, 2]
}}}

{{{id=22|
print &quot;Monomials: &quot;,f.monomials()
///
Monomials:  [a[0], a[1], a[2]]
}}}

{{{id=23|
print &quot;Coefficients: &quot;,f.coefficients()
///
Coefficients:  [1, 3, 3]
}}}

</div>
<p>We can iterate through the items in an element:</p>
<div class="highlight-python">

{{{id=24|
for index, coeff in f:
       print &quot;The coefficient of a_{%s} is %s&quot;%(index, coeff)
///
The coefficient of a_{0} is 1
The coefficient of a_{1} is 3
The coefficient of a_{2} is 3
}}}

{{{id=25|
# This uses the fact that f can be thought of as a dictionary  index--&gt;coefficient
print f[0], f[1], f[2]
///
1 3 3
}}}

{{{id=26|
# This dictionary can be accessed explicitly with the monomial_coefficients method
f.monomial_coefficients()
///
{0: 1, 1: 3, 2: 3}
}}}

</div>
<p>The parent (<img class="math" src="../_images/math/019e9892786e493964e145e7c5cf7b700314e53b.png" alt="A"> in our example) has several utility methods for
constructing elements:</p>
<div class="highlight-python">

{{{id=27|
A.
A.zero()
///
0
}}}

{{{id=28|
A.sum_of_monomials(i for i in Zmod(5) if i &gt; 2)
///
a[3] + a[4]
}}}

{{{id=29|
A.sum_of_terms((i+1,i) for i in Zmod(5) if i &gt; 2)
///
4*a[0] + 3*a[4]
}}}

{{{id=30|
A.sum(ZZ(i)*a[i+1] for i in Zmod(5) if i &gt; 2)  # Note coeff is not (currently) implicitly coerced
///
4*a[0] + 3*a[4]
}}}

</div>
<p>Note that it is safer to use <tt class="docutils literal"><span class="pre">A.sum()</span></tt> then to use <tt class="docutils literal"><span class="pre">sum()</span></tt>, in
case the input is an empty iterable:</p>
<div class="highlight-python">

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

{{{id=32|
print sum([]),&#39;:&#39;, parent(sum([]))
///
0 : <type 'int'>
}}}

</div>
<p>The <tt class="docutils literal"><span class="pre">map</span></tt> methods are useful ways to transform elements:</p>
<div class="highlight-python">

{{{id=33|
f.map_
print f,&quot;--&gt;&quot;, f.map_support     (lambda i  : i+3)
///
a[0] + 3*a[1] + 3*a[2] --> 3*a[0] + a[3] + 3*a[4]
}}}

{{{id=34|
print f,&quot;--&gt;&quot;, f.map_coefficients(lambda c  : c-1)
///
a[0] + 3*a[1] + 3*a[2] --> 2*a[1] + 2*a[2]
}}}

{{{id=35|
print f,&quot;--&gt;&quot;, f.map_term        (lambda i,c: (i+3,c-1))
///
a[0] + 3*a[1] + 3*a[2] --> 2*a[0] + 2*a[4]
}}}

</div>
<p><tt class="docutils literal"><span class="pre">f.map_mc</span></tt> is a deprecated synonym for <tt class="docutils literal"><span class="pre">f.map_term</span></tt>.</p>
<p>Note that <tt class="docutils literal"><span class="pre">term</span></tt> and <tt class="docutils literal"><span class="pre">item</span></tt> are not yet used completely consistently.</p>
<p>This fully functional <img class="math" src="../_images/math/73a2f1c6167409a35e72eabec74a8561652f99b4.png" alt="\ZZ">-module was created with the simple commands:</p>
<div class="highlight-python">

{{{id=36|
A = CombinatorialFreeModule(ZZ, Zmod(5), prefix=&#39;a&#39;)
a = A.basis()
///
}}}

</div>
</div>


          </div>
        </div>
      </div>
      <div class="sphinxsidebar">
        <div class="sphinxsidebarwrapper">
            <h3>This Page</h3>
            <ul class="this-page-menu">
              <li><a href="../_sources/demos/tutorial-using-free-modules.txt" rel="nofollow">Show Source</a></li>
            </ul>
          <div id="searchbox" style="display: none">
            <h3>Quick search</h3>
              <p class="searchtip" style="font-size: 90%">
              Enter search terms or a module, class or function name.
              </p>
          </div>
          <script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="../genindex.html" title="General Index">index</a></li>
        <li class="right">
          <a href="../modindex.html" title="Global Module Index">modules</a> |</li>
  
    
      <a href="../../index.html"><img src="../_static/sagelogo.png" style="vertical-align: middle" title="Sage Logo"></a>
    
  
  
        <li><a href="../index.html">Sage Reference v4.4.4</a> &raquo;</li>
 
      </ul>
    </div>
    
    <div class="footer">
      &copy; Copyright 2005--2010, The Sage Development Team.
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 0.6.3.
    </div>
    <script type="text/javascript">
/*global jQuery, window */
/* Sphinx sidebar toggle.  Putting this code at the end of the body
 * enables the toggle for the live, static, and offline docs.  Note:
 * sage.misc.html.math_parse() eats jQuery's dollar-sign shortcut. */
var jq = jQuery;  
jq(document).ready(function () {
    var bar, bod, bg, fg, key, tog, wid_old, wid_new, resize, get_state, set_state;
    bod = jq('div.bodywrapper');
    bar = jq('div.sphinxsidebar');
    tog = jq('<div class="sphinxsidebartoggle"></div>');
    
    /* Delayed resize helper.  Not perfect but good enough. */
    resize = function () {
        setTimeout(function () {
            tog.height(bod.height());
        }, 100);
    };
    jq(window).resize(function () {
        resize();
    });
    
    /* Setup and add the toggle. See Sphinx v0.5.1 default.css. */
    fg = jq('div.sphinxsidebar p a').css('color') || 'rgb(152, 219, 204)';
    bg = jq('div.document').css('background-color') || 'rgb(28, 78, 99)';
    wid_old = '230px';
    wid_new = '5px';
    tog.css('background-color', bg)
        .css('border-width', '0px')
        .css('border-right', wid_new + ' ridge ' + bg)
        .css('cursor', 'pointer')
        .css('position', 'absolute')
        .css('left', '-' + wid_new)
        .css('top', '0px')
        .css('width', wid_new);
    bod.css('position', 'relative');
    bod.prepend(tog);
    resize();
    
    /* Cookie helpers. */
    key = 'sphinxsidebar=';
    set_state = function (s) {
        var date = new Date();
        /* Expiry in 7 days. */
        date.setTime(date.getTime() + (7 * 24 * 3600 * 1000));
        document.cookie = key + encodeURIComponent(s) + '; expires=' +
            date.toUTCString() + '; path=/';
    };
    get_state = function () {
        var i, c, crumbs = document.cookie.split(';');
        for (i = 0; i < crumbs.length; i += 1) {
            c = crumbs[i].replace(/^\s+/, '');
            if (c.indexOf(key) === 0) {
                return decodeURIComponent(c.substring(key.length, c.length));
            }
        }
        return null;
    };
    
    /* Event handlers. */
    tog.mouseover(function (ev) {
        tog.css('border-right-color', fg);
    }).mouseout(function (ev) {
        tog.css('border-right-color', bg);
    }).click(function (ev) {
        if (bod.hasClass('wide')) {
            bod.removeClass('wide');
            bod.css('margin-left', wid_old);
            bar.css('width', wid_old);
            bar.show();
            set_state('visible');
        } else {
            set_state('hidden');
            bar.hide();
            bar.css('width', '0px');
            bod.css('margin-left', wid_new);
            bod.addClass('wide');
        }
        resize();
    });
    
    /* Hide the normally visible sidebar? */
    if (get_state() === 'hidden') {
        tog.trigger('click');
    } else {
        set_state('visible');
    }
});
    </script>