• Corrected Office Hours: I will not be having office hours this semester on Mondays 1:50-2:50. My other office hours are unchanged.

Section and page numbers refer to Messer.

• Proof due 1/19: A pure magic square of order n is an arrangement of the numbers 1,2,...,n² into an n × n array so that every row and column and the two main diagonals have the same sum. For example, a magic square of order 4 appears in Dürer's famous picture Melancholia:

  16	3	2	13
  5	10	11	8
  9	6	7	12
  4	15	14	1

  This satisfies 16+3+2+13 = 34 and similarly for every row and column, and 16+10+7+1 = 34 and similarly for the other diagonal.
  Problem: Prove that there is a unique pure magic square of order 3, up to rotation and reflection: that is, there is only one such 3 × 3 square together with its turns and flips. You are not just supposed to produce the square, but give a convincing argument that there are no others, taking into account all possible cases.
  Hint: There are two basic approaches.
  • The combinatorial method is to determine the entries one by one, starting with the center number, and eventually eliminating all but one possibility (along with its turns and flips).
  • The algebraic method is to solve a system of 8 linear equations in 9 variables, then find exactly which of these solutions is in positive integers, then determine which of these have all the numbers 1--9. Extra credit for working out this one: it is hard.
  Note: I expect your own work, without internet help, though you are welcome to work in teams.
  Solution (latex). I used Marijo Wohlfert's proof.

• Reading 1/10: 2.1 Linear Equations
  HW 1/10: Write and solve a linear system for each problem.
  1. I have $1 worth of nickels and dimes, with 14 coins in all. How many nickels and dimes?
  2. Each pair of equations defines two lines. For each pair, find the intersection points of the two lines (if any), and sketch the lines to verify your result.
     1. 3x - 2y = 1 and 5x + 4y = 2.
     2. 3x - 2y = 1 and -9x + 6y = 2
     3. 3x - 2y = 1 and -9x + 6y = -3
  3. Find the intersection point of the planes x + y = 1,   x + z = 2,   y + z = 3.
  4. At the pet store, dogs are $15, cats are $1, mice are 25¢. What are all the ways to buy 100 animals for $100?
  5. Extra Credit: Find a general formula for the intersection point of lines ax + by = p and cx + dy = q , in terms of the constants a,b,c,d,p,q. When are the lines parallel, so that there is no solution?
  Answers (to check your solution): 1. 8 nickels, 6 dimes.
  2a. (x,y) = (4/11, 1/22), unique solution: the lines intersect (cross each other) at one point.
  b. Adding three times the first equation to the second equation gives 0 = 5, which is never be true, so there is no solution to the system. The lines are parallel, and never cross.
  c. Any solution of the first equation is a solution of both, and the solution set is {(x, 3x/2 - 1/2) for x any real number}. These are two equations for the same line.
  3. (x,y,z) = (0,1,2).   4. The real-number solutions are: m arbitrary, d = 3m/56, c = 100 - 59m/56. The positive whole number solutions are: (d,c,m) = (0,100,0) or (3,41,56).

• Reading 1/12: 2.2 Gaussian Elimination
  HW 1/12: p.75 #5bd, 6bd, 9.
  Solve each system by Gaussian elimination. Each equation corresponds to a line in R². Visualize how these lines meet to understand the solution.
  1.   x + y = 1
     x - y = 0
     x + 2y = 1
  2.   x + y = 1
     x - y = 0
     x -3y = -1
  3.   x + y = 1
     2x + 2y = 2
     -x - y = -1
  4. Extra Credit: The unit square is the set of points (x,y) in the plane R² such that each coordinate x and y lies between 0 and 1. In set notation: S = {(x,y) ∈ R² such that 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1} A vertex (corner) of the square is where each of the coordinates equals 0 or 1; and a side is the set where just one of the coordinates equals 0 or 1. There are 4 vertices (0,0), (0,1), (1,0), (1,1); and 4 sides (0,y), (1,y), (x,0), (x,1). Here (x,1) means {(x,1) ∈ R² s.t. 0 ≤ x ≤ 1} , etc.
     1. Describe the unit cube in R³ analogously to the above, and list the 0D vertices, 1D edges, and 2D faces. How many of each?
     2. Define the unit 4D hypercube in R⁴ analogously. Find how many 0D vertices, 1D edges, 2D faces, and 3D hyperfaces. Note that although we cannot picture this object very well, we can deduce quite a bit about it.
     3. We can notch a wire into 4 equal segments and bend it into (the perimeter of) a square. Similarly, we can put six squares into a cross pattern, and fold it up into (the surface of) a cube. Draw or build a multi-cross shaped union of cubes which could fold up into (the 3D outside of) a 4D hypercube (if we could only fold in the right direction).
     4. Can you go further, and find how many d-dimensional faces in a 5-dimensional hypercube? An n-dimensional hypercube?
  Answers: 1. More equations than variables, so no solutions, as expected. Geometry: three lines in the plane form a triangle and have no common point.
  2. More equations than variables, but a redundant equation, so one solution, no free variables. Geometry: solution set is a point, the intersection of three lines forming a star (asterisk).
  3. More equations than variables, but two redundant equations, so one free variable y: Geometry: three lines are identical, so their intersection is the same line, which is the solution set.
  4. You can look this up easily, but it's much more fun to do it yourself. See also Salvador Dali's painting Crucifixion.

• Reading 1/14: 2.3 Solving Linear Systems
  HW 1/14: p.79 #1b, 2d, 4ab, 5b, 7d.
  Solve each system by Gaussian elimination. Each equation corresponds to a plane in R³. Visualize how these planes meet to understand the solution.
  1.   x + y + z = 1
     x - y + 2z = 1
  2.   x + y + z = 1
     x + y + 2z = 2
  3.   x - y + z = 1
     -2x + 2y - 2z = -2
  4.   x - y + z = 1
     -2x + 2y - 2z = 1
  5.   x + y + z = 1
     y - z = 2
     x - y - z = 3
  6.   x + y + z = 1
     y - z = 2
     x - y + 3z = -3
  Answers: 1. Leading (pivot) variables x, y, free variable z. Geometry: solution set is a line, the intersection of two planes in space.
  2. Leading variables x, z, free variable y. Geometry same as previous.
  3. Leading variable x, free variables y,z, due to redundant equation. Geometry: solution set is a plane, since the two planes are identical.
  4. Leading variable x and inconsistent equation, so no solution. Geometry: solution set is empty because equations define parallel planes in space.
  5. Leading variables x,y,z, no free variables, so unique solution. Geometry: solution set is a point, the intersection of three planes in space (similar to the xy, xz, yz coordinate planes intersecting at the origin).
  6. Leading variables x,y, free variable z, due to redundant equation. Geometry: solution set is a line, the intersection of three planes surrounding it like a paddle-wheel.

• Reading 1/19: 1.1 Sets and Logic
  HW 1/19: p.7 #2,5,7.
  Logical operations.
  • Given statements P, Q, R, etc. (which may be true or false in any given instance), we can combine them to make various compound statements: P OR Q;   P AND Q. Also P ⇒ Q, meaning: if P then Q. We can also take the negated or opposite statements: NOT(P), etc.
  • If P is the statement "x ∈ A", Q is "x ∈ B", and R is "x ∈ C" (that is, x is an element of set A, B, or C), then the compound statements correspond to set operations or relations. For example, P OR Q corresponds to A ∪ B = {x s.t. x ∈ A OR x ∈ B}, and P ⇒ Q corresponds to A ⊂ B, which means x ∈ A ⇒ x ∈ B. Also, NOT(P) corresponds to the set complement A = {x ∈ U s.t. x ∉ A}, where U means a universal set containing A.
  • Doing several logical operations gives rise to equivalent forms. Example: NOT(P AND Q)   is equivalent to   NOT(P) OR NOT(Q). That is, these two forms are both true or both false (depending on whether P, Q are true/false).
    An instance of this equivalence in everyday language: "I am not loud and obnoxious" means the same as: "I am not loud or not obnoxious."
    Furthermore, this logical equivalence implies the set equality: A ∩ B = A ∪ B .
  
  Problem: For each of the following compound statements, give: (a) an equivalent form; (b) a plausible everyday instance of this equivalence; (c) a corresponding statement about sets.
  1. NOT(P OR Q)
  2. NOT(P ⇒ Q)
  3. P AND (Q OR R)
  4. P OR (Q AND R)
  5. P ⇒ (Q AND R)
  6. (P OR Q) ⇒ R
  7. NOT(P) ⇒ NOT(Q)
  8. Extra Credit: Can you do the same for P ⇒ (Q OR R) or for (P AND Q) ⇒ R ? Are there any other basic rules for logical equivalence?
  Answers A. NOT(P) AND NOT(Q)   B. P AND NOT(Q)   C. (P AND Q) OR (P AND R)   D. (P OR Q) AND (P OR R)   E. (P ⇒ Q) AND (P ⇒ R)   F. (P ⇒ R) AND (Q ⇒ R)   G. Q ⇒ P

• Proof due 1/24: Do p.8 #7 as a formal proof by induction. That is, guess a formula a_n for the number of subsets of a set with n elements. For example, the set {} with no elements has one subset (itself), so a₀ = 1; and any set with one element has two subsets (the empty set and itself) so a₁ = 2.
  Now let P_n be the statement "Any set with n elements has a_n subsets." Prove this statement by Mathematical Induction (Sec 7.1, p.265): that is, first prove the anchor statement P₀ directly, then for every n show the link step, the implication P_n ⇒ P_n+1. Together, these imply P_n for every n ≥ 0.

• Reading 1/21: 7.1 Mathematical Induction
  HW 1/21: p.271 #1, 3, 5, 12.
  1. Prove by induction: 1 + 3 + 5 + ... + (2n-1) = n²
  2. Discover the formula for 1³ + 2³ + ... + n³ = p(n) as follows. It should be a polynomial p(n) = a + bn +cn² + dn³ + en⁴. Try to do the inductive proof, and determine the unique coefficients a,b,c,d,e for which the proof will work.
  3. Extra Credit: Find direct, non-inductive proofs for any of the above formulas.
  4. Extra Credit: Find the mistake in the following use of induction, which "proves" a statement which is obviously false.

     False Proposition: All the crayons in any box are the same color.
     False Proof: Let S_n be the statement: "In any box with n crayons, all the crayons have only one color." We prove this by induction.
     Anchor step S₁: If there is only 1 crayon in the box, then all crayons in the box do have only one color.
     Link step: Assume we already know S_n holds. Take any box with (n+1) crayons, and remove the last crayon. By the assumption S_n, all these first n crayons have only one color (say, red). Now put the last crayon back in, and take out the first crayon. By the assumption S_n, these last n crayons also have only one color. That is, the last crayon has the same color as any middle crayon, which we already know is red. Thus, the first, middle, and last crayons are all red. Therefore all the (n+1) crayons have only one color (red or whatever), and we conclude S_n+1 holds.
     From the anchor and link steps, we deduce that S₁ is true, which implies S₂ is true, which implies S₃ is true, etc., meaning any box with any number of crayons has only one color.

     Now, we can obviously have a box with different color crayons, so the proof cannot be valid. Could it be that induction is nonsense, or that it only applies to mathematical situations? In fact, there is just one very specific place where the argument is false.

• Reading 1/24: 1.2 Definition of a Vector Space
  HW 1/24: In class we saw how composition and scaling of motions in the plane lead to the natural definition of vector addition and scalar multiplication. Namely, if we represent two vectors by pairs of numbers (a,b) and (c,d), then we define: (a,b) + (c,d) = (a+c, b+d)     and      r (a,b) = (ra, rb). This is the motivating case of a vector space, and its essential algebraic properties are the Axioms 1-8 on p.9. Later, we will consider other math structures which are similar: they have their own definitions of additon and scalar multiplication satisfying all the Axioms. However, it is not easy to define such structures. Small changes make the axioms fail.

  Below, I give some sets V with their own special definitions of vector addition and scalar multiplication. See whether these are actually vector spaces. For each problem, go through Axioms 1-8, and determine which (if any) is violated.

  1. V = R² = {(a,b) s.t. a,b ∈ R} with the natural operations: (a,b) + (c,d) = (a+c, b+d) and r(a,b) = (ra, rb).
     Answer: We check each Axiom. Axiom 1 (additive commutativity): by definition, we have (a,b) + (c,d) = (a+c, b+d), and also (c,d) + (a,b) = (c+a, d+b). Since a+c = c+a and b+d = d+b for real numbers a,b,c,d, the two vector quantities are equal. We do not need to justify the commutativity of real numbers: we assume this known from previous study. Similarly, Axiom 2 (additive associativity) follows from associativity for real numbers, and it is the same with the other Axioms (but I still expect you to write them out).
  2. V = {(a,b) s.t. a,b ≥ 0} with the same operations as above.
     Answer: V is now a different set, and the Axioms do not all hold. Axioms 1 & 2 are automatic, since they are special cases of the previous case of Prob 1. Axiom 3 is OK, since 0 = (0,0) ∈ V. But Axiom 4 breaks down: for every vector v ≠ 0, there is no negative vector w = -v ∈ V, no way to get v + w = 0 for w ∈ V. It does not help that there is a negative in R². And there is an even bigger problem: scalar multiplication can take a vector out of V, for example (-1)(1,1) = (-1,-1), ∉ V.
  3. V = {(a,b) s.t. a,b ∈ R} with the operations: (a,b) + (c,d) = (a+c, b+d) and r(a,b) = (|r|a, |r|b), where |r| means absolute value.
     Answer: This is the same set as in (1), but with a new, strange definition of scalar multiplication. That is, we forget the usual definition of scalar multiplication, and ask if the Axioms hold with this strange definintion.
     Axioms 1 - 4 all work, since they involve only vector addition, which is the same as Prob 1. To check Axiom 5, we work out, according to the definition: r( (a,b) + (c,d) ) = (|r|(a+c), |r|(b+d)) and r(a,b) + r(c,d) = (|r|a + |r|c, |r|b + |r|d), which are indeed equal: thus Axiom 5 holds for these operations. Note we have used the new definition of r v, forgetting the old definition.
     However Axiom 6 breaks down: for example (1+(-1))(1,0) = 0(1,0) = (|0|1, |0|0) = (0,0), but 1(1,0) + (-1)(1,0) = (1,0) + (|-1|1,|-1|0) = (2,0). Since (0,0) ≠ (2,0), the Axiom fails in the case r = 1, s = -1, v = (1,0), so it is false. Note that a single of example of failure (a counter-example) is enough to make the general Axiom false.
  4. V = {(a,b) s.t. a,b ∈ R} with the strange operations: (a,b) + (c,d) = (a+d, b+c) and r(a,b) = (ra,rb).
     Answer: Axioms 1, 2, 6 break down. For example, Axiom 6: (r + s)(a,b) = (ra + sa, rb + sb), whereas r(a,b) + s(a,b) = (ra,rb) + (sa, sb) = (ra + sb, rb + sa), which is quite different.
  5. V = R with the usual addition and multiplication of numbers.
     Answer: Here the Axioms clearly hold by our previous knowledge. This space can be pictured in terms of arrows the same way as R² and R³: identify each point with the arrow from 0 to that point, and consider addition as laying arrows end-to-end.
  6. V = {a ∈ R s.t. a > 0}. Let us use a + b and ab to denote the usual operations on numbers, and a⊕b and r⊗a to denote the following new, strange vector operations: for a,b ∈ V, define a⊕b = ab; and for r ∈ R, define r⊗a = a^r (exponentiating a to the power r). Do the Axioms hold?
     Answer: Now a,b ≥ 0 are "vectors" in V. We have a⊕b = ab and b⊕a = ba, which are the same real number, so Axiom 1 holds for the strange addition. Similarly, Axiom 5: r⊗(a⊕b) = (ab)^r = a^rb^r = (r⊗a) ⊕ (r⊗b). In fact, all the Axioms hold. This example can be explained by thinking of v = (a,b) as a "weird label" for the vector v' = (log(a), log(b)) ∈ R². Then the weird operations on V correspond to the usual vector operations on R².
     Extra Credit: There should be essentially only one way to add real numbers. Explain this weird example by finding a one-to-one correspondence T : V → R taking positive reals in V to all reals, such that T(a⊕b) = T(a) + T(b) and T(r⊗b) = r T(b), turning weird addition and multiplication into the usual operations. The correspondence T is called an isomorphism.

• Reading 1/26: 1.9 Lines and Planes
  HW 1/26: p.52 #10,13.
  1. The corners of a unit cube have all coordinates equal to 0 or 1. For example, (1,0,0) and (0,1,1) are opposite corners. Write the four lines going through the four pairs of opposite corners, each in the parametric form L = {t v + p  s.t.  t ∈ R}, where t is a parameter (free variable), v is a direction vector pointing along the line, and p is a base point of the line. Find the point where these four lines meet, and verify your answer using the parametric equations.
  2. Write a parametric form for the plane passing through the points (1,0,0), (1,1,0), (1,1,1). Hint: Find two directions v,w pointing along the plane (i.e. pointing between the 3 points), and write the parametric form {t v + s w + p  s.t.  s,t ∈ R}, having two free variables s,t.
  3. p. 52 #12. Hint: Solve the system of linear equations which define the line, substitute t for the free variable, and write the solution in the form (x,y,z) = t v + p .

• Reading 1/28: 1.7 Function Spaces (p.32-37)
  HW 1/28: p.38 #8, 10. In principle, one can translate any fact in classical geometry into the language of vectors. Here is nice example.
  Consider a triangle in the plane with vertices A,B,C and sides AB, BC, AC.   A median as the line segment from one vertex to the midpoint of the opposite side: for example, if A' is the midpoint of BC, then AA' is one of the medians. A classical theorem says that the three medians of any triangle intersect at a point 2/3 of the way along each median.
  1. Assume a, b, c are the vectors from the origin to A,B,C. Find a parametrized form for the points of the median. Hint: since this is only a segment, the parameter should vary only over the interval 0 ≤ t ≤ 1.
  2. Find a formula for the points 2/3 of the way along each median. Use vector algebra to show these points are all equal. This special point is the centroid or center of gravity of the triangle.

• Proof due 1/31: This is a slightly extended version of HW 1/24 #6. Let V = {(a,b) s.t. a,b > 0}, and define the following weird operations on v = (a,b) and w = (c,d) ∈ V, and r∈R: let v⊕w = (ac, bd) and r⊗v = (a^r, b^r), where the expressions in the coordinates are usual multiplication and exponentiation. Show that V with the operations ⊕ and ⊗ does or does not satisfy the Axioms of a Vector Space. For example:   (1) v ⊕ w = w ⊕ v .   (3) There is some 0 ∈ V with v ⊕ 0 = v for all v .
  Extra Credit: Find a one-to-one correspondence (an isomorphism) T : V → R² with T(v ⊕ w) = T(v) + T(w) and T(r⊗v) = r T(v), where the operations on the right side of each equation are the usual vector addition and multiplication. Can you come up with other weird operations on (subsets of) R² which define a vector space? Hint: There are many, but they are all isomorphic to R².

• Reading 1/31: 1.3 Properties of Vector Spaces, 1.4 Subtraction and Cancellation (p.12-20). See also the Notes below on Constructing Proofs.
  HW 1/31: p. 16 #5. Could there be more than one 0 vector? Assume 0' also satisfies v + 0' = v for all v ∈ V, and prove 0' = 0 .

• Reading 2/4: 1.8 Subspaces (p.39-44). The main point is the Subspace Theorem (p.40): S is a subspace whenever 0 ∈ S and S is closed under the operations, meaning v + w ∈ S and rv ∈ S for every v,w ∈ S. Examples on p.41-44.
  HW 2/4: p.44 #2, 3,7,11,12, 19.
  Determine whether the following S are subspaces of V = F(R) = {all functions f : R → R}.
  1. S = P = {polynomial functions p(x) = a₀ + a₁x + ... + a_nxⁿ  s.t.  n ≥ 0 and a₀,...,a_n ∈ R}
  2. S ={polynomials p(x) of degree exactly n}.
     Recall: the degree of a polynomial is n, where xⁿ is the highest term with non-zero coefficient. Also deg(0) = -∞.
  3. S = P_n = {polynomials of degree n or less}.
  4. S = {polynomials whose degree is an even number n = 0,2,4...}.
  5. S = {even functions f(x)  s.t.  f(-x) = f(x)}.
  6. S = { f(x) = ax² + b cos(x) + c  s.t.  a,b,c ∈ R}.
  7. Extra Credit: Let V be a vector space. We say a set C ⊂ V is convex if for every pair of points v,w ∈ C, the line segment joining them is entirely in C: av + bw ∈ C for all a,b ≥ 0 with a+b=1.
     For a finite set T = {v₁,...,v_n} ⊂ V, the convex hull is: Conv(T) = {a₁v₁ + ... + a_nv_n  st.  a₁,...,a_n ≥ 0 and a₁+...+a_n = 1}. This is the set of weighted averages of the points in T. Show that:
     1. The line segment from v to w is Conv{v,w}. Hint: the line segment starts at v and goes in what direction?
     2. If T consists of n = 3 points, then Conv(T) is the triangle between them. Hint: We may define the triangle ABC to be all the points on line segments AD, where A is a vertex and M is on the opposite segment BC.
     3. Conv(T) is convex.
     4. Conv(T) is the smallest convex set containing T: that is, if T ⊂ C, a convex set, then Conv(T) ⊂ C.
     5. True or false: If V = R², and v = a₁v₁ + ... + a_nv_n ∈ Conv(T), then we may take all but three of the a_i to be 0: that is, the convex hull is covered by triangles. What if V = R³ or Rⁿ ?
     6. How would you define the convex hull of infinitely many points? For example, we should have Conv(Conv(T)) = Conv(T).

• Proof due 2/7: All the parts of Theorem 1.5 p.16. Your proofs may assume only the Axioms (1)-(8) and propositions previously proven in Ch 1.3. You may also use the earlier parts in the proof of the later parts, or choose the order in which you prove the parts. You may NOT assume your vectors have coordinates. The proofs should be very short: not be more than 2 pages for all.

• Reading 2/7: Ch 3.1 (p.91-95)
  HW 2/7: p.88 #10: Write the solution as linear combinations of some vectors.
  p.88 #11: Note that solutions of a system form a subspace if and only if the system is homogeneous (all constants zero).

• Reading 2/9: Ch 3.2 Span (p.97-100). See also Notes below: Idea of coordinates in a vector space.
  HW 2/9: p.95 #3a,c, 4a,e. (Use the Quick Examples, p.93 & 94.)
  Define the following subspace S ⊂ R⁴, the solutions to a homogeneous linear system: S = {(x₁,...,x₄)   s.t   x₁ - x₂ + x₃ - 2x₄ = 0}. Since the ambient space has 4 dimensions of freedom, and S is defined by 1 equation, we expect S to be a space of dimension 4 - 1 = 3. We want to define 3 coordinate axes inside S. (Note that the usual coordinate axes (1,0,0,0), (0,1,0,0),... lie outside S, and so cannot be used as "internal axes".)
  1. Check that the vectors v₁ = (1,0,-1,0),   v₂ = (2,1,1,1),   v₃ = (4,1,-1,1) are all in S. We will explore whether {v₁, v₂, v₃} makes a good choice of coordinate axes.
  2. Check that v = (2,0,0,1) lies in S. Show this v is not a linear combination of the 3 vectors, v ∉ Span{v₁, v₂, v₃}, by the method of p.93. That is, expand the vector equation: v = r v₁ + s v₂ + t v₃ into a system of 3 linear equations in variables (r,s,t), and show there is no solution. Thus, v cannot be reached along the "axes" {v₁, v₂, v₃}.
  3. Check w = (0,1,3,1) lies in S, and show w ∈ Span{v₁, v₂, v₃} by the same method as before. That is, find all solutions (r,s,t) of the corresponding linear system. We consider (r,s,t) to be the coordinates of w along the axes {v₁, v₂, v₃}. Are these coordinates unique? Can you picture what is wrong with this set of axes?
  4. Now solve the linear equation x₁ - x₂ + x₃ - 2x₄ = 0 by the usual Gaussian Elimination method. (There is no elimination, just the last step.) Write S in parametrized form as: S = { r u₁ + s u₂ + t u₃  s.t. r,s,t ∈ R } . Show that every vector v ∈ S can be written in one and only one way as v = r u₁ + s u₂ + t u₃ .
     Hint: Take a general v = (a,b,c,d) and see that there is a unique solution (r,s,t) of the corresponding linear system, which gives the coordinates of v along the axes {u₁, u₂, u₃}. The solution is very simple!
     Conclusion: {u₁, u₂, u₃} is a good set of coordinate axes for S, because any vector has unique coordinates.
  5. Extra Credit: Prove that the Gaussian Elimination method always gives a good set of coordinate axes for the subspace S ⊂ Rⁿ defined by any homogeneous linear system. That is, any vector in S has unique coordinates.

• No Proof due the week of 2/14.

• Reading 2/14: Ch 3.3 Linear Independence (p.103-109).
  HW 2/14:
  • p. 103 #9. Hint: Given a finite set of polynomials, find another polynomial which is not in their span.
  • p 103 #14. Hint: Spell out the definition of Span(v,w) and Span(v+w, v). Show that each is a subset of the other.
  • p. 110 #2, 6. Hint: Show that r₁v₁ + r₂v₂ + ... = 0 only for r₁ = r₂ =...= 0.
  • p. 110 #10. Use Quick Example, p. 106.
  • p. 111 #14.

• Reading 2/16: Ch 3.4 Basis (p.111-113).
  HW 2/16:
  • p.113 #3, 7, 9. Hint: Show that every vector in each space can be written uniquely as a linear combination of the given vectors. This can be done by solving a system of liinear equations.
    In each case, give a second solution by simplifying the given vectors to the standard basis (or a set which is easily seen to be a basis), using Gaussian elimination on columns as in class.
  • Prove the Proposition: In a vector space V, let B = {v₁,...,v_n} be any set of vectors. Let v_i' = r v_i for some scalar r ≠ 0, and define the set B' by substituting v_i' in place of v_i:   B' = {v₁,...,v_i',...,v_n}: that is, we scale one of the vectors in B. Then B is a basis of V if and only if B' is a basis of V.
    Note: This justifies one of the operations for Gaussian elimination on columns.
  • Extra Credit: p.114 #14.

• Proof due 2/21: Proposition: In a vector space V, let B = {v₁,...,v_n} be any set of vectors. Let v_i' = v_i + r v_j for some scalar r and some j ≠ i, and define the set B' by substituting v_i' in place of v_i:   B' = {v₁,...,v_i',...,v_n}: that is, we add to v_i a multiple of one of the other vectors in B. Then B is a basis of V if and only if B' is a basis of V.
  • Prove this using results we have discussed, including the Notes below and Sec 3.1-3.4. Remember basis means spanning and linearly independent. You may use any of the equivalent conditions for these properties, whichever is most convenient.
  • The significance of this proposition is that the same operations of Gaussian elimination on bases which we used on systems of equations can also be done on bases: namely adding a multiple of one vector to another, and obviously also switching two vectors or scaling one vector. We will use this to simplify bases.

• Test 1 Review 2/23:
  1. Determine whether each set of vectors is linearly independent.
     1. V = R⁴: {(0,1,2,3), (3,0,1,2), (2,3,0,1), (1,2,3,0)}.
     2. V = P₂: {(x-1)², (x+1)², (x-2)², (x+2)²}
     3. V = F(R): { (x+1)³, 2^x, |x| }
  2. Show that the following are subspaces, and find a basis for each.
     1. S = {f ∈ P₃   s.t. f(1) = 2f(2)}. Hint: Translate this into an equation on the coefficients.
     2. Span{(1,1,2), (1,0,1),(0,1,1)} ⊂ R³. Hint: Find all linear dependencies av₁ + bv₂ + cv₃ = 0, and eliminate redundant vectors.
  3. Prove or give a counter-example:
     1. For any n, we have 1 + 2 + 2² + ... + 2ⁿ = 2ⁿ⁺¹ - 1 .
     2. If the set of vectors {v,w} is linearly independent, then the set Span{v,w} is also linearly independent.
     3. Consider the FOIL rule for real numbers: (a+b)(c+d) = ac + ad + bc + bd. Find a corresponding rule for vector addition and scalar multiplcation, and give a formal statement of your rule. Prove your rule using only the Axioms of a vector space, justifying each step.

  Answers: 1. In each case, find all solutions (r₁,...,r_n) to r₁v₁ + ... + r_nv_n = 0. If the only solution is (r₁,...,r_n) = (0,...,0), then the set is independent; otherwise a non-zero solution will give a dependency equation. For (a), (b), use standard coordinates to turn the vector equation into a system of linear equations in the variables r₁,...,r_n. For (c), take the vector equation at 3 particular values, say x = 0, 1, -1, which yields 3 linear equations in r₁ ,..., r₃ . Cases (a) and (c) are bases; case (b) is not, as can also be seen from the Dimension Thm: P₂ has dimension 3, so 4 vectors must be dependent.
  2. For each case, check that if two vectors satisfy the definition of S, then their sum also satisfies, and similarly for scalar multiplication. In case (a), the condition on f(x) = a + bx + cx² + dx³ is:

  a + b + c + d = 2(a + 2b + 4c + 8d),   i.e.   a + 3b +7c +15d = 0. Gaussian elimination of the equation the basis is: { x-3 , x²-7 , x³-15 }. in case (b), find all linear dependencies r₁v₁ + r₂v₂ + r₃v₃ = 0, which are in fact: v₁ - v₂ - v₃ = 0. Thus any of the 3 vectors can be dropped without changing the Span, and the remaining 2 vectors are linearly independent.
  3a. Straightforward induction: Use 1 + ... + 2ⁿ = 2ⁿ⁺¹ to prove 1 + ... + 2ⁿ + 2ⁿ⁺¹ = 2ⁿ⁺² - 1.
  b. Not true: the Span contains vectors like w = v₁ + v₂, which has the dependency w - v₁ - v₂ = 0. Even simpler, the Span contains w = 0, which is linearly dependent all by itself!
  c. Interpret the FOIL rule as: (r + s)(v + w) = rv + rw + sv + sw, where r,s ∈ R and v,w ∈ V. This is proved by successively applying the distributive laws, Axioms 5 & 6.

• Extra Credit: Recall from Test 1 the following:
  Proposition: Given a set of vectors B = {v₁,...,v_n}, define the set C= {w₁,...,w_n}, where w₁ = v₁ and w_i = v_i-1 + v_i for i ≥ 2. If B is linearly independent, then C is also linearly independent.
  Problem: Inductively prove this statement P_n for n = 1,2,3,.... The anchor step is trivial. For the link step, the main problem is the logical structure. The Inductive Hypothesis is P_n: If B_n is lin indep, then C_n is lin indep, where B_n , C_n denote the appropriate n-element sets. Now consider a linearly independent B_n+1 having an extra vector v_n+1 , which defines an extra w_n+1 , and suppose that 0 = s₁w₁ + ... + s_nw_n + s_n+1w_n+1 .
  You must now show, using all the assumptions so far, that s₁ = ... = s_n = s_n+1 = 0.

• Reading 3/2: 4.2 Geometry in Euclidean Spaces
  HW 3/2:
  1. Computing angles with dot product: p.147 #1, 2, 4.
  2. Theorem: A parallelogram is a rhombus (all side lengths equal) if and only if the two diagonals are perpendicular to each other. Prove this using a dot product equation. Be careful to show both directions of the implication.
  3. Subspaces as orthogonal spaces
     1. p.148 #6,7,8,9.
     2. For a set of vectors C = {w₁,..., w_k} ⊂ V = Rⁿ define the set of vectors perpendicular to all the w_i's: C^⊥ = {v ∈ V s.t. v•w_i = 0 for all i}, where v•w denotes dot product. Show that C^⊥ is a vector space; in fact the space of solutions v = (x₁,...,x_n) to a homogeneous linear system having one equation a₁x₁ + ... + a_nx_n = 0 for each vector w_i = (a₁,...,a_n).

• Reading 3/4: 4.1 Inner Products and Norms
  HW 3/4:
  For a vector space V with basis B = {v₁,...,v_n} define the following substitute for dot product: an operation taking a pair of vectors v,w to a scalar denoted < v,w >, defined as follows. If v = r₁v₁ + ... + r_nv_n and w = s₁v₁ + ... + s_nv_n , then < v,w > = r₁s₁ + ... + r_ns_n .
  1. Show that for V = Rⁿ and B = E = {e₁,...,e_n} the standard basis, < v,w > is just the ordinary dot product.
  2. Show that for any V and any basis B, the operation < v,w > satisfies the axioms of an inner product in Def 4.1 p.136: that is:
     1. < v,v > ≥ 0 for all v, and < v,v > = 0 only for v = 0.
     2. < v,w > = < w,v >
     3. < rv,w > = r< v,w >
     4. < v+w,x > = < v,x > + < w,x >.

• Proof due 3/14: The Fibonacci sequence. Define: F = (F₁, F₂, F₃,...) = (1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...) determined by the initial values F₁ = F₂ = 1 and the recurrence: F_n = F_n-1 + F_n-2   for n ≥ 3 .
  1. Look up the history of this sequence, which started with Fibonacci's book introducing Arabic numerals to Europe. Explain how it models delayed self-reproduction.
  2. Test that F_n exhibits exponential growth by plotting (n, log F_n) for fairly large n. Explain why, if there exists a limit F_n+1 / F_n → r, then r must be the golden ratio, meaning the positive solution of: r/1 = (r+1)/r .
  3. Extra Credit: Show that F_n is even exactly when n is divisible by 3. You can use induction, but the link step should probably examine a whole cycle of (odd, odd, even), which implies the next (odd, odd, even). Next: which Fibonacci numbers are divisible by 3? Can you find other interesting divisiblity properties, and prove them? Hint: there is a very general and very pretty such property.
  4. Show that the set of all sequences: A = { a = (a₁, a₂, a₃,...)   s.t.   a_i ∈ R for each i } is a vector space under the natural vector addition and scalar multiplication. It is huge and useless, except as an ambient space.
  5. Show that the set of "Fibonacci-like" sequences: F = { a ∈ A   s.t.   a_n = a_n-1 + a_n-2 for n ≥ 3 } is a subspace of A with basis e₁ = (1,0,1,1,2,3,5,...) and e₂ = (0,1,1,2,3,5,8,...). Note that F = e₁ + e₂ .
  6. A geometric sequence is of the form: g = (r, r², r³,...), so that the n^th term is rⁿ. Show that g ∈ F whenever   rⁿ = r^n-1 + r^n-2   for all n ≥ 3, which is equivalent to the single quadratic equation  r² - r - 1 = 0   with solutions: r₁ = ½(1 + √5)   and   r₂ = ½(1 - √5). Conclude that the two geometric sequences: g₁ = (r₁, r₁², r₁³,...),   g₂ = (r₂, r₂², r₂³,...) form a basis of F. Hint: It is enough to show these are linearly independent. Why?
  7. Since {g₁, g₂} is a basis, we can write: F = c₁ g₁ + c₂ g₂. Find these unique coordinate scalars (c₁,c₂). Since the sequences are equal, the n^th terms are equal:   F_n = c₁ r₁ⁿ + c₂ r₂ⁿ.
     Hint: write a sequence a = (a₁, a₂,...) in terms of the standard basis as: a = a₁ e₁ + a₂ e₂, so that you can represent a by just its first two coordiantes (a₁, a₂). Now the equation becomes: (1,1) = c₁ (r₁, r₁²) + c₂ (r₂, r₂²) .
  8. Simplify the above to prove Binet's formula: F_n = (r₁ⁿ - r₂ⁿ) /√5 . This is very hard to believe: Somehow all the √5's on the right-hand side cancel out for any value of n, and leave only the whole number F_n. Verify this by hand for n = 1,2,3. Incredible, but true.
  9. Note that r₁ ≈ 1.6 and r₂ ≈ -0.6 . Thus the term r₂ⁿ is almost negligeable. Prove that F_n = round(r₁ⁿ / √5), where round( ) means round to the nearest whole number.
     Use this formula on a calculator or spreadsheet to compute F₅₀ exactly. If you can, make a spreadsheet computing F_n from the recurrence definition in one column, and using the formula in the other, and see that they are the same. (Also print out the formulas in each cell, so I can see them.)

• Reading 3/14: 4.2, p. 145-147.
  HW 3/14: p. 147 #5, 7, 8.
  
  1. Recall from HW 3/2 that for any set of vectors C ⊂ V = Rⁿ, whether C is a finite or infinite set, we define C^⊥ = { v ∈ V s.t. v•w = 0 for all w ∈ C }. Show the following properties this construction:
     1. C^⊥ = (Span C)^⊥
     2. C ⊂ (C^⊥)^⊥
     3. If B ⊂ C, then C^⊥ ⊂ B^⊥ .
  2. Recall that a set C = {u₁,...,u_m} is orthonormal if  u_i•u_i = 1 for all i, and  u_i•u_j = 0 for i ≠ j.
     1. Let S = { v = (x,y,z) ∈ R³ s.t. x + y + z = 0 } = (1,1,1)^⊥. Find a basis {v₁, v₂} for S using Gaussian Elimination.
     2. Find an orthonormal basis {u₁, u₂} for the above S as follows. First, let u₁ = v₁/|v₁|, so as to get u₁•u₁ = 1. Second, let u'₂ be the projection of v₂ perpendicular to u₁: u'₂ = v₂ − (v₂•u₁)u₁. Finally, divide u'₂ by its length:  u₂ = u'₂ / |u'₂| , to get u₂•u₂ = 1.
        Compute {u₁, u₂} and check that it is orthonormal.
        Would this method generalize to give an orthonormal basis of any subspace S ⊂ Rⁿ ?

• Reading 3/16: 4.4 Orthogonality, especially p. 158-161, and 4.5 Fourier Analysis.
  HW 3/16:
  1. p.168 #4.
  2. p.162 #7,9; p. 168 #5.
     These concern the vector space V = Cont([a,b]) = {continuous functions f : [a,b] → R}. (Here f : [a,b] → R means that the function f(x) takes inputs x in the interval [a,b], and gives outputs in R.) We have the following inner product on V, a substitute for dot product (see p.138):
     < f , g > = ∫_a^b f(x) g(x) dx . We need to restrict to continuous functions on a finite interval because otherwise there might be infinite area under the graphs, so the integral would be undefined.
  3. Extra Credit: p.167 #2. Here the function space is Cont([-π,π]): the interval [-π,π] makes for neater calculations. You need to compute integrals like ∫_-π^π sin(kx) sin(mx) dx for various k,m. Do as many of these as you can by hand, perhaps using induction.

• Project due Mon 3/21: Compute a Fourier approximation.
  1. Do p. 168 #7, computing the first few terms of the Fourier approximation to f(x) = x² on [-π,π]. Refer to the Quick Example p.165. To get the coefficients, do all the integrals by hand, using integration by parts or other methods. Hint: The integral of an odd function over [-π,π] is always zero. Check your work with a computational program like Wolfram Alpha (see example).
  2. Make a spreadsheet plotting x² and the Fourier approximation, to see how close they are. Note how the approximation quickly fails away from the interval [-π,π], because x² is not a periodic function.
     Note: To get a practical Fourier approximation, you do not need exact values for the integrals giving the coefficients, only numerical values to a few decimal places. That is all you can see in the graphs, anyway.

• Reading 3/23: 6.2 Compositions and Inverses.
  HW 3/23:
  • p.223 #1,2,8. The problems give several functions f : X → Y, where the input set X (the domain) and the output set Y (the codomain) are not necessarily vector spaces, and the functions are not necessarily linear. Still, we consider the same two properties:
    • f is one-to-one means: if f(x₁) = f(x₂), then x₁ = x₂. That is, each output-value y ∈ Y is hit by at most one input value x ∈ X with f(x) = y.
    • f is onto means: for every y ∈ Y, there is at least one x ∈ X with f(x) = y.
    If f is one-to-one and onto, then it has has an inverse function f^-1 : Y → X with f^-1(f(x)) = x and f(f^-1(y)) = y.
    The problems ask to show that each function has each property, or give a counter-example.
    Hints: For the first 3 functions with X = Y = R, it is helpful to look at the graph (though your answer has to be verbal/numerical, not pictorial). The last function L : R³ → R³ is linear, and solving L(x,y,z) = (a,b,c) by Gaussian Elimination allows you to determine one-to-one-ness and onto-ness.
  • p.224 #5. Here we work with spaces of vectors which are themselves functions: P = polynomial functions, C(R) = continuous functions (no jumps), and D(R) = differentiable functions (no kinks). The operator A is anti-differentiation, taking a function f as input and giving a function g as output: A(f) = g, where g(x) = ∫₀^x f(x) dx. Note that the input of A is the function f, not the real value x.
    The problem asks: If we consider A with each domain, is it one-to-one and/or onto? Also, use the Fundamental Theorems of Calculus to determine wether the differentiation mapping D is an inverse of A.
  • p.225 #14. Prove the formula (f ° g)^-1 = g^-1 ° f ^-1. Informally, this is common sense: to undo f-after-g, you undo g after undoing f. Give a formal argument by showing that g^-1 ° f^-1 has the properties which define (f ° g)^-1.
  • Extra Credit: p.225 #21. These are famous examples regarding Georg Cantor's notion of infinity. We say two sets have equivalent cardinality (same size) if there is an invertible fuction (one-to-one and onto) between them. A cardinal number is defined as an equivalence class of sets, finite or infinite.
    • Sets with the cardinality of the natural numbers N are called countable, and parts (a)-(c) show that the integers and the rationals are countable, even though they seem much larger than N.
    • Extend parts (d), (e) by showing that the intervals [0,1) and [0,1], the reals R, and the plane R² all have the same cardinality, but are not countable. A famous result (Independence of the Continuum Hypothesis) shows that whether there is a cardinal between the naturals and the reals is an undecidable question.

• Reading 3/25: 6.3 Matrix of a Linear Function
  HW 3/25:
  1. Consider the following linear mappings T : R² → R² :
     • I = no motion, do nothing: I(v) = v for all v.
     • T₀ = 90° counter-clockwise rotation
     • T₁= reflection across the x-axis.
     • T₂= reflection across the y-axis.
     • T₃= reflection across the line y = x.
     • T₄= 45° counterclockwise rotation.
     • T₅= rotation by 180°
     Find the matrix of each of these mappings. Use matrix multiplication to compute:
     1. T₁ ° T₀
     2. T₁ ° T₁
     3. T₁ ° T₂
     4. T₂ ° T₁
     5. T₀ ° T₃
     6. T₃ ° T₀
     What can you say about the relationship between T ° T ' and T ' ° T for various T, T ' ?
  2. p.231 #3. Verify that T(v) = [T]•v, where • means matrix multiplication. Recall that the matrix [T] of a linear function T : Rⁿ → R^m is a table of numbers with m rows and n columns (m × n), with columns [ T(e₁) | ... | T(e_n) ].
  3. Find the matrix of the map from p.216 #5, namely T : P₂ → P₃ with T(p) = q, where q(x) = p(x-1). Also compute [T]•[p] for p(x) = a + bx + cx², and verify that [T(p)] = [T]•[p] .
     Hints: For v ∈ V, with basis, B = {v₁,...,v_n}, we use [v] = [v]_B to mean the column vector (r₁,...,r_n) of B-coordinates of v. The matrix of a linear mapping T : V → W (with respect to basis B of V and basis C of W) is: [T] = [T]_C^B  =  [ [T(v₁)]_C  | ... |  [T(v_n)]_C ] .
     Here, we take B = {1,x,x²} and C = {1,x,x²,x³}, so p(x) = a + bx + cx² has column vector [p] = [p]_B = (a,b,c); and q(x) = a + bx + cx² + dx³ has column vector [q] = [q]_C = (a,b,c,d).

• No Proof due 3/28.

• Reading 3/28: 6.4 Matrices of Compositions and Inverses
  HW 3/28: p.191 #4 (answers p.372); p.237 #1, 2, 3(d).

• Reading 4/1: 6.5 Change of Basis
  HW 4/1:
  1. p.244 #3.
  2. Do p.244 #1,2,4(a) as follows. For each problem, do these steps:
     1. In each case there is a vector space V having a standard basis E and non-standard bases B,B'. Find the change-of basis matrix [P_E^B] which changes B-coords to standard E-coords: this is the matrix whose column vectors are the B-basis in E-coordinates. Similarly find [P_E^B'].
        Example: For #2, we have V = P₂ = polynomials of degree at most 2, E = {1,x,x²},     B = {x, 1-x, 1+x²},
        [P_E^B]  =  [ [x]_E   [1-x]_E   [1+x²]_E ]  = 

        0	1	1
        1	-1	0
        0	0	1

     2. Compute the inverse matrix which changes E to B: that is, [P_B^E] = [P_E^B] ^-1.
        Do this for basis B, not B'.
     3. Finally compute the change of basis from B' to B as the composition of changing B' to E, then E to B. That is, compute the matrix product: [P_B^B'] = [P_B^E] • [P_E^B'].
  3. Define T : P₂ → P₂ by T(f) = (x-2) df /dx . That is, T differentiates f, then multiplies by x-2. Consider the standard basis E, and a basis B = {1, x-2, (x-2)²} specially adapted to this mapping.
     1. Directly compute the matrix of T in B-coordinates, that is [T]_B^B.
     2. Next compute the change-of-basis matrx [P_E^B] and its inverse [P_B^E] = [P_E^B]⁻¹ .
     3. Now compute the matrix of T in E-coordinates, [T]_E^E = [P_E^B] • [T]_B^B • [P_E^B]⁻¹ .
     4. Finally, compute [T]_E^E directly as [ [T(1)]_E   [T(x)]_E   [T(x²)]_E ].
     5. Even if the direct computation of [T]_E^E is easier, it is still revealing to know that T has such a simple description as [T]_B^B.
        Give a geometric description of T as stretching or collapsing R³ along three special vectors, which are called the proper vectors or eigenvectors of T. We will learn more about this later.

• Proof due 4/4: Prove the following, using results we have previously covered.
  Let T : V → W be a linear mapping, and {v₁,...,v_n} a basis of V. Then we have:
  1. T is one-to-one  ⇔  {T(v₁),...,T(v_n)} is a linearly independent subset of W.
  2. T is onto  ⇔  {T(v₁),...,T(v_n)} spans W.
  3. Assuming dim(V) = dim(W), we have: T is one-to-one  ⇔  T is onto.

• Reading 4/4: 6.6 Image and Kernel, 6.7 Rank and Nullity.
  HW 4/4:
  1. p.250 #2. Use the Quick Example, p. 246-247. Compute the Ker(T) by solving the equation T(v) = 0 for unknown v = (x₁, x₂,...). Compute the Image as the span of the column vectors of T which correspond to leading 1's in the row-reduced matrix. For part (c) verify the Rank-Nullity Theorem (Thm 6.27, p.251).
     Let T : V → W be a linear map with domain space V and codomain space W. Then the range Im(T) ⊂ W and the kernel Ker(T) ⊂ V are subspaces, and dim Im(T) + dim Ker(T) = dim(V). We call rank(T) = dim Im(T) and nullity(T) = dim Ker(T).
  2. p. 254 #3(a): Use the Rank-Nullity Theorem.

• Reading 4/8: 6.6 Image and Kernel; 6.7 Rank and Nullity.
  HW 4/8: p. 254 #1. Check whether the given dimensions are consistent with the Rank-Nullity Theorem (Thm 6.27)

• Proof due 4/11: Here is another example of a special basis adapted to a given problem: summing powers of integers.
  1. Recall the vector space of degree k polynomials: V = P_k = { a₀ + a₁x + ... + a_kx^k   s.t. a_i ∈ R for all i }. with standard basis E = {1, x, x²,..., x^k}. For each k, define the falling power polynomial: x^k := x(x-1)(x-2)...(x-k+1) so that:   x⁰ = 1,  x¹ = x,  x² = x(x-1),  x³ = x(x-1)(x-2), etc. Our special basis will be B_k := {1, x¹, x²,..., x^k}.
     1. Show that B₃ forms a basis of P₃. Hint: Use matrix computations to show that B is linearly independent (or that it spans). The other property follows automatically since....
     2. Prove each B_k forms a basis of P_k for any k.
        Hint: Use induction on k. Assume you know B_k is linearly independent, and suppose a₀ + a₁x¹ + ... + a_kx^k + a_k+1x^k+1 = 0 in P_k+1 . Now imagine the expansion in the standard basis: what is the coefficient of x^k+1 ?
     3. For k = 3, find the change-of-basis matrix [P_E^B] and its inverse [P_B^E], and use this to write 1, x, x², x³ in terms of 1, x¹, x², x³.
     4. For a function f(x), define the discrete derivative Δf(x) := f(x+1) − f(x) , analogous to the usual derivative df/dx, the limit of (f(x+h) − f(x)) / h . Show the crucial property of the falling power polynomials: Δ(x^k) = k x^k-1 . This is in analogy with (d/dx)(x^k) = k x^k-1.
     5. Now it is easy to prove the formula: 1^k + 2^k + 3^k + ... + n^k = (n+1)^k+1 / (k+1) , the discrete integral analog of ∫₀ⁿ x^k dx = n^k+1/(k+1) .
        Hint: This follows from x^k = Δx^k+1 / (k+1). By the way, can you fix the summation formula to make it hold for k = 0?
     6. Write the above summation formula for k = 1 to get a familiar result. Now write x² = x + x² as before, and sum both sides for x = 1,...,n to find the formula for 1² + ... + n². Do the same for 1³ + ... + n³.
        
     7. Extra Credit: This is the start of a whole theory: the Calculus of Discrete Differences. Here are some more samples.
        • Explore the summation formulas for larger k. Look up the relevance of Bernoulli numbers.
        • Let us denote the derivative as D = d/dx, and the n^th derivative as Dⁿf(x). Recall from Calculus that for any function f(x) we have Taylor's Formula: f(x) = c₀ + c₁x + c₂x² + ...   for coefficients c_i = Dⁱf(0) / i! (whenever the infinite sum on the right-hand side converges). Give an elementary proof of this formula in case f(x) is a polynomial. Hint: We start with a polynomial function f(x) = a₀ + ... + a_nx^k. Take derivatives of both sides and set x = 0 to show that the formula for c_i recovers the original coefficients a_i .
        • Now prove the Discrete Taylor's Formula for a polynomial f(x) of degree k: f(x) = b₀ + b₁x¹ + b₂x² + ... + b_kx^k for coefficients b_i = Δⁱf(0)/i! .
        • The following is the beginning of a sequence (a₀, a₁,a₂,...) with a_n = f(n) for some polynomial f(x): 0, 10, 24, 48, 112, 270, 600, 1204, 2208, 3762, 6040, 9240, ... Figure out the polynomial f(x) using the Discrete Taylor's Formula. That is, use the sequence to compute f(0), Δf(0), Δ²f(0),..., and plug into the Formula. Is your f(x) the only possible answer?
        • In fact, the Discrete Taylor Formula will produce an infinite series expansion for any function f(x), provided the series is convergent. Try expanding some familiar functions to get interesting formulas.
        • Try exploring solutions of difference equations (discrete differential equations involving Δ instead of D). For example, find the solutions to Δf(x) = f(x), the discrete analog of e^x. Or Δ²f(x) = -f(x), the discrete analog of sin(x) and cos(x). You can find solutions directly, or by solving for coefficients in the Discrete Taylor Formula.

• Axiomatic method for vector spaces
  • The definition of vector space (Axioms 1-8) distills the minimum essential properties that make vector computations work in the motivating original case of 2D and 3D space.
  • After writing down these Axioms, we find other examples of spaces which satisfy the Axioms. This allows us to treat them analogously to arrows in 2D and 3D. Examples:
    • Rⁿ and its subspaces: for example the set of solutions to any linear system which is homogeneous (all constants are 0).
    • F(X) = { f : X → R} the space of all functions from a given set X to R. A function is denoted by a letter like f, g, h,... or by f(x), g(x), h(x), where x is a variable ranging over X, the domain or input set of the functions. The domain X may be R, the positive reals R₊ , the whole numbers N, or any set at all. The output set is always R, and function addition and scalar multiplication operate on outputs, not inputs. For example, the scalar multiple g = 2f is the function with g(a) = 2 f(a) for each input x = a. The zero function 0 = z(x) is the function with z(a) = 0 for all inputs x = a.
    • F(R) has many important subspaces, such as the set P of all polynomials, and the polynomials of degree at most n: P_n = {a₀ + a₁x + ... + a_nxⁿ   s.t.  a₀,...,a_n ∈ R} ,
    • Other subspaces of F(R) include: the set of even functions (or odd functions); and the solutions to a homogeneous differential equation like f ''(x) + f(x) = 0 , namely V = {a cos(x) + b sin(x) s.t. a,b ∈ R}.
  • We will prove theorems which are consequences of the Axioms 1-8. These theorems will hold for all examples of vector spaces, because the proofs do not make any references to the details of any example: they use only the properties which all examples have in common, namely the Axioms.
    • There are a couple of dozen basic formulas such as those in Theorems 1.2--1.8 (p.13-19): for example 0v = 0 and (-1)v = -v. These are so fundamental to algebra, that any structure where they did not hold would be very weird and different from our motivating examples, and should not be called a vector space. We would have to include these basic formulas among the required Axioms, making a very long list of requirements for a vector space. However, we do not need to do this: the basic formulas all follow strictly from Axioms 1-8, as shown in the basic proofs of Ch 1.3 & 1.4.
    • Definition: A subspace of a vector space V is a subset S ⊂ V such that S is itself a vector space with the same operations as V.
      Subspace Theorem: S ⊂ V is a subspace provided:
      1. 0 ∈ S
      2. S is closed under vector addition: if v,w ∈ S, then v + w ∈ S.
      3. S is closed under scalar multiplication: if v ∈ S, r ∈ R, then rv ∈ S.

• Constructing Proofs. A proof is a sequence of logical deductions from specified facts and assumptions to a desired conclusion. Writing proofs is an art, with no easy method to it, but the following steps are the basics.
  1. Picture what the proposition means for common examples like R², R³, and for specific vectors, numbers, etc.
     • If the statement doesn't seem reasonable in the examples, it is probably false, or you are not understanding it properly.
     • If a general statement clearly fails for just one example (a counter-example), then it is certainly false: no proof could exist, since it would also apply to the counter-example.
  2. Determine the parts of the proposition.
     • Hypothesis: what is given or assumed, the setup, often appearing after "if" or "let" or "for any" in the statement.
     • Conclusion: what is to be proved, often appearing after "then" in the statement.
     • Write the hypothesis at the top of your page, the conclusion at the bottom, leaving lots of blank space between.
     • Be clear on the background you are allowed to use in the proof, depending on your audience. In this course, we assume all facts of arithmetic and high-school algebra applying to real numbers. You can use these without justification, since we all know them. (We do not know the corresponding facts about vectors until we prove them or assume them as Axioms.)
     • Be clear on what previous results you can assume in your proof. You do not need to re-prove facts like 0v = 0: after our initial proof, just refer to Thm 1.4. Once such facts become thoroughly familiar, you can just use them without references.
  3. Construct a bridge of logical implications from the hypothesis to the conclusion. This is the hard part! Strategies:
     • Review the defintion of each term in the hypothesis and conclusion. Write the definitions near the terms: they will almost certainly be needed in your proof.
     • Break down more complicated propositions into sub-statements, each with its hypothesis and conclusion.
     • Work from both ends, transforming the hypothesis and conclusion into different forms until you get both in the same form.
     • Transform the statement logically, such as into the contrapositive: P ⇒ Q is equivalent to NOT(Q) ⇒ NOT(P).
     • Break the proposition P into a sequence of statements P₀ , P₁ ,..., and try a proof by induction.
     • If all else fails, try proof by contradiction: assume the hypothesis is true, the conclusion is false, and logically derive a nonsensical statement that something is both true and false.
       Not recommended for beginners! Any mistake will lead to a contradiction which looks like a success.
  4. Make a final draft of the proof:
     • Start with a complete statement of the Proposition (or Theorem for important propositions, Lemma for less important ones).
     • The logical flow of deductions must be clear: FROM the hypothesis TO the conclusion (no more working from both ends).
     • Each successive statement must be clearly true, given the previous statements. Inferences can be justified by definitions, by previously proved statements, or by general logical principles, such as: if two things are equal, then we can substitute one for the other in any statement or equation.
     • Leave out: the story of how you found the proof, examples and specific cases that you tried, and anything else outside the logical path from hypothesis to conclusion.
     • Judge your audience: leave out details that will be obvious to them. As in other forms of expository writing, more words = more pain. We consider a proof rigorous not if it spells out every last detail, but rather if it is clear to the audience how every last detail could be supplied if wanted.
       In your HW, assume your audience is one of your classmates who has not done this assignment and needs a good deal of explanation. Do NOT assume the audience is the professor, who knows all about the problem and needs only a hint that you understand the proof.

• Idea of coordinates in a vector space
  • In the original case of R², we define coordinates by picking two axes with a scale of length on each. The coordinates of a point P = (x,y) specify how far you need to go in each axis direction to get to P from the origin. If v is the vector from the origin to P, this means v is a linear combination of the unit-length coordinate vectors, which we will call e₁ = (1,0) and e₂ = (0,1): v = xe₁ + ye₂ = x(1,0) + y(0,1) = (x,y). Similarly for Rⁿ, we have unit vectors e₁ = (1,0,...,0), ... , e_n = (0,...,0,1), and: v = x₁e₁ + ... + x_ne_n = (x₁,...,x_n).
  • For a general, abstract vector space V, we often have no definition of coordinates, as for spaces of functions. If V is a subspace of Rⁿ, we have the coordinates of the surrounding space, but there are "too many" of these: a plane in R³ has points with 3 coordinates, even though the plane has only 2 dimensions of internal motion, 2 degrees of freedom.
  • The general definition of coordinates on V is to pick a set B = {v₁,...,v_n} which we think of as unit vectors along coordinate axes. If a vector is obtained by going a certain distance along each direction, we take the list of these distances to be the coordinates: v = r₁v₁ + ... + r_nv_n , means the coordinates which describe v are (r₁,...r_n).
  • Example: Consider the space of functions satisfying the differential equation of harmonic motion: V = {f ∈ F(R)   s.t.  f "(x) = -f(x) }. This space has no inherent coordinates. However, it is a fact that there are two basic solutions, cos(x) and sin(x), and all others are linear combinations of these: V = Span{cos(x), sin(x)} = {a cos(x) + b sin(x)   s.t. a,b ∈ R}. Now we say a function f(x) = a cos(x) + b sin(x) is described by coordinates (a,b), and this sets up a one-to-one correspondence between V and R². Careful: we don't say f(x) = (a,b), since f(x) is a function and (a,b) is a list of two numbers. Rather, the coordinates correspond to or describe f(x), telling where it sits in V.
    Further, this correspondence respects vector addition: if f(x) = a cos(x) + b sin(x) and g(x) = c cos(x) + d sin(x), then the sum f(x) + g(x) = (a+c)cos(x) + (b+d)sin(x) has coordinates (a+c, b+d) = (a,b) + (c,d). That is, the sum of functions in V has the coordinates of the sum of vectors in R². We may thus do vector computations in V by coordinates in R².
  • Main Question: When does a set of vectors {v₁,...,v_n} define good coordinate axes in V?
    The main desire is that each vector v gets unique coordinates. What could go wrong?
    • We could have too few vectors, so not every v can be obtained by moving along the axis directions: V ≠ Span{v₁,...,v_n}.
      In the function example above, if we knew only a single basic solution v₁ = cos(x), this would not be enough to give coordinates to every v = f(x) ∈ V.
    • We could have too many vectors, which do not point in independent directions.
      In the function example, suppose we mistakenly take 3 basic solutions v₁ = cos(x),   v₂ = sin(x), and v₃ = cos(x + π/4). A trig identity gives cos(x + π/4) = √2 cos(x) + √2 sin(x), so we have two expressions for one vector: v = 0v₁ + 0v₂+ 1v₃ = √2v₁ + √2v₂ + 0v₃ , making (0,0,1) and (√2, √2, 0) both coordinates for v. What a mess!

• Requirements for a Basis
  • In a vector space V, a basis B = {v₁,...,v_n} is a set of vectors defining a good system of coordinate axes inside V. That is, every v ∈ V can be written as a linear combination   v = r₁v₁ + ... + r_nv_n   for a unique list of coordinates (r₁,..., r_n) ∈ Rⁿ. That is, v has a well-defined position with respect to the axes, as explained above. The plural of basis is bases, pronounced "bay-seez".
  • Formally, we say B is a basis if it has two good properties: spanning and linear independence. Each of these can be expressed in different ways.
  • Spanning. We say B spans V if it satisfies either of the conditions in the following:
    Proposition: The following conditions on B = {v₁,...,v_n} are equivalent:
    1. Every v ∈ V can be written in some way (perhaps several ways) as a linear combination of v_i's.
    2. V = Span(B)
    Loosely speaking, this means there are "enough directions" in B to fill V: we can reach any vector in V along the axis directions in B.
  • Linear independence. We say B is linearly independent if it satisfies any of the conditions in the following:
    Proposition: The following conditions on B = {v₁,...,v_n} are equivalent:
    1. Any v ∈ V can be written in at most one way (perhaps in no way) as a linear combination of v_i's.
    2. 0 can be written in exactly one way as a linear combination of the v_i's.
       That is, 0 = r₁v₁ + ... + r_nv_n only for r₁ = ... = r_n = 0.
    3. None of the vectors v_i is redundant, meaning no v_i can be written as a linear combination of the others: v_i ≠ r₁v₁ + ... + r_i-1v_i-1 + r_i+1v_i+1 + ... + r_nv_n ; for all r₁,...,r_n ∈ R.
    Loosely speaking, this means the vectors in B do not interfere with or cross each other, but rather point in different directions. Note this does not require the vectors to be perpendicular to each other.
  • Terminology. A linear combination of v₁,...,v_n is an expression r₁v₁ + ... + r_nv_n, where r₁,...,r_n are any scalars. The span of some vectors means the set of all possible linear combinations of the vectors: Span(B) = Span{v₁,...,v_n} = { r₁v₁ + ... + r_nv_n for all r₁,...,r_n ∈ R }. Note that Span(B) is always a subspace, since it contains 0 and is closed under vector addtion and scalar multiplication.

• Test 1: Fri Feb 25, in class. Come 5 min early for extra time. Syllabus:
  • Definitions
    • Vector space (addition, scalar mult, Axioms 1-8)
    • Subspace S ⊂ V, Subspace Theorem (conditions a,b,c)
    • Internal coordinates with respect to a basis B = {v₁,...v_n}: V     ↔    Rⁿ
      v = r₁v₁ + ... + r_nv_n ↔ (r₁,...,r_n)                  
    • Definition of a Basis: spanning (condition a or b) and linear independence (condition a or b or c).
  • Main theorems
    • Contraction: If a set B spans V, then B contains some basis of V.
    • Expansion: If a set B is linearly independent, then B is contained in some basis of V.
    • Dimension: Any two bases of a given vector space have the same number of vectors.
      The dimension of a vector space V is the number of vectors in any basis B: that is, dim(V) = #B.
    • Subspace dimension: If S ⊂ V is a subspace, then dim(S) ≤ dim(V).
    • Useful Corollary: Suppose dim(V) = n (so some basis has n elements) and B is a set with n vectors (a candidate for a basis). If B is linearly independent, then B is a basis. If B spans V, then B is a basis.
  • Main examples: finding bases
    • V = Rⁿ, n-space. Standard basis E = {e₁ = (1,0,...,0), ... , e_n = (0,...0,1)}.
      To check another basis B = {v₁,...,v_n}, test for linear independence by solving r₁v₁ + ... + r_nv_n = 0 to get r₁ = ... = r_n = 0. Useful Corollary guarantees spanning.
    • S = {solutions to a homogeneous linear system}, subspace cut out from Rⁿ by equations.
      Solve the system by Gaussian Elimination, and write as a linear combination with the free variables as coefficients.
    • S = Span{u₁,...,u_m} = {r₁u₁ + ... + r_mu_m  s.t. r₁,...,r_m ∈ R}, parametric form of a subspace. Test for linear dependence of {u₁,...,u_m} by solving r₁u₁ + ... + r_mu_m = 0. Remove the u_i corresponding to free variables r_i in the solution: the remaining u_i are linearly independent and form a basis of S.
    • V = F(X), the function space of f : X → R. This has no reasonable basis.
    • S = {solutions to a homogeneous linear differential equation} ⊂ F(X). Examples of such equations: f ' = f ,   f '' = -f ,   x³f " + sin(x)f ' - e^xf = 0 . The key is, a sum of two solutions is a solution (and same for scalar multiple).
    • P, the space of all polynomial functions of any degree. This has standard basis {1, x, x²,...}, an infinite set.
    • P_n , polynomials of degree at most n. Standard basis {1, x, x²,...,xⁿ⁺¹}, so dim(P_n) = n+1.
      To check another basis, test for linear independence in the same way as for Rⁿ (write in terms of standard basis).
    • Subspaces of P_n defined by homogeneous conditions like f(1) = 0 or f(0) + 3 f(2) = 0. The key is, if two functions satisfy the condition, then their sum also satisfies (and same for scalar multiple).
      To get a basis, write a general polynomial f(x) = a₀ + a₁x + ... + a_nxⁿ, write what the conditions mean as linear equations in the a_i's, and solve by Gaussian Elimination for variables a₀, a₁, ..., a_n .
  • Proofs
    • Basic lemmas for vector spaces. Any common algebraic fact for numbers should also be true for vectors, provided it can be interpreted in terms of vector addition and scalar multiplication, and it should be provable from Axioms 1-8.
    • Steps for constructing proofs (from Notes below)
      1. Picture reasonableness, search for counterexamples.
      2. Identify Hypothesis and Conclusion.
      3. Work from both ends: unpack definitions and make a bridge of equivalences or deductions.
      4. Make a final draft with deductions from Hypo to Concl.
    • Proof by Induction: Break up the statement A into cases A₀, A₁,... Prove Anchor Step A₀ directly; then Chain Step: if A_n then A_n+1, for any n. Final conclusion: A_n is true for all n ≥ 0.
    • Know how to use the definitions and the Useful Corollary to prove a set is a basis (or just spanning, or lin indep)
  • Computational Method: Gaussian Elmination to solve systems of linear equations; matrix form, leading and free variables.