NOTE: This page contains all the machine-verifiable examples presented during the lectures, as well as all the homework assignments. Click here to go back to the main page with the course information and schedule.

• 1. Introduction and Motivation
• 1.1. Models, systems, and system states
• 1.2. A language of system states: terms and their algebraic properties
• 1.3. Extending the language of models: vectors and matrices
• 1.4. Review: formulas, sets, and term equality
• 2. Vectors
  • 2.1. Defining operations on vectors
  • 2.2. Properties of vector operations
  • 2.3. Assignment #1: Vector Algebra
  • 2.4. Common vector properties, relationships, and operators
  • 2.5. Solving common problems involving vector algebra
  • 2.6. Using vectors and linear combinations to model systems
• 3. Matrices
  • 3.1. Matrices and multiplication of a vector by a matrix
  • 3.2. Interpreting matrices as tables of relationships and transformations of system states
  • 3.3. Interpreting multiplication of matrices as composition of system state transformations
  • 3.4. Assignment #2: Using Vectors and Matrices
  • 3.5. Matrix operations and their interpretations
  • 3.6. Matrix properties
  • 3.7. Solving the equation M v = w for M with various properties
  • 3.8. Row echelon form and reduced row echelon form
  • 3.9. Matrix transpose
  • 3.10. Orthogonal matrices
  • 3.11. Matrix rank
  • 3.12. Assignment #3: Matrix Properties and Operations
• Review 1. Vector and Matrix Algebra and Applications
• 4. Vector Spaces
  • 4.1. Sets of vectors and their notation
  • 4.2. Membership and equality relations involving sets of vectors
  • 4.3. Vector spaces as abstract structures
  • 4.4. Assignment #4: Vector Spaces and Polynomials
  • 4.5. Basis, dimension, and orthonormal basis of a vector space
  • 4.6. Homogenous, non-homogenous, overdetermined, and underdetermined systems
  • 4.7. Application: approximating overdetermined systems
  • 4.8. Application: approximating a model of system state relationships
  • 4.9. Application: distributed computation of least-squares approximations
  • 4.10. Orthogonal complements and algebra of vector spaces
• 5. Linear Transformations
  • 5.1. Set products, relations, and maps
  • 5.2. Homomorphisms and isomorphisms
  • 5.3. Linear transformations
  • 5.4. Orthogonal projections as linear transformations
  • 5.5. Assignment #5: Approximations and Linear Transformations
  • 5.6. Matrices as linear transformations
  • 5.7. Application: communications
  • 5.8. Affine spaces, affine transformations, and optimization
  • 5.9. Fixed points, eigenvectors, and eigenvalues
• Review 2. Vector and Matrix Algebra, Vector Spaces, and Linear Transformations
• Appendix A. Notes on tools

---

1. Introduction and Motivation

This section introduces at a high level the direction and goals of this course, as well as some terminology. Do not worry if all the details are not clear; all this material will be covered in greater detail and with many more examples during the course.

1.1. Models, systems, and system states

When many real-world problems are addressed or solved mathematically and computationally, the details of those problems are abstracted away until they can be represented directly as idealized mathematical structures (e.g., numbers, sets, matrices, and so on). We can talk about this distinction by calling the real-world problems systems (i.e., organized collections of interdepentend components) that have distinguishable system states, and the abstract versions of these systems that only capture some parts or aspects of the different system states as models. Since models are abstractions, we must also consider the interpretation of a model that explains how the different parts of the model are related to the different parts of the system (i.e., what each part of the model represents).

The set of real numbers is a very simple kind of model that can be used to represent quantities or, by considering quantities and fractions of units (e.g., inch, meter, kilogram, and so on), a magnitude. If we adopt R as our model of a system, we can then represent individual system states using individual real numbers.

model (language for describing system states)	example of a system state in the model	interpretation	system
R	7	number of giraffes	zoo
R	1	distance in AU between the two objects	the Earth-Sun system
R	5.6	temperature in Celsius	weather in Boston

Thus, real numbers are a very simple symbolic language for modelling systems. Furthermore, this language allows us to describe characteristics of systems concisely ("7" is much more concise than a drawing of seven giraffes).

1.2. A language of system states: terms and their algebraic properties

Real numbers can be used to characterize the quantities or magnitudes of parts of a system, but this is often not enough. We may want to capture within our models certain kinds of changes that might occur to a system. In order to do so, we must add something to our language of models: binary operators such as +, -, ⋅, and so on.

model (language for describing system states)	a system state in the model	interpretation	system
R with addition (+)	3	number of apples in one of the apple baskets	a collection of apple baskets
R with addition (+)	3 + 2	number of apples in two of the apple baskets	a collection of apple baskets
R with addition (+)	2 + 3	number of apples in two of the apple baskets	a collection of apple baskets
symbolic language	symbol string (a.k.a., "term") in the language	meaning of symbol string	system

The different parts of this language for models have technical names. So far, we have seen real numbers and operators. We can build up larger and larger symbol strings using operators and real numbers. These are all called terms.

Notice that when our language for models only had real numbers, each symbol corresponded to a unique system state. However, by introducing operators into our language for describing system states, we are now able to write down multiple symbol strings that represent the same system state (e.g., 2 + 3 and 3 + 2). In other words, "2 + 3" and "3 + 2" have the same meaning.

1.3. Extending the language of models: vectors and matrices

Real numbers and operators are still not sufficient to capture many interesting aspects of real-world systems: they can only capture quantities, one-dimensional magnitudes (e.g., distance). What if we want to capture multidimensional magnitudes (e.g., temperature and pressure) or relationships between different quantities? These can correspond to points, lines, planes, spaces; relationships and changes within such systems can be modelled as translations, rotations, reflections, stretching, skewing, and other transformations.

Example: Suppose we have $12,000 and two investment opportunities: one has an annual return of 10%, and the other has an annual return of 20%. How much should we invest in each opportunity to get exactly $1800 over one year?

The above problem can be represented as a system in which two magnitudes x ∈ R and y ∈ R have a relationship. Typically, this is represented using a system of equations:

x + y	=	12000
0.1 x + 0.2 y	=	1800

The possible solutions to this system are the collection of all pairs of real numbers that can be assigned to the pair (x,y). These are the possible system states. Notice that these can be interpreted directly as points on a plane.

How does the above example suggest we might extend our language for system states in a model? We might consider ordered pairs (x,y) of real numbers. More generally, we might consider ordered lists (x₁,...,x_n) of real numbers. In this course, we will introduce a few new kinds of terms into our language for models that can help us represent these sorts of relationships within systems: vectors and matrices. We will also study the algebraic properties of this extended language.

new term language construct	what it represents
vectors	system state in the model
matrix	transitions between system states
matrix	changes to system states
matrix	relationships between system states
matrix multiplication	composition of transformations of system states

1.4. Review: sets and formulas

---

2. Vectors

In this section we consider a particular kind of term: a vector. A vector can have many interpretations, but the most common is that of a point in a geometric space. We first define a notation for names of vectors. Vectors will be written using any of the the following equivalent notations:

2.1. Defining operations on vectors

We have introduced a new kind of term (vectors) with their own corresponding notation. As with R, the set of real numbers, we define symbol to represent the sets of vectors.

We will also use symbols to name some geometric manipulations of vectors. One such operation is addition. Suppose we treat vectors as paths from (0,0), so that (2,3) is the path from (0,0) to (2,3) and (1,2) is the path from (0,0) to (1,2). Then vector addition would represent the final destination if someone walks first along the length and direction specified by one vector, and then from that destination along the length and direction specified by the other. The following definition for the operation + and vectors of two components corresponds to this intuition.

Notice that we have defined an entirely new operation; we are merely reusing (or "overloading") the + symbol to represent this operation. We cannot assume that this operation has any of the properties we normally associate with addition of real numbers. However, we do know that according to our interpretion of vector addition (walking along one vector, then along the other from that destination), this operation should be commutative. Does our symbolic definition conform to this interpretation? If it does, then we should be able to show that [x;y] + [x';y'] and [x+x';y+y'] are names for the same vector. Using the commutativity of the real numbers and our definition above, we can indeed write the proof of this property.

Recall that we can view multiplication by a number as repeated addition. Thus, we could use this intuition and our new notion of vector addition defined above to define multiplication by a real number; in this context, it will be called a scalar, and the operation is known as scalar multiplication.

Scalar multiplication has some of the intuitive algebraic properties that are familiar to us from our experience with R. Below, we provide proofs of a few.

Once we have defined scalar multiplication, we can now assign a meaning to the negation operator (interpreting -v for any vector v ∈ R² as referring to the scalar multiplication −1 ⋅ v).

The above definition allows us to define vector subtraction: for two vectors v and w ∈ R², v - w = v + (-w).

Notice that we did not define vector division. In fact, division by a vector is undefined (in the same way that division by 0 is undefined). However, we can prove a cancellation law for vectors.

2.2. Properties of vector operations

In this course, we will study collections of vectors that have particular properties. When a collection of vectors satisfies these properties, we will call it a vector space. We list these eight properties (in the form of equations) below. These must hold for any u, v, and w in the collection, and 0 must also be a vector in the collection.

u + (v + w)	=	(u + v) + w
u + v	=	v + u
0 + v	=	v
v + (-v)	=	0
1 * v	=	v
s * (u + v)	=	(s * u) + (s * v)
(u + v) * s	=	(u * s) + (v * s)
s * (t * u)	=	(s * t) * u

Note that these are not unique; we could have specified an alternative equation for the additive identity.

Each equation can be derived from the other using the commutativity

These eight equations can be called axioms (i.e., assumptions) when we are studying vector spaces without thinking about the internal representation of vectors. For example, the above derivation of the alternative additive identity equation is based entirely on the axioms and will work for any vector space. However, to show that some other structure, such as R², is a vector space we must prove that these properties are satisfied. Thus, to define a new vector space, we usually must:

1. define a way to construct vectors;
2. define a vector addition operator + (i.e., how to add vectors that we have constructed);
3. specify the vector that is the additive identity (call it 0);
4. define vector inversion: a process for constructing the inverse of a vector;
5. prove that the eight properties of a vector space are satisfied by the vectors, +,0, and *.

---

2.3. Assignment #1: Vector Algebra

In this assignment you will perform step-by-step algebraic manipulations involving vectors and vector operations. In doing so, you will assemble machine-verifiable proofs of algebraic facts. Your proofs must be automatically verifiable using the proof verifier. Please submit a single text file a1.txt containing your proof scripts for each of the problem parts below.

Working with machine verification can be frustrating; minute operations that are normally implied must often be explicit. However, the process should familiarize you with common practices of rigorous algebraic reasoning in mathematics: finding, applying, or expanding definitions to reach a particular formula that represents a desired argument or solution.

1. 1. Finish the proof below by solving for a using a sequence of permitted algebraic manipulations.
      HTML

      text

      load into verifier

      ∀ a, b ∈ R,
      

      3 a   =   b b + 8

      
      implies
      # ... put proof steps here ...
      

      a = ? # replace "?" with an integer

      
      

      \forall a, b \in \R,
    
    [3; a] = [b; b + 8]
    
  \implies
    # ... put proof steps here ... 
    
    a = ?  # replace "?" with an integer 
    


   2. Finish the proof below by solving for b in terms of a.
      HTML

      text

      load into verifier

      ∀ a,b ∈ R,
      

      b 38   =   3 7   a +   0 4   b

      
      implies
      # ... put proof steps here ...
      

      b = ? # replace "?" with a term containing "a"

      
      

      \forall a,b \in \R,
  
    [b; 38] = [3; 7] a  + [0; 4] b
  
  \implies
    # ... put proof steps here ... 
    
    b = ?  # replace "?" with a term containing "a" 
    


   3. Finish the proof below to show that [1;2] and [-2;1] are linearly independent.
      HTML

      text

      load into verifier

      1 2   ⋅   −2 1   = 1 ⋅ −2 + 2 ⋅ 1   and

      
      # ... put proof steps here ...
      

      (   1 2   ) and (   −2 1   ) are orthogonal

      
      

      
[1; 2] * [-2; 1] = 1 * -2 + 2 * 1 \and

  # ... put proof steps here ... 
  
  `([1; 2]) and ([-2; 1]) are orthogonal`
  


   4. Solve for x (the solution is an integer).
      HTML

      text

      load into verifier

      ∀ x ∈ R,
      

      (   x 4   ) and (   1 1   ) are orthogonal

      
      implies
      # ... put proof steps here ...
      

      x = ?

      
      

      \forall x \in \R,
    
    `([x; 4]) and ([1; 1]) are orthogonal`
    
  \implies
    # ... put proof steps here ... 
    
    x = ?
    


   5. Show that no [x; y] exists satisfying both of the below properties by deriving a contradiction (e.g., 1 = 0).
      HTML

      text

      load into verifier

      ∀ x,y ∈ R,
      

      (   x y   ) is a unit vector

      (   x⋅x y⋅y   ) and (   1 1   ) are orthogonal

      
      implies
      # ... put proof steps here ...
      

      ? # this should be a contradiction

      
      

      \forall x,y \in \R,
    
    `([x; y]) is a unit vector` 
    `([x*x; y*y]) and ([1; 1]) are  orthogonal`
    
  \implies
    # ... put proof steps here ... 
    
    ? # this should be a contradiction 
    


2. We have shown in lecture that R², together with vector addition and scalar multiplication, satisfies some of the vector space axioms. In this problem, you will show that the remaining axioms are satisfied.
   1. Finish the proof below showing that [0; 0] is a left identity for addition of vectors in R².
      HTML

      text

      load into verifier

      ∀ x,y ∈ R,
      # ... put proof steps here ...
      

      0 0   +   x y   =   x y

      
      

      \forall x,y \in \R,
  # ... put proof steps here ... 
  
  [0; 0] + [x; y] = [x; y]
  


   2. Finish the proof below showing that [0; 0] is a right identity for addition of vectors in R².
      HTML

      text

      load into verifier

      ∀ x,y ∈ R,
      # ... put proof steps here ...
      

      x y   +   0 0   =   x y

      
      

      \forall x,y \in \R,
  # ... put proof steps here ... 
  
  [x; y] + [0; 0] = [x; y]
  


   3. Finish the proof below showing that 1 is the identity for scalar multiplication of vectors in R².
      HTML

      text

      load into verifier

      ∀ x,y ∈ R,
      # ... put proof steps here ...
      

      1 ⋅   x y   =   x y

      
      

      \forall x,y \in \R,
  # ... put proof steps here ... 
  
  1 * [x; y] = [x; y]
  


   4. Finish the proof below showing that the component-wise definition of inversion is consistent with the inversion axiom for vector spaces.
      HTML

      text

      load into verifier

      ∀ x,y ∈ R,
      # ... put proof steps here ...
      

      x y   + (−   x y   ) =   0 0

      
      

      \forall x,y \in \R,
  # ... put proof steps here ... 
  
  [x; y] + (-[x; y]) = [0; 0]
  


   5. Finish the proof below showing that the addition of vectors in R² is associative.
      HTML

      text

      load into verifier

      ∀ a,b,c,d,e,f ∈ R,
      # ... put proof steps here ...
      

      a b   + (   c d   +   e f   ) = (   a b   +   c d   ) +   e f

      
      

      \forall a,b,c,d,e,f \in \R,
  # ... put proof steps here ... 
  
  [a; b] + ([c; d] + [e; f]) = ([a; b] + [c; d]) + [e; f]
  


   6. Finish the proof below showing that the distributive property applies to vector addition and scalar multiplication for R².
      HTML

      text

      load into verifier

      ∀ s, x, y, x', y' ∈ R,
      # ... put proof steps here ...
      

      s (   x y   +   x' y'   ) = (s   x y   ) + (s   x' y'   )

      
      

      \forall s, x, y, x', y' \in \R,
  # ... put proof steps here ... 
  
  s ([x; y] + [x'; y']) = (s [x; y]) + (s [x'; y'])
  


3. Any point p on the line between vectors u and v can be expressed as a(u-v)+u for some scalar a. In fact, it can also be expressed as b(u-v)+v for some other scalar b. In this problem, you will prove this fact for R³.

   Given some p = a(u-v)+u, find a formula for b in terms of a so that p = b(u-v)+v. Add this formula to the beginning of the proof (after a = ) and then complete the proof.

   HTML

   text

   load into verifier

   ∀ a,b ∈ R, ∀ u,v,p ∈ R³,
   

   p	=	a (u − v) + u
   a	=	? # define a in terms of b

   
   implies
   # ... put proof steps here ...
   

   p = b (u − v) + v

   
   

   \forall a,b \in \R, \forall u,v,p \in \R^3,
    
    p  =  a (u - v) + u 
    a  =  ? # define a in terms of b 
    
  \implies
    # ... put proof steps here ... 
    
    p = b (u - v) + v
    


   The verifier's library contains a variety of derived algebraic properties for R and R³ in addition to the vector space axioms for R³. Look over them to see which might be useful.

---

2.4. Common vector properties, relationships, and operators

We introduce two new operations on vectors (e.g. u and v): the norm (|| ... ||) and the dot product (u ⋅ v). When interpreting some other structure, such as R², as a vector space, we must provide definitions for these operators in order to use them.

Notice that the dot product is a new, distinct form of multiplication (distinct from multiplication of real numbers, and distinct from scalar multiplication). Also notice that the two operations are related:

These operations can be shown to have various algebraic properties.

We also introduce several vector properties. Some deal with a single vector; some deal with two vectors; and some deal with three vectors.

In R², we can derive the linear independence of [x;y] and [x';y'] from the orthogonality of [x;y] and [x';y'] using a proof by contradiction.

In the case of vectors in R², the properties of linear dependence and orthogonality can be defined in terms of the slopes of the vectors involved. However, note that these definitions in terms of slope are a special case for R². The more general definitions (in terms of scalar multiplication and dot product, respectively) apply to any vectors in a vector space. Thus, we can derive the slope definitions from the more general definitions.

Orthogonal projections of vectors have a variety of interpretations and applications; one simple interpretation of the projection of a vector v onto a vector w is the shadow of vector v on w with respect to a light source that is orthogonal to w.

The above example can be generalized to an arbitrary vector v and unit vector u; then, it can be generalized to any vector u by using the fact that u/||u|| is always a unit vector.

2.5. Solving common problems involving vector algebra

We review the operations and properties of vectors introduced in this section by considering several example problems.

2.6. Using vectors and linear combinations to model systems

In the introduction we noted that in this course, we would define a symbolic language for working with a certain collection of idealized mathematical objects that can be used to model system states of real-world systems in an abstract way. Because we are considering a particular collection of objects (vectors, planes, spaces, and their relationships), it is natural to ask what kinds of problems are well-suited for such a representation (and also what problems are not well-suited).

What situations and associated problems can be modelled using vectors and related operators and properties? Problems involving concrete objects that have a position, velocity, direction, geometric shape, and relationships between these (particularly in two or three dimensions) are natural candidates. For example, we have seen that it is possible to compute the projection of one vector onto another. However, these are just a particular example of a more general family of problems that can be studied using vectors and their associated operations and properties.

A vector of real numbers can be used to represent an object or collection of objects with some fixed number of characteristics (each corresponding to a dimension or component of the vector) where each characteristic has a range of possible values. This range could be a set of magnitudes (e.g., position, cost, mass), a discrete collection of states (e.g., absence or presence of an edge in a graph), or even a set of relationships (e.g., for every cow, there are four cow legs; for every $1 invested, there is a return of $0.02). Thus, vectors are well-suited for representing problems involving many instances of objects where all the objects have the same set of possible characteristics along the same set of linear dimensions. In these instances, many vector operations also have natural interpretations. For example, addition and scalar multiplication (i.e., linear combinations) typically correspond to the aggregation of a property across multiple instances or copies of objects with various properties (e.g., the total mass of a collection of objects).

In order to illustrate how vectors and linear combinations of vectors might be used in applications, we recall the notion of a system. A system is any physical or abstract phenomenon, or observations of a phenomenon, that we characterize as a collection of real values along one or more dimensions. A system state or state a system is a particular collection of real values. For example, if a system is represented by R⁴, states of that system are represented by individual vectors in R⁴ (note that not all vectors need to correspond to valid or possible states; see the examples below).

Example: Suppose there is a network of streets and intersections and the city wants to set up cameras at some of the intersections. Cameras can only see as far as the next intersection. Suppose there are five streets (#1, #2, #3, #4, #5) and four intersections (A, B, C, and D) at which cameras can be placed, and the city wants to make sure a camera can see every street while not using any cameras redundantly (i.e., two cameras should not film the same street).

Vectors in R⁵ can represent which streets are covered by a camera. A fixed collection of vectors, one for each intersection, can represent what streets a camera can see from each intersection. Thus, the system's dimensions are:

• is street #1 covered by a camera?
• is street #2 covered by a camera?
• is street #3 covered by a camera?
• is street #4 covered by a camera?
• is street #5 covered by a camera?
• is there a camera at intersection A? (represented by the variable a below)
• is there a camera at intersection B? (represented by the variable b below)
• is there a camera at intersection C? (represented by the variable c below)
• is there a camera at intersection D? (represented by the variable d below)

Four fixed vectors will be used to represent which streets are adjacent to which intersections:

0 1 0 0 1   ,   1 0 1 1 0   ,   1 1 0 0 0   ,   1 0 0 1 1

Placing the cameras in the way required is possible if there is integer solution to the following equation involving a linear combination of the above vectors:

0 1 0 0 1   a +   1 0 1 1 0   b +   1 1 0 0 0   c +   1 0 0 1 1   d

=

1 1 1 1 1

The notion of a linear combination of vectors is common and can be used to mathematically model a wide variety of problems. Thus, a more concise notation for linear combinations of vectors would be valuable. This is one of the issues addressed by introducing a new type of term: the matrix.

---

3. Matrices

In this section we introduce a new kind of term: a matrix. We define some operations on matrices and some properties of matrices, and we describe some of the possible ways to interpret and use matrices.

3.1. Matrices and multiplication of a vector by a matrix

Matrices are a concise way to represent and reason about linear combinations and linear independence of vectors (e.g., setwise linear independence might be difficult to check using an exhaustive approach), reinterpretations of systems using different dimensions, and so on. One way to interpret a matrix is as a collection of vectors. Multiplying a matrix by a vector corresponds to computing a linear combination of that collection of vectors.

As an example, we consider the case for linear combinations of two vectors. The two scalars in the linear combination can be interpreted as a 2-component vector. We can then put the two vectors together into a single object in our notation, which we call a matrix.

Notice that the columns of the matrix are the vectors used in our linear combination. Notice also that we can now reinterpret the result of multiplying a vector by a matrix as taking the dot product of each of the matrix rows with the vector.

Because a matrix is just two column vectors, we can naturally extend this definition of multiplication to cases in which we have multiplication of a matrix by a matrix: we simply multiply each column of the second matrix by the first matrix and write down each of the resulting columns in the result matrix.

These definitions can be extended naturally to vectors and matrices with more than two components. If we denote using M_ij the entry in a matrix M found in the ith row and jth column, then we can define the result of matrix multiplication of two matrices A and B as a matrix M such that

Mij   =   ith row of A ⋅ jth column of B.

3.2. Interpreting matrices as tables of relationships and transformations of system states

We saw how vectors can be used to represent system states. We can extend this interpretation to matrices and use matrices to represent relationships between the dimensions of system states. This allows us to interpret matrices as transformations between system states (or partial observations of system states).

If we again consider the example system involving a barn of cows and chickens, we can reinterpret the matrix as a table of relationships between dimensions. Each entry in the table has a unit indicating the relationship it represents.

	chickens	cows
heads	1 head/chicken	1 head/cow
legs	2 legs/chicken	4 legs/cow

Notice that the column labels in this table represent the dimensions of an "input" vector that could be multiplied by this matrix, and the row labels specify the dimensions of the "output" vector that is obtained as a result. That is, if we multiply using the above matrix a vector that specifies the number of chickens and the number of cows in a system state, we will get a vector that specifies the number of heads and legs we can observe in that system.

1 head/chicken 1 head/cow 2 legs/chicken 4 legs/cow   ⋅   x chickens y cows

=

x+y heads 2x+4y legs

Thus, we can interpret multiplication by this matrix as a function that takes system states that only specify the number of chickens and cows, and converts them to system states that only specify the number of heads and legs:

3.3. Interpreting multiplication of matrices as composition of system state transformations

---

3.4. Assignment #2: Using Vectors and Matrices

In this assignment you will solve problems involving vectors and matrices. Please submit a single file a2.* 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. Consider the line L in R² that passes through the following two vectors:

   u	=	9 7
   v	=	1 -5

   1. Using set notation, define L in terms of u and v.
   2. Determine whether the following vectors are on the line L:

      25 31

      ,

      7 −1

      ,

      −3 −11

   3. Find all unit vectors orthogonal to L.
   4. Define the line L^⊥ that passes through the origin and is orthogonal to L using an equation of the form:

      y

      =

      m ⋅ x + b

      In other words, find m, b ∈ R such that:

      L⊥

      =

      {   x y     |   y = m ⋅ x + b }

2. For each of the following collections of vectors, determine whether the collection is linearly independent. If it is, explain why; if not, show that one of the vectors is a linear combination of the other vectors in the collection.
   1. The following two vectors in R²:

      2 1

      ,

      3 2

   2. The following three vectors in R²:

      -2 1

      ,

      1 3

      ,

      2 4

   3. The following three vectors in R⁴:

      2 0 4 0

      ,

      6 0 4 3

      ,

      1 7 4 3

3. Consider the following vectors in R³:

   u	=	3 7 9
   v	=	2 −5 3
   w	=	3 4 −3

   1. Compute the orthogonal projection of w onto the vector:

      1/√(12) 1/√(12) 1/√(12)

   2. Determine whether each of the following points lies on the plane perpendicular to u:

      3 0 -1

      ,

      7 -9 -5

      ,

      1 1 -1

   3. Extra credit: Given the vector v and w, let P be the plane orthogonal to v, and let Q be the plane orthogonal to w. Find a vector p ∈ R³ that lies on the line in R³ along which P and Q intersect, and provide a definition of the line.

4. You decide to drive the 2800 miles from New York to Los Angeles in a hybrid vehicle. A hybrid vehicle has two modes: using only the electric motor and battery, it can travel 1 mile on 3 units of battery power; using only the internal combustion engine, it can travel 1 mile on 0.1 liters of gas (about 37 mpg) while also charging the battery with 1 unit of battery power. At the end of your trip, you have 1400 fewer units of battery power than you did when you began the trip. How much gasoline did you use (in liters)?

   You should define a system with the following dimensions:

   • net change in the total units of battery power;
   • total liters of gasoline used;
   • total number of miles travelled;
   • number of miles travelled using the electric motor and battery;
   • number of miles travelled using the engine.

   You should define a matrix M ∈ R^3×2 to characterize this system. Then, write down an equation containing that matrix (and three variables in R), and solve it to obtain the quantity of gasoline.

   M ⋅   x y

   =

   ? ? ?

5. Suppose we create a very simple system for modelling how predators and prey interact in a closed environment. Our system has only two dimensions: the number of prey animals, and the number of predators. We want to model how the state of the system changes from one generation to the next.

   If there are x predators and y prey animals in a given generation, in the next generation the following will be the case:

   • all predators already in the system will stay in the system;
   • all prey animals already in the system will stay in the system;
   • for every prey animal, two new prey animals are introduced into the system;
   • for every predator, two prey animals are removed from the system;
   • we ignore any other factors that might affect the state (e.g., natural death or starvation).

   1. Specify explicitly a matrix T in R^2×2 that takes a description of the system state in one generation and produces the state of the system during the next generation. Note: you may simply enter the matrix on its own line for this part of the problem, but you must also use it in the remaining three parts below.

   2. Show that the number of predators does not change from one generation to the next.

      T ⋅   x y

      =

      x y'

   3. Determine what initial state [x₀; y₀] is such that there is no change in the state from one generation to another.

      T ⋅   x0 y0

      =

      x0 y0

   4. Suppose that in the fourth generation of an instance of this system (that is, after the transformation has been applied three times), we have 2 predators and 56 prey animals. How many predators and prey animals were in the system in the first generation (before any transformations were applied)? Let [x; y] represent the state of the system in the first generation. Set up a matrix equation that involves [x; y] and matrix multiplication, and solve it to obtain the answer.

---

3.5. Matrix operations and their interpretations

The following table summarizes the matrix operations that we are considering in this course.

term	definition	restrictions	general properties
M1 + M2	component-wise	matrices must have the same number of rows and columns	commutative, associative, has identity (matrix with all 0 components), has inverse (multiply matrix by -1), scalar multiplication is distributive
M1 ⋅ M2	row-column-wise dot products	columns in M1 = rows in M2 rows in M1 ⋅ M2 = rows in M1 columns in M1 ⋅ M2 = columns in M2	associative, has identity I (1s in diagonal and 0s elsewhere), distributive over matrix addition, not commutative in general, no inverse in general
M -1		columns in M = rows in M matrix is invertible	M -1 ⋅ M = M ⋅ M -1 = I

The following tables list some high-level intuitions about how matrix operations can be understood.

level of abstraction	interpretations of multiplication of a vector by a matrix
applications	transformation of system states	extraction of information about system states	computing properties of combinations or aggregations of objects (or system states)	conversion of system state observations from one set of dimensions to another
geometry	"moving" vectors in a space (stretching, skewing, rotating, reflecting)	projecting vectors	taking a linear combination of two vectors	reinterpreting vector notation as referring to a collection of non-canonical vectors

level of abstraction	interpretations of multiplication of two matrices
applications	composition of system state transformations or conversions
geometry	sequencing of motions of vectors within a space (stretching, skewing, rotating, reflecting)

level of abstraction	invertible matrix		singular matrix
applications	reversible transformation of system states	extraction of complete information uniquely determining a system state	irreversible transformation of system states	extraction of incomplete information about a system state
geometry	reversible transformation or motion of vectors in a space		projection onto a strict subset of a set of vectors (space)
symbolic	reversible transformation of information numerically encoded in matrix (example of such information: system of linear equations encoded as matrix)		irreversible/"lossy" transformation of information encoded in matrix

Suppose we interpret multiplication of a vector by a matrix M as a function from vectors to vectors:

3.6. Matrix properties

The following are subsets of R^n×n that are of interest in this course because they correspond to transformations and systems that have desirable or useful properties. For some of these sets of matrices, matrix multiplication and inversion have properties that they do not in general.

subset of Rn×n	definition	closed under matrix multiplication	properties of matrix multiplication	inversion
identity matrix	∀ i,j     Mij = 1 if i=j, 0 otherwise	closed	commutative, associative, distributive with addition, has identity	has inverse (itself); closed under inversion
elementary matrix	can be obtained via an elementary row operation from I: add nonzero multiple of one row of the matrix to another row multiply a row by a nonzero scalar swap two rows of the matrix Note: the third is a combination of the first two operations.		associative, distributive with addition, have identity	have inverses; closed under inversion
scalar matrices	∃ s ∈ R, ∀ i,j     Mij = s if i=j, 0 otherwise	closed	commutative, associative, distributive with addition, have identity	nonzero members have inverses; closed under inversion
diagonal matrices	∀ i,j     Mij ∈ R if i=j, 0 otherwise	closed	associative, distributive with addition, have identity	nonzero members have inverses; closed under inversion
matrices with constant diagonal	∀ i,j     Mii = Mjj		associative, distributive with addition, have identity
symmetric matrices	∀ i,j     Mij = Mji		associative, distributive with addition, have identity
symmetric matrices with constant diagonal	∀ i,j     Mii = Mjj and Mij = Mji	closed	commutative, associative, distributive with addition, have identity
upper triangular matrices	∀ i,j     Mij = 0 if i > j	closed	associative, distributive with addition, have identity	not invertible in general; closed under inversion when invertible
lower triangular matrices	∀ i,j     Mij = 0 if i < j	closed	associative, distributive with addition, have identity	not invertible in general; closed under inversion when invertible
invertible matrices	∃ M -1 s.t. M -1 M = M M -1 = I	closed	associative, distributive with addition, have identity	nonzero members have inverses; closed under inversion
square matrices	all of Rn×n	closed	associative, distributive with addition, have identity

Two facts presented in the above table are worth noting.

Another fact not in the table is also worth noting.

Given the last fact, we might ask whether the opposite is true: are all invertible matrices the product of a finite number of elementary matrices? The answer is yes, as we will see further below.

3.7. Solving the equation M v = w for M with various properties

Recall that for v,w ∈ Rⁿ and M ∈ R^n×n, an equation of the following form can represent a system of equations:

Notice that if M is invertible, we can solve for v by multiplying both sides by M ^-1. More generally, if M is a member of some of the sets in the above table, we can find straightforward algorithms for solving such an equation for v.

M is ...	algorithm to solve M v = w for v
the identity matrix	w is the solution
an elementary matrix	perform a row operation on M to obtain I; perform the same operation on w
a scalar matrix	divide the components of w by the scalar
a diagonal matrix	divide each component of w by the corresponding matrix component
an upper triangular matrix	start with the last entry in v, which is easily obtained; move backwards through v, filling in the values by substituting the already known variables
a lower triangular matrix	start with the first entry in v, which is easily obtained; move forward through v, filling in the values by substituting the already known variables
product of a lower triangular matrix and an upper triangular matrix	combine the algorithms for upper and lower triangular matrices in sequence (see example below)
an invertible matrix	compute the inverse and multiply w by it

3.8. Row echelon form and reduced row echelon form

We define two more properties that a matrix may possess.

M is in row echelon form	all nonzero rows are above any rows consisting of all zeroes the first nonzero entry (from the left) of a nonzero row is strictly to the right of the first nonzero entry of the row above it all entries in a column below the first nonzero entry in a row are zero (the first two conditions imply this)
M is in reduced row echelon form	M is in row echelon form the first nonzero entry in every row is 1; this 1 entry is the only nonzero entry in its column

We can obtain the reduced row echelon form of a matrix using a sequence of appropriately chosen elementary row operations.

Question: For a given matrix in reduced row echelon form, how many different matrices can be reduced to it (one or more than one)?

The above result implies the following fact.

The following table summarizes the results.

fact				justification
(1)	{M | M is a finite product of elementary matrices}	=	{M | rref M = I}	I is an elementary matrix; sequences of row operations are equivalent to multiplication by elementary matrices
(2)	{M | M is a finite product of elementary matrices}	⊂	{M | M is invertible}	elementary matrices are invertible; products of invertible matrices are invertible
(3)	{M | rref M = I}	⊂	{M | M is invertible}	fact (1) in this table; fact (2) in this table; transitivity of equality
(4)	{M | M is invertible}	⊂	{M | rref M = I}	proof by contradiction; non-invertible M implies rref M has all zeroes in bottom row
(5)	{M | M is invertible}	=	{M | rref M = I}	for any sets A,B, A ⊂ B and B ⊂ A implies A = B
(6)	{M | M is a finite product of elementary matrices}	=	{M | M is invertible}	fact (1) in this table; fact (5) in this table; transitivity of equality

Given all these results, we can say that the properties for a matrix M in the following table are all equivalent: if any of these is true, then all of them are true. If any of these is false, then all of them are false.

M is invertible

det  M ≠ 0

the columns of M are (setwise) linearly independent

Mv = w has exactly one solution

M is a finite product of elementary matrices

If E₁ ,..., E_n are all lower triangular, then then M has an LU decomposition. However, this will not always be the case. But recall that E₁ ,..., E_n are all elementary matrices.

3.9. Matrix transpose

3.10. Orthogonal matrices

Below, we provide a verifiable argument of the above fact for the R^2×2 case.

We can summarize this by adding another row to our table of matrix subsets.

subset of Rn×n	definition	closed under matrix multiplication	properties of matrix multiplication	inversion
orthogonal matrices	M⊤ = M -1	closed	associative, distributive with addition, have identity	nonzero members have inverses; closed under inversion

3.11. Matrix rank

Yet another way to characterize matrices is by considering their rank.

We will see in this course that rank M is related in many ways to the various characteristics of a matrix.

We will not prove the above in this course in general, but typical proofs involve first proving that for all A ∈ R^n×n, rank A ≤ rank (A^⊤). Why is this sufficient to complete the proof? Because we can apply this fact for both A and A^⊤ and use the fact that (A^⊤)^⊤ = A:

rank(A)	≤	rank(A⊤)
rank(A⊤)	≤	rank((A⊤)⊤)
rank(A⊤)	≤	rank(A)
rank(A⊤)	=	rank(A)

To get some intuition about the previous fact, we might consider the following question: if the columns of a matrix M ∈ R^2×2 are linearly independent, are the rows also linearly independent?

The following table summarizes the important facts about the rank and rref operators.

rank (rref M) = rank M

rref (rref M ) = rref M

rank (M⊤) = rank M

for M ∈ Rn×n, M is invertible iff rank M = n

---

3.12. Assignment #3: Matrix Properties and Operations

In this assignment you will use Python to implement several of the vector and matrix operations and predicates we have introduced so far. Please submit a single file a3.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.

1. In this assignment, we will represent vectors as Python tuples. For example, the vector [1;2;3] would be represented in Python as (1,2,3).
   1. Define a Python function scale(s,v) that takes two arguments: a scalar s and a vector v. The function should return the result of multiplying the vector by the scalar.

      scale(2, (3,4,5))     # Returns (6,8,10).

   2. Define a Python function norm(v) that takes a vector argument v and returns its norm (i.e., its length).
      
      
   3. Define a Python function dot(v,w) that takes two vectors as arguments and returns their dot product. If the two vectors do not have the same number of components, the function should return None.
      
      Include a comment explaining exactly how many addition operations and how many multiplication operations your implementation performs when the input is a pair of vectors that each have n components.

      dot((1,2), (3,4))     # Returns 11.
      dot((5,1,0), (1,1,2)) # Returns 6.
      dot((5,1,0,4), (1,2)) # Returns None.

   4. Define a Python function orthogonal(v,w) that takes two vectors as arguments and returns True only if the two input vectors are orthogonal to one another; if they are not orthogonal, it returns False. If the two vectors do not have the same number of components, the function should return None.
      
      
   5. Define a Python function proj(v,w) that takes two vectors as arguments and returns a vector that is the projection of v onto w.
2. In this assignment, we will represent matrices as tuples of tuples. For example, the matrix

   1 2 3 4

   would be represented as ((1,2),(3,4)):
   1. Define a Python function mult(A,B) that takes two matrix arguments and returns the matrix that is the result of multiplying A by B. If either argument is not a valid matrix, or if the two matrices cannot be multiplied because the number of rows and/or columns does not match as necessary, the function should return None.
      
      Include a comment explaining exactly how many addition operations and how many multiplication operations your implementation performs when the input is a pair of matrices that each have n rows and columns.

      mult(((1,2),(3,4)), ((-5,-6),(7,8)))     # Returns ((9,10),(13,14)).

   2. Define a Python function upper(A) that takes a matrix argument and returns True only if the matrix A is upper triangular; otherwise, it returns False.
   3. Define a Python function transpose(A) that takes a matrix argument and returns the transpose of that matrix.
   4. Define a Python function lower(A) that takes a matrix argument and returns True only if the matrix A is lower triangular; otherwise, it returns False.
   5. Define a Python function symmetric(A) that takes a matrix argument and returns True only if the matrix A is symmetric; otherwise, it returns False.
   6. Define a Python function orthogonal(A) that takes a matrix argument and returns True only if the matrix A is orthogonal; otherwise, it returns False. You may name this function orthogonal2() if all your tests are at the end of your file and you don't want this definition to hide the definition of orthogonal() from Problem #1(d) above.
3. In this problem you will implement functions that can be used to generate elementary matrices corresponding to the three types of elementary row operations. In matrices, the first row is indexed as i = 1 (unlike tuples and lists in Python). Thus, you will need to convert the row indices i and j into the corresponding Python tuple indices. Hint: begin with the identity matrix and apply the row operation to that matrix.
   
   1. Define a Python function elementary_swap(r,c,i,j). This function should take four integer arguments:
      • r is the number of rows
      • c is the number of columns;
      • i and j are the two rows to swap.
      The function should return a single matrix that can then be used to swap row i with row j by using matrix multiplication. See example below.

      mult(elementary_swap(3,3,1,3), ((1,2,3), (0,0,0), (7,8,9))) # Returns ((7,8,9), (0,0,0), (1,2,3)).

   2. Define a Python function elementary_scale(r,c,i,s). This function should take four integer arguments:
      • r and c are the row and column counts, respectively;
      • i is the row to scale;
      • s is the scalar to use.
      The function should return a single matrix that can then be used to scale row i using the scalar s. See example below.

      mult(elementary_scale(2,2,2,-1), ((1,2), (3,4))) # Returns ((1,2), (-3,-4)).

   3. Define a Python function elementary_add(r,c,i,j,s). This function should take four integer arguments:
      • r and c are the row and column counts, respectively;
      • i is the row to add to row j;
      • s is the scalar with which to scale row i before adding it to row j.
      The function should return a single matrix that can then be used to add a multiple (by s) of row i to row j. See example below.

      mult(elementary_add(3,3,1,2,-1), ((1,2,3), (0,0,0), (7,8,9))) # Returns ((1,2,3), (-1,-2,-3), (7,8,9)).

4. Define a Python function is_rref(A) that takes a matrix argument A and returns True only if A is in reduced row echelon form; otherwise, it returns False.

---

---

Review 1. Vector and Matrix Algebra and Applications

The following is a breakdown of what you should be able to do at this point in the course (and of what you may be tested on in an exam). Notice that many of the tasks below can be composed. This also means that many problems can be solved in more than one way.

• vectors
  • definitions and algebraic properties of scalar and vector operations (addition, multiplication, etc.)
  • vector properties and relationships between vectors
    • dot product of two vectors
    • norm of a vector
    • unit vectors
    • orthogonal projection of a vector onto another vector
    • orthogonal vectors
    • linear dependence of two vectors
    • linear independence of two vectors
    • linear combinations of vectors
    • linear independence of three vectors
  • lines and planes
    • line defined by a vector and the origin ([0; 0])
    • line defined by two vectors
    • line in R² defined by a vector orthogonal to that line
    • plane in R³ defined by a vector orthogonal to that plane
• matrices
  • algebraic properties of scalar and matrix multiplication and matrix addition
  • collections of matrices and their properties (e.g., invertibility, closure)
    • identity matrix
    • elementary matrices
    • scalar matrices
    • diagonal matrices
    • upper and lower triangular matrices
    • matrices in reduced row echcelon form
    • determinant of a matrix in R^2×2
    • inverse of a matrix and invertible matrices
  • other matrix operations and properties
    • determine whether a matrix is invertible
      • using the determinant for matrices in R^2×2
      • using facts about rref for matrices in R^n×n
    • algebraic properties of matrix inverses with respect to matrix multiplication
    • transpose of a matrix
      • algebraic properties of transposed matrices with respect to matrix addition, multiplication, and inversion
    • matrix rank
  • matrices in applications
    • solve an equation of the form LU = w
    • matrices and systems of states
      • interpret partial observations of system states as vectors
      • interpret relationships betweem dimensions in a system of states as a matrix
      • given a partial description of a system state and a matrix of relationships, find the full description of the system state
      • interpret system state transitions/transformations over time as matrices
        • population growth/distributions over time
          • compute the system state after a specifieds amount of time
          • find the fixed point of a transition matrix

Below is a comprehensive collection of review problems going over the course material covered until this point. These problems are an accurate representation of the kinds of problems you may see on an exam.

---

4. Vector Spaces

We are interested in studying sets of vectors because they can be used to model sets of system states, observations and data that might be obtained about systems, geometric shapes and regions, and so on. We can then represent real-world problems (e.g., given some observations, what is the actual system state) as equations of the form M ⋅ v = w, and sets of vectors as the collections of possible solutions to those equations. But what is exactly the set of possible solutions to M ⋅ v = w? Can we characterize it precisely? Can we define a succinct notation for it? Can we say anything about it beyond simply solving the equation? Does this tell us anything about our system?

In some cases, it may make more sense to consider only a finite set of system states, or an infinite set of discrete states (i.e., only vectors that contain integer components); for example, this occurs if vectors are used to represent the number of atoms, molecules, cows, chickens, power plants, single family homes, and so on. However, in this course, we make the assumption that our our sets of system states (our models of systems) are infinite and continuous (i.e., not finite and not discrete); in this context, this simply means that the entries in the vectors we use to represent system states are real numbers.

Notice that the assumption of continuity means that, for example, if we are looking for a particular state (e.g., a state corresponding to some set of observations), we allow the possibility that the state we find will not correspond exactly to a state that "makes sense". Consider the example problem involving the barn of cows and chickens. Suppose we observe 4 heads and 9 legs. We use the matrix that represents the relationships between the various dimensions of the system to find the number of cows and chickens:

1 1 2 4   ⋅   x chickens y cows	=	4 heads 9 legs
x	=	3.5
y	=	0.5

Notice that the solution above is not an integer solution; yet, it is a solution to the equation we introduced because the set of system states we are allowing in our solution space (the model of the system) contains all vectors in R², not just those with integer entries.

As we did with vectors and matrices, we introduce a succinct language (consisting of symbols, operators, predicates, terms, and formulas) for infinite, continuous sets of vectors. And, as with vectors and matrices, we study the algebraic laws that govern these symbolic expressions.

4.1. Sets of vectors and their notation

We will consider three kinds of sets of vectors in this course; they are listed in the table below.

kind of set (of vectors)	maximum cardinality ("quantity of elements")	solution space of a...	examples
finite set of vectors	finite		{(0,0)} {(2,3),(4,5),(0,1)}
vector space	infinite	homogenous system of linear equations:   M ⋅ v = 0	{(0,0)} R R2 span{(1,2),(2,3),(0,1)} any point, line, or plane intersecting the origin
affine space	infinite	nonhomogenous system of linear equations:   M ⋅ v = w	{ a + v | v ∈ V} where V is a vector space and a is a vector any point, line, or plane

To represent finite sets of vectors symbolically, we adopt the convention of simply listing the vectors between a pair of braces (as with any set of objects). However, we need a different convention for symbolically representing vector spaces and affine spaces. This is because we must use a symbol of finite size to represent a vector space or affine space that may contain an infinite number of vectors.

If the solution spaces to equations of the form M ⋅ v = w are infinite, continuous sets of vectors, in what way can be characterize them? Suppose that M ∈ R^2×2 and that is M invertible. Then we have that:

M	=	a b c d
w	=	s t
M ⋅ v	=	w
a b c d   ⋅ v	=	s t
v	=	(1/(ad-bc)) ⋅   d −b −c a   ⋅   s t
v	=	(s/(ad−bc)) ⋅   d −c   + (t/(ad−bc)) ⋅   −b a

Notice that the set of possible solutions v is a linear combination of two vectors in R². In fact, if a collection of solutions (i.e., vectors) to the equation M ⋅ v = 0 exists, it must be a set of linear combinations (in the more general case of M ⋅ v = w, it is a set of linear combinations with some specified offset). Thus, we introduce a succinct notation for a collection of linear combinations of vectors.

Recall the definition for what constitutes a vector space (there are many equivalent definitions).

Given the two facts above, we can safely adopt span{v₁, ..., v_n} as a standard notation for vector spaces. In addition to this notation, we will also often use the notation Rⁿ for specific values of n (e.g., R² is equivalent to span{[1;0],[0;1]}), and {0} for specific vector 0 (e.g., {[0;0]} is equivalent to span{[0;0]}).

4.2. Membership and equality relations involving sets of vectors

Recall that many of the algebraic laws we saw governing operators on vectors and matrices involved equality of vectors and matrices. In fact, one can view these laws as collectively defining the semantic equality of the symbols (i.e., they specify when two symbols refer to the same object).

The meaning of symbols is closely tied to the equality relation we define over them. In the case of the span notation, one potential problem is that there is more than one way to describe a set using span notation. For example:

span {   2 3   }	=	span {   4 6   }
span {   1 0   ,   0 1   }	=	span {   2 1   ,   0 -1   }

How can we determine if two spans are equivalent? We must define the equality relation (i.e., the relational operator) that applies to sets of vectors (including infinite sets containing all linear combinations of vectors). We first recall the definition of equality for our vector notation.

With the equality of pairs of vectors defined, it is possible to provide a definition of equality for sets of vectors (both finite and infinite). However, we will build the definition gradually. First, let us define when a vector is a member of a finite set of vectors using vector equality.

Notice that the above defines membership of v in the set using an equation (in this case, v = w_i where i ∈ {1,...,k}). We can take the same approach in the case of an infinite set of vectors.

Now suppose we want to determine if a finite set of vectors is a subset of a span. Let us first consider how we would check if a finite set of vectors is a subset of another finite set of vectors.

Thus, we can generalize the above by replacing the second finite set of vectors with a span.

The above implies that a matrix can be used to represent a particular vector space. We will see in other sections further below that a given vector space can be represented in more than one way by a matrix, and that more than one matrix can be used to represent a vector space.

4.3. Vector spaces as abstract structures

Our definitions of a vector space so far have explicitly referenced sets of concrete vectors as we usually understand them. However, this is not necessary.

The above definition specifies conditions under which any set of objects S can be studied as a vector space.

We have encountered many sets that satisfy the above properties (thus making them vector spaces); below is a table of vector spaces, including vector spaces we have already encountered and vector spaces we will encounter later in the course.

vector space	addition operation	additive identity	scalar multiplication operation
R	addition of real numbers	0	multiplication of real numbers
R2	vector addition: [ a ; b ] + [ c ; d ] = [ a + c ; b + d ]	[ 0 ; 0 ]	scalar multiplication: s ⋅ [ a ; b ] = [ s ⋅ a ; s ⋅ b ]
R3	vector addition: [ a ; b ; c ] + [ d ; e ; f ] =           [ a + d ; b + e ; c + f ]	[ 0 ; 0 ; 0]	scalar multiplication: s ⋅ [ a ; b ; c ] = [ s ⋅ a ; s ⋅ b ; s ⋅ c ]
Rn	vector addition: [ a1 ; ... ; an ] + [ b1 ; ... ; bn ] =           [ a1 + b1 ; ... ; an + bn ]	[ 0 ; ... ; 0 ]	scalar multiplication: s ⋅ [ a1 ; ... ; an ] = [ s ... a1 ; ... ; s ⋅ an ]
span { [0;0] } = { [0;0] }	vector addition	[0;0]	scalar multiplication of vectors in R2
span { v1 , ... , vk } ⊂ Rn	vector addition	[ 0 ; ... ; 0 ]	scalar multiplication of vectors in Rn
R2×2	matrix addition	[ 0 , 0 ; 0 , 0 ]	scalar multiplication of a matrix
Rn×n	matrix addition	[ 0, ..., 0 ; ... ; 0, ..., 0 ]	scalar multiplication of a matrix
affine space with origin at a ∈ R2	v ⊕ w = (v - a) + (w - a) + a	a	s ⊗ v = s ⋅ (v - a) + a
set of lines through the origin f(x) = a x	f ⊕ g = h where h(x) = f(x) + g(x)	f(x) = 0 ⋅ x	s ⊗ f = h where h(x) = s × f(x)
set of polynomials of degree 2 f(x) = a x2 + b x + c	f ⊕ g = h where h(x) = f(x) + g(x)	f(x) = 0	s ⊗ f = h where h(x) = s × f(x)
set of polynomials of degree k f(x) = ak xk + ... + a0	f ⊕ g = h where h(x) = f(x) + g(x)	f(x) = 0	s ⊗ f = h where h(x) = s × f(x)

An abstract definition of vector spaces is useful because it also allows us to study by analogy and learn about other objects that are not necessarily sets of vectors. All the properties we can derive about vector spaces using the above definition will apply to other sets of objects that also satisfy the above definition.

The disadvantage to using the approach presented in this subsection to fitting functions to data points is that the data must match an actual function perfectly (or, equivalently, the space of functions being considered must be rich enough to contain a function that can fit the data points exactly). We will see further below how to find functions that have the "best" fit (for one particular definition of "best") without necessarily matching the points exactly.

---

4.4. Assignment #4: Vector Spaces and Polynomials

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 Rⁿ and matrices in R^n×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 { v₁, ..., v_k } in the notation span { v₁, ..., v_k }.

   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 R². If there are k + 1 vectors in the input, the function should find a polynomial of the form f(x) = a_k x^k + ... + a₁ x + a₀ that exactly fits these vectors. The function should return a single vector (a_k, ..., a₁, a₀) 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) = a_k x^k + ... + a₁ x + a₀ that represents the function f, the function should return a vector (a_k, ..., a₁, a₀) 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) = a_k x^k + ... + a₁ x + a₀ that represents the function f, the function should return a vector (a_k, ..., a₁, a₀) 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.

---

4.5. Basis, dimension, and orthonormal basis of a vector space

We have adopted span{v₁,...,v_n} as our notation for vector spaces. However, this makes it possible to represent a given vector space in a variety of ways:

We might naturally ask: given a vector space V, what is the smallest possible size for a finite set of vectors W such that V = span W?

Recall that for any vector v ∈ Rⁿ and any unit vector u ∈ Rⁿ, (v ⋅ u) ⋅ u is the projection of v onto the line parallel to u (i.e., the vector space {a u | a ∈ R}). We can use this fact to define a process for turning an arbitrary basis into an orthonormal basis.

Many computational environments for mathematics that support linear algebra provide an operator for turning a basis into an orthonormal basis.

Why is an orthonormal basis useful? Once again, we appeal to the fact that (v ⋅ u) ⋅ u is the projection of v onto u, where v ⋅ u is the length of that projection. Suppose we want to determine how to express an arbitrary vector v using an orthonormal basis u₁,...,u_n.

4.6. Homogenous, non-homogenous, overdetermined, and underdetermined systems

While we have usually considered n × n matrices, in real-world applications (especially those involving data), system states usually have a shorter description than the corpus of data (e.g., observational data) being used to determine the system state. Thus, problems in such applications usually involve matrices in which the number of rows is very different from the number of columns. Furthermore, the data may be noisy, which means that there may be no exact system state that matches the data. Informally, this might mean that the system of equations being used to determine a system state is overdetermined. On the other hand, if the amount of data is not sufficient to determine a single system state, a system is underdetermined.

4.7. Application: approximating overdetermined systems

We see that we may have many choices for w' in changing an overdetermined system M ⋅ v = w to a system with at least one solution M ⋅ v' = w'. Above, we have introduced a notion of error so that we can compare the quality of different choices of w'. How can we pick the w' that minimizes the error ||w - w'||? Let us first define what the vector leading to the minimal error is.

How do we find w*?

Why is it called a "least-squares" approximate solution? In the table below, we summarize the correspondences used in the above facts.

concept related to solving MB x = v	notation	relationship	notation	geometric concept
the space of values W' with which we can replace w in the overdetermined system M v = w to make a system M v = w' that has solutions	{M ⋅ v | v ∈ Rn}	the span of the columns of M	span B	the subspace W' of W spanned by B
the error of an approximate solution v'	||w - M v' ||	M v' = w'	||w - w'||	the distance between w ∈ W and w' ∈ span B
M ⋅ v* where v* is the minimum error solution	for all v', ||w - M w* || ≤ ||w - M w' ||	M v* = w*	for all w' ∈ span B, ||w - w*|| ≤ ||w - w'||	the orthogonal projection w* of w ∈ W onto span B (the closest vector in span B to w)

Notice that we know a solution to M v* = w* exists, and that we can show this in two different ways. Since w* ∈ span B, it must be that w is a linear combination of the vectors in B, so it is a linear combination of the columns in M. Alternatively, if M is a square matrix and we know that B is a basis, then the columns of M are linearly independent, which means M is invertible, so

Relationship to curve fitting and linear regressions in statistics

The method described above does overlap with standard curve fitting and linear regression techniques you see in statistics. There are many variants to these approaches, and the one considered above corresponds to a fairly basic variant that has no specialized characteristics (i.e., it makes no special assumptions about the data points, the relative importance of the data points, their distribution, or the way they can be interpreted).

• The approach above is known as ordinary least squares and as linear least squares.
• The case in which the function space is {f | f(x) = ax + b, a,b ∈ R} corresponds to a simple linear regression. This involves fitting a line to a collection of points while minimizing the sum of the squares of the distances parallel to the y-axis between all the data points and the approximate line. This diagram is an illustration of this. The method in these notes is more general in that it is not restricted to polynomials of order 1, but can be used to fit polynomials of any order to data.
• We can restate the least squares method described in these notes as finding x* such that the vector ε in M x* = v - ε is minimized. Notice that ε + w = v. The length of the vector ε can be viewed as the sum of squares of y-axis-aligned distances from the estimate curve to the actual data points:
  ||ε|| = ||v - M x*||.

• This diagram illustrates the projection method being used.
• The matrix M in M x = v is sometimes called the design matrix. The same term is used to refer to the corresponding matrix in a simple linear regression.

4.8. Application: approximating a model of system state dimension relationships

The approach described in the previous section can be used to approximate a solution to the equation M v = w. Usually, if M describes a model of a system (in this sense, system refers to a system of states that are described by values along some number of dimensions), solving M v = w corresponds to determining a system state v given some other information about a system state w.

What if we instead have a large collection of pairs of observations of system states of the form (v,w) (or, more generally, any collection of observations of a system along multiple dimensions). Can we approximate a model of a set of relationships between some two subsets of the dimensions in the system? In other words, if we take all our observations (x₁, ..., x_n) and divide them into pairs of descriptions x = (x₁,...,x_k) and v = (x_k+1,...,x_n), can we find the best M that approximates the relationship between incomplete system state descriptions x and v?

4.9. Application: distributed computation of least-squares approximations

4.10. Orthogonal complements and algebra of vector spaces

Notice that the orthogonal complement of a subspace is always taken within the context of some specified space V. We consider vector spaces, their orthogonal complements, and common set operations: set union, set intersection, and set product.

---

5. Linear Transformations

5.1. Set products, relations, and maps

We consider the following sets of vectors and their properties.

construct	definition	example	graphical example
V × W	{ (v,w) | v ∈ V, w ∈ W }	{1,2,3} × {4,5,6} = {(1,4),(1,5),(1,6), (2,4),(2,5),(2,6), (3,4),(3,5),(3,6)}
R is a relation between V and W	R ⊂ V × W	{(1,D), (2,B), (2,C)} is a relation between {1,2,3,4} and {A,B,C,D}
f is a function from V to W f is a map from V to W	f is a relation between V and W and ∀ v ∈ V, there is at most one w ∈ W s.t. f relates v to w	{ (x,f(x)) | f(x) = x2 }
R -1 is the inverse of R	{ (w,v) | (v,w) ∈ R }
f: X → Y is injective
f: X → Y is surjective
f: X → Y is bijective

Notice that we may have f such that f is a function, but f ^-1 is not a function.

Notice that the definition of f does not uniquely determine its codomain. For example, f(x) = x² could have a codomain of R if f : R → R, or it could have a codomain of R⁺ if f : R → R⁺.

Notice that the above does not mean that there is not some V' where V ⊂ V' that does have a solution to the equation f(v) = w. For example, f(x) = 3 x is surjective if f ∈ R → R but not surjective if f ∈ Z → Z.

5.2. Homomorphisms and isomorphisms

The previous section defined a number of properties of functions f: A → B that only address the equality of elements in A and B. However, what if A and B have relations and operators? For example, what if A and B are vector spaces with an identity, an addition operation, and a scalar multiplication operation?

We can restrict our notion of a map or function to maps or functions f: A → B that somehow preserve or consistently transform the properties of operators and relations we may have already defined on A and B. For example, suppose we have A = {a₁, a₂, a₃}, B = {b₁, b₂, b₃}, an operator ⊕ such that a₁ ⊕ a₂ = a₃, and an operator ⊕ over elements of B such that b₃ ⊕ b₂ = b₁. A map f from A to B that preserves (or respects, or consistently transforms) ⊕ would be such that

f(a3) = b1

f(a2) = b2

f(a1) = b3

Notice that the above map is such that the operation ⊕ is respected by the map f:

f(a3)      =      f(a1 ⊕ a2)      =      f(a1) ⊕ f(a2)      =      b3 ⊕ b2      =      b1

5.3. Linear transformations

In this course we are interested in a specific kind of homomorphism.

5.4. Orthogonal projections as linear transformations

---

5.5. Assignment #5: Approximations and Linear Transformations

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 : R³ → R² where:

      f(v)

      =

      1 2 0 2 4 1   ⋅ v

   2. The linear transformation f : R² → R² where:

      f(v)

      =

      1 0 0 0   ⋅ v

   3. The linear transformation f : R⁵ → R¹ where:

      f(v)

      =

      0 0 0 1 2   ⋅ v

   4. The linear transformation f : R² → R² 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 x² + 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 (x_i, y_i) 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 [x₁; ...; x₁₀₀] 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 [y₁; ...; y₁₀₀] onto the two column vectors of the matrix. Each engineer computes the following values using the data available to them:

   ||   x1 ⋮ x50   ||	=	3		x1 ⋅ y1 + ... + x50 ⋅ y50	=	62		y1 + ... + y50	=	120
   ||   x51 ⋮ x100   ||	=	4		x51 ⋅ y51 + ... + x100 ⋅ y100	=	38		y51 + ... + y100	=	80

   1. Once the engineers compute the projection of [y₁; ...; y₁₀₀] onto span of the vector [x₁; ...; x₁₀₀], 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 [y₁; ...; y₁₀₀] 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?

---

5.6. Matrices as linear transformations

5.7. Application: communication

We want to transmit information, but we have constraints (e.g., security or high cost of transmission). Suppose we have two linear transformations f : V → W and f ^-1 : W → V such that f ^-1 o f is a bijection (and, thus, an isomorphism). If im(f) has some desirable property that the domain of f does not possess (e.g., it is obscured, or it has a smaller representation size), we can use f as an encoding function for the information we want to transmit, and f ^-1 as a decoding function.

5.8. Affine spaces and affine transformations

We are interested in studying solution spaces of systems of the form M ⋅ v = w. However, these are not vector spaces because they do not always contain 0 (i.e., the origin). Recall that if a solution space of a system does contain 0, the solution space is a vector space and M ⋅ v = w must be a homogenous system where w = 0.

How do we find an isomorphism between an affine space and a parallel vector space?

5.9. Fixed points, eigenvectors, and eigenvalues

We introduce several properties of linear transformations; these properties it possible to work with linear transformations in new and convenient ways.

We can generalize the notion of a fixed point by observing that a fixed point is just a vector on which the linear transformation acts as a scalar multiplier (in the case of a fixed point, the multiplier is 1). If v is a fixed point of f, then we have that:

What if we created another notion that was not restricted to 1?

Eigenspaces have many other applications. In particular, they make it possible to provide "natural" interpretations of general notions of concepts such as differentiation in the context of vector spaces.

---

Review 2. Vector and Matrix Algebra, Vector Spaces, and Linear Transformations

The following is a breakdown of what you should be able to do at the end of the course (and of what you may be tested on in an exam). Notice that many of the tasks below can be composed. This also means that many problems can be solved in more than one way.

• vectors
  • definitions and algebraic properties of scalar and vector operations (addition, multiplication, etc.)
  • vector properties and relationships between vectors
    • dot product of two vectors
    • norm of a vector
    • unit vectors
    • orthogonal projection of a vector onto another vector
    • orthogonal vectors
    • linear dependence of two vectors
    • linear independence of two vectors
    • linear combinations of vectors
    • linear independence of three vectors
  • lines and planes
    • line defined by a vector and the origin ([0; 0])
    • line defined by two vectors
    • line in R² defined by a vector orthogonal to that line
    • plane in R³ defined by a vector orthogonal to that plane
• matrices
  • algebraic properties of scalar and matrix multiplication and matrix addition
  • collections of matrices and their properties (e.g., invertibility, closure)
    • identity matrix
    • elementary matrices
    • scalar matrices
    • diagonal matrices
    • upper and lower triangular matrices
    • matrices in reduced row echcelon form
    • determinant of a matrix in R^2×2
    • inverse of a matrix and invertible matrices
  • other matrix operations and properties
    • determine whether a matrix is invertible
      • using the determinant for matrices in R^2×2
      • using facts about rref for matrices in R^n×n
    • algebraic properties of matrix inverses with respect to matrix multiplication
    • transpose of a matrix
      • algebraic properties of transposed matrices with respect to matrix addition, multiplication, and inversion
    • matrix rank
  • matrices in applications
    • solve an equation of the form LU = w
    • matrices and systems of states
      • interpret partial observations of system states as vectors
      • interpret relationships betweem dimensions in a system of states as a matrix
      • given a partial description of a system state and a matrix of relationships, find the full description of the system state
      • interpret system state transitions/transformations over time as matrices
        • population growth/distributions over time
          • compute the system state after a specifieds amount of time
          • find the fixed point of a transition matrix
• vector spaces
  • vector spaces and their properties
    • given a set of vectors or other objects, show that it is a vector space
    • express a vector space as a span of a finite set of vectors
    • given two vector spaces defined using span notation, show one is a subspace of the other
    • given two vector spaces defined using span notation, show they are equal
    • find the basis of a vector space
    • find an orthonormal basis of a vector space
    • find the dimension of a vector space
    • find the orthogonal complement of a vector space
  • particular vector spaces
    • the set of polynomials {f | f(x) = a_k x^k + ... + a₁ x + a₀, a₁,...,a_k ∈ R}
    • the solution set of an equation { v | M ⋅ v = w }
  • affine spaces
  • find the least-squares approximation of an overdetermined linear system
• linear transformations
  • determine if a relation is a map
  • determine if a map is a linear transformation
  • given a linear transformation (and/or its matrix representation)...
    • show it is injective
    • show it is surjective
    • show it is bijective
    • find its image (a vector space)
    • find its space of fixed points
    • find its eigenvalues
    • find its eigenvector for a given eigenvalue
  • compositions of linear transformations and their properties
  • compute orthogonal projections...
    • onto the span of a single vector in Rⁿ
    • onto a subspace of Rⁿ...
      • by first computing an orthonormal basis and then using it to find the projection
      • by using the formula M ⋅ M^⊤ if M has orthonormal columns
      • by using the formula M ⋅ (M^⊤ ⋅ M) ^-1 ⋅ M^⊤
• applications and solving systems of equations
  • curve fitting
    • find a polynomial curve that exactly fits a given set of points in R²
    • find a least-squares approximate polynomial curve that best fits a set of points in R²

Below is a comprehensive collection of review problems going over the material covered in this course. These problems are an accurate representation of the kinds of problems you may see on an exam.

---

Extra Problems

In this assignment you will solve problems involving underdetermined systems and eigenvectors. All problems count as extra credit; there is no penalty (in terms of your overall course grade) for not completing this assignment.

Please submit a single file a6.* 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. Consider the following vector subspaces of R³:

   V	=	span {   1 0 -2   }
   W	=	span {   4 1 2   }

   You are in a spaceship positioned at:

   p

   =

   20 15 -30

   1. Suppose a transmitter's signal beam only travels in two opposite directions along V. What is the shortest distance your spaceship must travel to intercept the signal beam?
   2. Suppose the transmitter is also rotating around the axis collinear with W. What is the shortest distance your spaceship must travel to reach a position at which it can hear the signal?
2. Consider the following underdetermined system:

   -2 4 4 -8   ⋅   x y

   =

   -8 16

   1. Define an isomorphism between the solution space W of the above equation and a parallel vector space V. You must provide a definition of both the vector space and the isomorphism.
   2. Suppose that the cost of a solution vector v to the above system is defined to be ||p − v|| where

      p

      =

      1 5

      What is the solution to the above system that has the lowest cost?
3. Suppose that vectors in R² represent population quantities in two locations (e.g., x is the number of people in the city and y is the number of people in the suburbs), the linear transformation f:R² → R² represents a change in the quantities over the course of one year if the economy is doing well, g:R² → R² represents a change in the quantities over the course of one year if the economy is not doing well, and v₀ is the initial state:

   f(v)	=	2 1 4 2   ⋅ v
   g(v)	=	0.1 0.2 0.4 0.3   ⋅ v
   v0	=	100 200

   The population state is initially v₀; after 302 years have passed, the total number of years with a good economy was 100 and the total number of years with a poor economy was 202. What is the state of the population distribution at this point?
4. As above, let vectors in R² be system state descriptions that represent population quantities in two locations, and let f represent a change in the quantities over the course of one year if the economy is doing well, and let g represents a change in the quantities over the course of one year if the economy is not doing well:

   f(v)	=	60 120 20 40   ⋅ v
   g(v)	=	0.06 0.12 0.02 0.04   ⋅ v
   v0	=	3 1
   v100	=	300000 100000

   If the initial state is v₀ and after 100 years the state is v₁₀₀, during how many years of this period was the economy doing well?

---

---

Appendix A. Notes on tools

This section contains some useful information and comments about some of the tools you may employ in this course.

Aartifact

Aartifact is an interactive logic and algebra verifier developed within the Boston University Computer Science Department that runs inside a web browser.

Syntactic layout of an argument: Each formula in an argument starts on an un-indented line (a line with no spaces at the beginning). Thus, it is possible to process multiple formulas simultaneously. See example below.

Each formula consists of one or more lines; the first line is unindented, while all subsequent lines in the formula are indented. Each new line after a quantifier represents a subformula; each new line is assumed to begin with an and logical operator that connects that subformula to the subformulas on the lines above it.

An implies logical operator should appear on its own line. All lines above implies are premises. All lines below it are the conclusions.

Output: The results of a verification process are color-coded:

• assumption (assumed to be true);
• true (due to logical and algebraic properties);
• unknown (may be true or false);
• false;
• contradiction (both true and false).

See the example below.

Python

Python is a programming language; an interpreter for Python can be downloaded here: http://www.python.org/download/. In this section we present some examples of Python functions.

Below is a function that returns the jth column of a matrix as a vector. You may find this function useful when completing Assignment #3.

def matrix_column(m, j):
    # Users will specify j as a matrix column
    # in the range {1,...,n}. Since Python uses
    # 0-indexing, we adjust.
    j = j - 1
    
    # v will be the column vector.
    v = [0 for i in range(0,len(m))]
     
    for i in range(0,len(m)): # for each row
        v[i] = m[i][j]
 
    return tuple(v)
 
matrix_column( ((1,2,3),(4,5,6),(7,8,9)), 2) # Returns (2, 5, 8).

Below is a more concise definition of the above function.

def matrix_column(m, j):
    return tuple([m[i][j-1] for i in range(0,len(m))])

Below is one way to implement vector addition.

def plus(u, v):
    if len(u) != len(v):
        return None
 
    w = [0 for x in u]
    for i in range(0,len(u)):
        w[i] = u[i] + v[i]
 
    return tuple(w)
 
# Example.
plus ((1,2), (3,4)) # Returns (4,6).

Below is a more concise implementation of both vector addition and vector subtraction.

def plus(u, v):
    if len(u) != len(v):
        return None
 
    return tuple([u[i] + v[i] for i in range(0,len(u))])
 
def minus(u, v):
    if len(u) != len(v):
        return None
 
    return tuple([u[i] - v[i] for i in range(0,len(u))])

We can use the vector addition function to implement matrix addition.

def plus_matrix(a, b):
    if len(a) != len(b): # Number of rows does not match.
        return None
 
    # We can add the rows using vector addition.
    # Notice we do not need to check that lengths
    # match because it is checked by plus().
    return tuple([plus(a[row], b[row]) for row in range(0,len(a))])

Below is a more complex function that checks if two vectors with any number of components are linearly dependent.

# This helper function returns True only if the
# vector consists of all 0 components (i.e., it
# is the origin).
def is_zero(v):
    for i in range(0,len(v)):
        if v[i] != 0:
            return False
    return True
 
# The following function checks if u and v are linearly dependent.
def lin_dep(u, v):
    # Make sure vectors have same number of components,
    # and at least two components.
    if len(u) != len(v) or len(u) < 2 or len(v) < 2:
        return None
 
    # We want to solve v*s = u for s, if possible.
    # We break v*s = u into a series of equations
    # containing s:
    #
    #   u[0] * s = v[0]
    #   u[1] * s = v[1]
    #     ...
    #   u[n] * s = v[n]
    #
    # The same s should work for all of the equations
    # above.
 
    # Until we determine what s should be, we set it
    # to None.
 
    s = None
 
    # If either vector is the (0,...,0) vector,
    # then u*s = v or v*s = u can be solved with s = 0,
    # so they are trivially linearly dependent.
 
    if is_zero(u) or is_zero(v):
        return True
 
    # At this point, s != 0, since the above case
    # handles the s = 0 cases.
 
    # We want to solve v*s = u and s != 0.
    # Look for an equation that determines s, or
    # if s is known, make sure it is a solution for
    # each equation.
    for i in range(0,len(u)):
        if (u[i] == 0 or v[i] == 0) and u[i] != v[i]:
            # One is zero, the other is not;
            # since s != 0, there is no way to
            # solve for s.
            return False
        else:
            if s == None:
                # We haven't found an s yet
                # (only zeroes so far).
                s = u[i] / v[i]
            elif s != u[i] / v[i]:
                return False
 
    return True

The function below checks if the first vector u is on the line defined by v and w. This occurs only if the vector minus(v,w) is linearly dependent with minus(u,w) (or with minus(u,v)).

def vector_on_line_between(u,v,w):
    return lin_dep(minus(v,w), minus(u,w))