5.5. Assignment #5: Approximations and Linear Transformations (back to full lecture notes)

In this assignment you will solve problems involving overdetermined systems and linear transformations.

Please submit a single file a5.* containing your solutions. The file extension may be anything you choose; please ask before submitting a file in an exotic or obscure file format (plain text is preferred).

  1. For each of the linear transformations f defined below, determine the following.
    • What are the domain and codomain?
    • Is it injective? If it is, provide a step-by-step argument. If not, provide a counterexample.
    • Is it surjective? If it is, provide a step-by-step argument. If not, provide a counterexample.
    • Is it bijective? Explain why or why not.
    • What is dim(im(f))? Your answer must be an integer.

    1. The linear transformation f : R3R2 where:
      f(v)
      =
       
      1 2 0
      2 4 1
       
      v

    2. The linear transformation f : R2R2 where:
      f(v)
      =
       
      1 0
      0 0
       
      v
    3. The linear transformation f : R5R1 where:
      f(v)
      =
       
      0 0 0 1 2
       
      v
    4. The linear transformation f : R2R2 where:
      f(v)
      =
       
      0 a
      a 0
       
      v      where a ≠ 0
  2. In this problem, you will practice finding the least-squares approximate solutions to overdetermined systems.

    1. Find the least-squarse approximate solution to the following equation, and compute the error of that solution:
       
      1 -2
      -2 4
       
       
      x
      y
       
      =
       
      1
      5
       
    2. Suppose you are given the following polynomial:
      f(x)
      =
      x2 - 2 x + 6
      Find the best-fit curve in the space {f | f(x) = a x + b, a,b R} for the above polynomial using the x values {-1, 0, 2}.
    3. Suppose you are given the following data points:
       
      1
      2
       
      ,
       
      0
      1
       
      ,
       
      -1
      0
       
      ,
       
      -2
      3
       
      Find the best-fit curve in the space {f | f(x) = a x2 + b x + c, a,b,c R} for these data points.
  3. Two engineers are trying to find the best-fit curve in the space { f | f(x) = a x + b, a,b R } for a collection of 100 data points of the form (xi, yi) for i {1,...,100}, but that collection is split across two databases of 50 points each. Each engineer has access to only one of the databases. Symbolically, the overdetermined system they are trying to solve is represented using the following equation:
     
    x1 1
    x100 1
     
     
    a
    b
     
    =
     
    y1
    y100
     
    Suppose the two column vectors [x1; ...; x100] and [1; ...; 1] of the matrix are orthogonal to one another (but not necessarily unit vectors). Then, the first thing they need to do is project the vector of [y1; ...; y100] onto the two column vectors of the matrix. Each engineer computes the following values using the data available to them:
    ||
     
    x1
    x50
     
    ||
    =
    3
        
        x1y1 + ... + x50y50
    =
    62
        
        y1 + ... + y50
    =
    120
    ||
     
    x51
    x100
     
    ||
    =
    4
        
        x51y51 + ... + x100y100
    =
    38
        
        y51 + ... + y100
    =
    80
    1. Once the engineers compute the projection of [y1; ...; y100] onto span of the vector [x1; ...; x100], they collectively obtain some vector of the form:
      s
       
      x1
      x100
       
      =
      orthogonal projection of
       
      y1
      y100
       
      onto
       
      x1
      x100
       
      for some s. What is s? Your answer must be an integer.
    2. Once the engineers compute the projection of [y1; ...; y100] onto span of the vector [1; ...; 1], they collectively obtain some vector of the form:
      t
       
      1
      1
       
      =
      orthogonal projection of
       
      y1
      y100
       
      onto
       
      1
      1
       
      for some t. What is t? Your answer must be an integer.
    3. What are the coefficients a and b of the best-fit line f(x) = a x + b for the data? Your answers should be integers.
  4. In this course, we learned how to find a solution to an overdetermined system such that the solution has the smallest possible error. However, sometimes a system is underdetermined, and we want to find the solution with minimal cost for some definition of cost. In this problem, you will devise a method for doing so using some of the techniques we have used to solve overdetermined systems. Consider the following underdetermined system:
     
    1 3
    2 6
     
     
    x
    y
     
    =
     
    10
    20
     
    1. Define the solution space to the above system; you must use set notation. We will call this space S.
    2. What is shortest vector in S? Recall that the length of a vector is its distance from the origin. How can you use orthogonal projection to determine which vector in S is the shortest?

    3. Suppose that the cost of a solution vector v to the above system is defined to be ||v||. What is the solution to the above system that has the lowest cost?
  5. Suppose you are assembling a processing plant that generates electricity and produces biofuel as a byproduct. You can purchase any number of each of the following two types of generators:
    • generators of type A produce 4 units of electricity for every 1 unit of biofuel produced;
    • generators of type B produce 8 units of electricity for every 2 units of biofuel produced.
    Furthermore, in order for the generators to work, each generator must be connected to every other generator of the same type as well as a central controller, and connections cost $4. As a result, the connection cost for each kind of generator is computed as follows:
    • when you buy x generators of type A, each generator of type A costs 4 ⋅ x dollars;
    • when you buy y generators of type B, each generator of type B costs 4 ⋅ y dollars.
    If you must generate exactly 40 units of electricity and 10 units of biofuel while paying the least connection cost possible, how many of each kind of generator should you purchase?