Assignment

Access to the software and download of the assignment

For this week, the assignment will be essentially empty. Using the git repository will mainly be a convenient way for you to save and transfer your work, and for us to review it.

Instructions

All non-trivial code must be in the moncode.py file. If it becomes too long, you can create other files, mentioning them in the mentioning them in the report.

Any function must:

• be documented
  the documentation must include examples and a quick estimate of the algorithmic complexity of the function;

• be tested
  see the example provided for how to write the tests as doctests;

• use wherever possible annotations of type.

You should have checked your code with static analysers such as pyflakes or mypy.

In addition, you must keep a concise report up to date along the way.

Getting started

See the files moncode.py and the report skeleton in the README.md.

Import the objects defined in moncode.py and reload them automatically when changes are made:

%load_ext autoreload
%autoreload 2
from moncode import *

Use:

response("As-tu faim")

Consultation of the documentation:

response?

Static checks:

!pyflakes moncode.py

!mypy moncode.py

Launching the tests:

!sage -t moncode.py

Indications

To use Sage objects in moncode.py, e.g. for type annotations, you need to import them:

from sage.all import matrix, GF  # type:ignore

Gauß elimination

Implement Gauß’s algorithm for computing the row echelon form of a matrix with coefficients in a field:

def reduced_echelon_form(m: matrix) -> matrix:
    """
    Returns the matrix `m` put in step form 
    “""

What is the complexity of your implementation?

Note

Here and in latter complexity analyses, state explicitly your computation model: how do you measure the size of the input? What are the elementary operations? Justify your analysis.

Membership testing for a vector subspace

Let V=(v_i)_i be a list of vectors. We wish to determine whether a vector w is in the vector subspace generated by (v_i)_i.

Implement a function:

def subspace_membership(V, w):
    """
    Test whether `w` is generated by the vectors in `V`.
    """

You will use the reduced_echelon_form function.

Would it be enough to have a matrix in echelon form?

What is the complexity of your implementation?

Computation of a base of the sum of two vector subspaces

Let \(U\) and \(V\) be two subspaces of some finite dimensional vector space \(W\), each given by a basis expressed in the canonical basis of \(W\). Implement an algorithm that computes a basis of the sum \(U+V\) of these two subspaces.

What is the complexity of your implementation?