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.


All non-trivial code must be in the 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 and the report skeleton in the

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

%load_ext autoreload
%autoreload 2
from moncode import *


response("As-tu faim")

Consultation of the documentation:


Static checks:


Launching the tests:

!sage -t


To use Sage objects in, 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?


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?