# 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
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?