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):
        lead = 0
        if lead >= cols: return soln(M)
        i = r
        while M[i][lead] == 0:
            i += 1
            if i == rows:
                i, lead = r, lead + 1
                if cols == lead: return soln(M)
        while abs(M[r][lead]) < epsilon: lead += 1
        if abs(M[r][lead]) > epsilon:
            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.