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

In this assignment you will solve problems involving vector spaces and vector spaces of polynomials. Please submit a single file a4.* 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 or PDF are preferred).

You can use the following form to compute the rref using WolframAlpha:

    1. Explain in detail why the following formula is true for any a R and b R if a ≠ 0 and b ≠ 0:
      span {
       
      a
      b
       
      ,
       
      a+1
      b
       
      }
      =
      span {
       
      1
      0
       
      ,
       
      0
      1
       
      }
      This can be done in multiple ways. One way is to show that the two vectors on the left-hand side are linearly independent. Suppose they are linearly dependent. Then there exists s R such that:
       
      a
      b
       
      =
      s
       
      a+1
      b
       
      a
      =
      s ⋅ (a + 1)
      s
      =
      a / (a + 1)
      b
      =
      sb
      s
      =
      1
      a / (a + 1)
      =
      1
      s
      s
      Since assuming that they are linearly dependent leads to the contradiction above, they must be linearly independent. Alternatively, we can show that the following matrix is invertible:
      det 
       
      a a + 1
      b b
       
      =
      ab - b ⋅ (a+1)
      =
      b ( a - a - 1)
      =
      b ⋅ (-1)
      b
      0
      det 
       
      a a + 1
      b b
       
      0
      Thus, the span of its columns is all of R2.
    2. Assume addition and scalar multiplication of curves in R2 are defined in the usual way as follows:
      f + g = h
          
      where      h(x) = f(x) + g(x)
      sf = h
          
      where      h(x) = sf(x)
      Find a basis of the following vector space:
      { f  |  f(x) = a ⋅ 2x+2 + b ⋅ 2x + c x where a,b,c R }

      The space of curves defined above can be defined as the set of linear combinations of the following three curves:
      f(x)
      =
      2x+2
      g(x)
      =
      2x
      h(x)
      =
      x
      However, {f, g, h} is not a basis because f and g are linearly dependent:
      f
      =
      4 ⋅ g
      f(x)
      =
      4 ⋅ g(x)
      2x+2
      =
      4 ⋅ 2x
      2x+2
      =
      22 ⋅ 2x
  1. Find an orthonormal basis of each of the following spaces. Please show your work.

    1. The line L defined by:
      L
      =
      {
       
      x
      y
       
       |  y = -3 x }

      Since L is a line, dim L = 1, so it is sufficient to find a single unit vector that spans L. Any vector on the line sufficies. If x = 1, then y = -3, so we can say:
      L
      =
      span {
       
      1
      -3
       
      }
      ||
       
      1
      -3
       
      ||
      =
      √(12 + (-3)2)
      =
      √(10)
      Thus, the orthonormal basis for L is:
      L
      =
      span {
       
      1/√(10)
      -3/√(10)
       
      }
    2. The space V defined by:
      V
      =
      span {
       
      1
      2
      0
      3
       
      ,
       
      1
      0
      3
      1
       
      ,
       
      2
      0
      0
      0
       
      ,
       
      1
      -2
      0
      -3
       
      }

      First, we note that the last vector is a linear combination of two other vectors:
       
      1
      -2
      0
      -3
       
      =
       
      2
      0
      0
      0
       
       
      1
      2
      0
      3
       
      None of the remaining three vectors are a linear combination of the other two, so we have found a basis:
      basis V
      =
      {
       
      1
      2
      0
      3
       
      ,
       
      1
      0
      3
      1
       
      ,
       
      2
      0
      0
      0
       
      }
      Alternatively, we could have found a basis by computing the following rref and keeping only the non-zero rows as the basis:
      rref
       
      1 2 0 3
      1 0 3 1
      2 0 0 0
      1 -2 0 -3
       

      We can now apply the Gram-Schmidt process to find an orthonormal basis:
      u1
      =
       
      2
      0
      0
      0
       
      e1
      =
       
      1
      0
      0
      0
       
      u2
      =
       
      1
      2
      0
      3
       
      − (
       
      1
      2
      0
      3
       
       
      1
      0
      0
      0
       
      ) ⋅
       
      1
      0
      0
      0
       
      =
       
      0
      2
      0
      3
       
      e2
      =
       
      0
      2/√(13)
      0
      3/√(13)
       
      u3
      =
       
      1
      0
      3
      1
       
      − (
       
      1
      0
      3
      1
       
       
      1
      0
      0
      0
       
      ) ⋅
       
      1
      0
      0
      0
       
      − (
       
      1
      0
      3
      1
       
       
      0
      2/√(13)
      0
      3/√(13)
       
      ) ⋅
       
      0
      2/√(13)
      0
      3/√(13)
       
      =
       
      0
      0
      3
      1
       
       
      0
      6/13
      0
      9/13
       
      =
       
      0
      −6/13
      3
      4/13
       
      e3
      =
      √(1573/169) ⋅
       
      0
      −6/13
      3
      4/13
       

    3. The plane in R3 orthogonal to the vector v where:
      v
      =
       
      1
      0
      2
       

      We must first find a basis for the plane P, which we can define as:
      P
      =
      { w | wv = 0 }
      =
      {
       
      x
      y
      z
       
      | 1 ⋅ x + 0 ⋅ y + 2 ⋅ z = 0 }
      To find one vector on the plane, we simply use the equation in the definition above:
      x + 2 ⋅ z
      =
      0
      x
      =
      −2 ⋅ z
      x
      =
      −2      (we choose x as the independent variable and assign a value to it)
      y
      =
      2      (since y can be anything, we choose something convenient)
      z
      =
      1      (this is determined by the equation)
      Next, we want to find another vector in the plane. Since we are looking for an orthonormal basis, we look for a vector that is orthogonal to the one we already found above. Thus, we must solve a system of two equations:
       
      x
      y
      z
       
       
      1
      0
      2
       
      =
      0
       
      x
      y
      z
       
       
      −2
      2
      1
       
      =
      0
      x + 2 ⋅ z
      =
      0
      −2 x + 2 y + z
      =
      0
      x
      =
      2      (we choose x as the independent variable and assign a value to it)
      y
      =
      5/2
      z
      =
      −1
      Thus, we now have two orthogonal vectors. It suffices to normalize both of them:
      V
      =
      span {
       
      −2
      2
      1
       
      ,
       
      2
      5/2
      −1
       
      }
      =
      span {
       
      −2/3
      2/3
      1/3
       
      ,
       
      4/(3 √(5))
      5/(3√(5))
      −2/(3/√(5))
       
      }
  2. For each of the following, find the exact polynomial (i.e., the natural number representing the degree of the polynomial and its real number coefficients).

    1. The input box below takes as input a space-separated list of real numbers. Clicking evaluate outputs the result of computing f(x) for each of the numbers x in the list.
      Suppose that the following is true:
      f
      { f  |  f(x) = a x2 + b x + c where a,b,c R }
      Find the coefficients of the polynomial f being computed by the box above. Explain how you obtained your result (write out the equations).
      It is sufficient to sample the polynomial at three points and then to solve for its coefficients:
       
      (0)2 (0) 1
      (1)2 (1) 1
      (2)2 (2) 1
       
       
      a
      b
      c
       
      =
       
      f(0)
      f(1)
      f(2)
       
      =
       
      20
      19
      12
       
       
      a
      b
      c
       
      =
       
      -3
      2
      20
       
      Any valid method or tool can be used to solve the equation, but the equation must be specified. Note that the sampled points may vary; this is fine as long as the coefficients match the points that were being used to fit the curve (that is, solutions with different coefficients should be accepted as long as the initial points and curve oefficients and mutually consistent).
    2. The input box below takes as input a space-separated list of real numbers. Clicking evaluate outputs the result of computing f(x) for each of the numbers x in the list. The only information available to you is that f is a polynomial; it has some degree k, but that degree is unknown to you.
      Find all the coefficients of the polynomial f being computed by the box above. Explain how you obtained your result (justify your answer by appealing to properties of polynomials and write out the equations).
      This problem can be approached by repeatedly falsifying hypotheses about the polynomial until a hypothesis that cannot be falsified is reached.

      First, suppose that the polynomial for the curve has degree k = 1 (i.e., it is of the form a x + b). Then it should be possible to fit a line (a polynomial of the form a x + b) exactly to three points on the curve. If this is not possible, then the curve's polynomial has degree greater than k = 1. By following this process, we find that an exact solution exists for 6 points and k = 5.

  3. Let polynomials in F = {f | f(t) = a t2 + b t + c } represent a space of possible radio signals. To send a vector v R3 to Bob, Alice sets her device to generate the signal corresponding to the polynomial in F whose coefficients are represented by v. Bob then has his receiver sample the radio signals in his environment at multiple points in time t to retrieve the message.
    1. Suppose Alice wants to transmit the following vector v R3 to Bob:
      v
      =
       
      -2
      1
      3
       
      Alice sets her radio transmitter to generate a signal whose amplitude as a function of time is:
      f(t)
      =
      -2 t2 + t + 3
      Suppose Bob wants to recover the message sent by Alice. At how many values of t should Bob sample the signal to recover Alice's message? Write out the computation Bob would perform to recover the message v from Alice.
      Bob would need to sample the signal at three (3) distinct points, e.g. t {0,1,2}. Bob would then solve the following equation:
       
      (0)2 (0) 1
      (1)2 (1) 1
      (2)2 (2) 1
       
       
      a
      b
      c
       
      =
       
      f(0)
      f(1)
      f(2)
       
       
      0 0 1
      1 1 1
      4 2 1
       
       
      a
      b
      c
       
      =
       
      3
      2
      −3
       
       
      a
      b
      c
       
      =
       
      −2
      1
      3
       
    2. Suppose Bob samples the signals at t {1,2,3} and obtains the vectors listed below. What vector in R3 did Alice send? Show your work.
      {
       
      1
      1
       
      ,
       
      2
      −3
       
      ,
       
      3
      −11
       
      }
      Bob would need to solve the following equation:
       
      (1)2 (1) 1
      (2)2 (2) 1
      (3)2 (3) 1
       
       
      a
      b
      c
       
      =
       
      1
      −3
      −11
       
       
      a
      b
      c
       
      =
       
      −2
      2
      1
       
      The solution can be obtained by solving a system of equations, by computing the rref of an augmented matrix, or any other valid method
    3. Suppose the environment contains noise from other communication devices; the possible signals in this noise are always from the span of the following polynomials:
      g(t)
      =
      2 t − 2
      h(t)
      =
      t2 + 3 t
      Alice and Bob agree that Alice will only try to communicate to Bob one scalar r R at a time. They agree on a unit vector u R3 ahead of time. Any time Alice wants to send some r R to Bob, she will have her device generate the signal corresponding to the polynomial represented by ru. If the vectors below represent the samples collected by Bob, what scalar was Alice sending to Bob?
      {
       
      1
      3
       
      ,
       
      2
      9
       
      ,
       
      3
      13
       
      }

      To allow Bob to distinguish Alice's signal from the noise, Alice must choose a signal that is linearly independent from the two noise signals. While Alice and Bob could theoretically agree on any linearly independent vector (as long as it is linearly independent, a correct solution is possible), the computions are easiest if the vector is orthogonal to the span of the two noise vectors. The two noise polynomials can be represented as vectors in R3, and the noise plane P can be defined as their span:
      P
      =
      span {
       
      0
      2
      −2
       
      ,
       
      1
      3
      0
       
      }
      We want to find a unit vector orthogonal to the plane P. It is sufficient to find a solution to the following system of equations:
       
      0
      2
      −2
       
       
      x
      y
      z
       
      =
      0
       
      1
      3
      0
       
       
      x
      y
      z
       
      =
      0
      ||
       
      x
      y
      z
       
      ||
      =
      1
      Solving the above yields the vector:
      u
      =
      (1/√(11)) ⋅
       
      −3
      1
      1
       
      Next, we must determine the coefficients of the curve Bob observed. This curve is a linear combination of the noise polynomials and Alice's polynomial (Alice's polynoial is represented by u).
       
      (1)2 (1) 1
      (2)2 (2) 1
      (3)2 (3) 1
       
       
      a
      b
      c
       
      =
       
      3
      9
      13
       
       
      a
      b
      c
       
      =
       
      −1
      9
      −5
       
      Finally, we must remove the contribution of the noise vectors from the observed vector in order to isolate Alice's signal. There are two ways to approach this (they are equivalent). One approach is to find the orthogonal projection of the observed vector onto the span of the noise vectors, and then to subtract this projection from the observed vector. Another approach is to project the observed vector directly onto span {u}; we use the latter.
      (
       
      −1
      9
      −5
       
      ⋅ (1/√(11)) ⋅
       
      −3
      1
      1
       
      ) ⋅ (1/√(11)) ⋅
       
      −3
      1
      1
       
      =
       
      −21/11
      7/11
      7/11
       
      Since u is a unit vector, the above vector's length represents the scalar by which u was multiplied, so its length is the scalar s in su.
      s
      =
      ||
       
      −21/11
      7/11
      7/11
       
      ||
      =
      √(539)/11
    4. Suppose there is no noise in the environment. Alice, Bob, and Carol want to send individual scalars to one another at the same time: all three would be sending a signal simultaneously, and all three would be listening at the same time:
      • Alice's device would generate a signal corresponding to a scalar multiple of f(x) = 2 x + 1;
      • Bob's device would generate a signal corresponding to a scalar multiple of g(x) = -x2 + 1;
      • Carol's device would generate a signal corresponding to a scalar multiple of h(x) = x2 - 3 x.
      Suppose you sample the radio signals at a given moment and obtain the vectors below. Determine which scalars Alice, Bob, and Carol are each transmitting. Your answer can be in the form of a vector, but you must specify which scalar corresponds to which sender.
      {
       
      0
      5
       
      ,
       
      1
      7
       
      ,
       
      2
      7
       
      }

      We can set up the following equation, where a, b, and c are the scalars being transmitted by Alice, Bob, and Carol, respectively:
      a
       
      f(0)
      f(1)
      f(2)
       
      + b
       
      g(0)
      g(1)
      g(2)
       
      + b
       
      h(0)
      h(1)
      h(2)
       
      =
       
      5
      7
      7
       
       
      f(0) g(0) h(0)
      f(1) g(1) h(1)
      f(2) g(2) h(2)
       
       
      a
      b
      c
       
      =
       
      5
      7
      7
       
       
      1 1 0
      3 0 −2
      5 −3 −2
       
       
      a
      b
      c
       
      =
       
      5
      7
      7
       
      Using any valid method for solving the equation above, we get:
       
      a
      b
      c
       
      =
       
      3
      2
      1
       
      An alternative approach is to first determine the polynomial being observed by setting up an equation, finding the exact curve that fits the three points provided, and then setting up a second matrix equation to determine what linear combination of the three signal polynomials adds up to the curve that fits the three points.