### 4.4.Assignment #4: Vector Spaces and Polynomials(back to full lecture notes)

In this assignment you will use Python to implement several functions that operate on vector spaces and polynomials. Please submit a single file `a4.py` containing your solutions.

Your file may not import any modules or employ any external library functions (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts.

In this assignment, we will represent vectors in Rn and matrices in Rn×n using Python tuples and nested tuples, respectively (as we did in Assignment #3). A helper function `solve()` is provided below. This function takes a square matrix `M` as its first argument and a vector `w` as its second argument. If there is a solution `v` to the equation `M * v = w`, it returns the vector `v`; otherwise, it returns `None`. The `solve()` method has been updated. Please use the implementation below, which should handle zero rows and columns correctly.

```def solve(M, w, epsilon = 1.0/(10**10)):
rows, cols = len(M)+1, len(M[0])+1
if rows != cols: return None
I = [[1 if c==r else 0 for c in range(cols)] for r in range(rows)]
M = [([M[c][r] for c in range(cols-1)] if r < rows-1 else list(w))+[0]+I[r] for r in range(rows)]
def soln(M):
if len([1 for i in range(cols) if abs(M[-1][i]) > epsilon]) > 0: return None
return tuple([-1*M[-1][cols+j] for j in range(cols-1)])
for r in range(rows):
if lead >= cols: return soln(M)
i = r
i += 1
if i == rows:
if cols == lead: return soln(M)
M[r] = [ mrx / M[r][lead] for mrx in M[r]]
for i in [j for j in range(rows) if j != r]:
if r < rows-1:
M[i] = [ iv - M[i][lead]*rv for rv,iv in zip(M[r],M[i])]
return soln(M)```
Below is an example of `solve()` being invoked:
`solve( ((1,3),(2,1)), (5,6) ) # Returns (2.6, 0.8).`
1. A definition of the `Span` class is provided below. Objects of this class represent spans; the `vectors` field of each object is the finite set of vectors { v1, ..., vk } in the notation span { v1, ..., vk }.
```class Span():
def __repr__(self): return "span " + str(self.vectors)
def __str__(self):  return "span " + str(self.vectors)
def __init__(self, vectors): self.vectors = vectors

def contains(self, v):
pass # Implement for Problem #1, part (a).

def __eq__(span1, span2):
pass # Implement for Problem #1, part (b).

def basis(self):
pass # Implement for Problem #1, part (c).

def dim(self):
pass # Implement for Problem #1, part (d).

def orthonormal(self):
pass # Implement for Problem #1, part (e).```

1. Define the `Span` class's `contains()` method, which returns `True` if the vector argument `v` is in the vector space defined by the span, and `False` otherwise.
```V = Span( { (1,0), (0,1) } )
V.contains((2,-3)) # Returns True.```
2. Define the `Span` class's `__eq__()` method, which takes two arguments that are both `Span` objects. The method should return `True` if the two spans are equivalent; it should return `False` otherwise. This method is invoked if you apply the `==` operator to two `Span` objects:
`Span( { (1,0), (0,1) } ) == Span( { (2,3) } ) # Returns False.`
3. Define the `Span` class's `basis()` method, which returns a finite set of vectors corresponding to a basis of the vector space represented by the `Span` object.
4. Define the `Span` class's `dim()` method, which returns a positive integer corresponding to the dimension of the vector space represented by the `Span` object.
5. Define the `Span` class's `orthonormal()` method, which returns a finite set of vectors corresponding to an orthonormal basis of the vector space represented by the `Span` object.
2. Define a function `exactFit()` that takes as its input a set of vectors in R2. If there are k + 1 vectors in the input, the function should find a polynomial of the form f(x) = ak xk + ... + a1 x + a0 that exactly fits these vectors. The function should return a single vector (ak, ..., a1, a0) containing the coefficients of the polynomial.
```      exactFit( {
(-1,31), (-4,  268327), ( 1,  17), (-5, -1520701), ( 3,  389147), \
(-3,  78869), (-6, -19979509), ( 5,  29571949), ( 0, -1), (-2,  5027) \
} )
# The above should return (8, 36, -1, -2, 0, -9, -4, 0, -10, -1) where k is 9.```
3. In this problem, input polynomials are represented as Python functions. Below are a few examples:
```def f(x): return 2 * x**2 + 3 * x - 5
def g(x): return x**3 + 4 * x**2 - 2 * x + 8```
Implement the following functions.

1. Define a function `findK()` that takes two inputs, a function `f` and a positive integer `k`. If there exists a polynomial of the form f(x) = ak xk + ... + a1 x + a0 that represents the function `f`, the function should return a vector (ak, ..., a1, a0) containing the coefficients of the polynomial. Otherwise, it should return `None`.
```def f(x): return x**3 + 4 * x**2 - 2 * x + 8
findK(f, 3) # Should return (1, 4, -2, 8).```
2. Define a function `find()` that takes a single input, a function `f`. If for any k there exists a polynomial of the form f(x) = ak xk + ... + a1 x + a0 that represents the function `f`, the function should return a vector (ak, ..., a1, a0) containing the coefficients of the polynomial. Otherwise, it should return `None`.
```def f(x): return x**3 + 4 * x**2 - 2 * x + 8
find(f) # Should return (1, 4, -2, 8).```
Try to make your implementation of `find()` as efficient as possible.