Homework 3: Determinants and bases#

In order to successfully complete this assignment, you must follow all the instructions in this notebook and upload your edited ipynb file to D2L with your answers on or before 11:59am ET on Friday, March 24.

You may collaborate with other students in this course. However, you may only share ideas with each other, not code or answers.

Also, note that your section’s TA will run your code cells in order (top to bottom) in order to grade your homework submission. So please make sure your code cells work as you intend when you run them in order.

# Here are some libraries you may need to use
%matplotlib inline
import matplotlib.pylab as plt
import numpy as np
import sympy as sym
sym.init_printing(use_unicode=True)

# import for checking answers
from answercheck import checkanswer

1. Determinant, lines and areas (25 pts)#

✅ QUESTION 1a: (5 pts) Show that the equation of the line in $\mathbb{R}^2$ through distinct points $(x_1, y_1)$ and $(x_2, y_2)$ can be written as $$ \begin{vmatrix} 1 & x & y \\ 1 &x_1 & y_1 \\ 1 & x_2 & y_2 \end{vmatrix} =0 $$

Put your answer here

✅ QUESTION 1b: (5 pts) Find a $3\times 3$ determinant equation similar to that in the previous question that describes the equation of the line through $(x_1,y_1)$ with slope $m$.

Put your answer here

Fact: If $A$ is a $2\times 2$ matrix, the area of the parallelogram determined by the columns of $A$ is $|\det A|$.

✅ QUESTION 1c: (5 pts) Calculate the area of the parallelogram determined by the points $(-2,-2)$, $(0,3)$, $(4,-1)$ and $(6, 4)$, by first translating the parallelogram to one having the origin as a vertex, and then applying the formula above.

Put your answer here

✅ QUESTION 1d: (5 pts) Find a formula for the area of the triangle whose vertices are $(0,0)$, $(a_{11},a_{21})$, and $(a_{12},a_{22})$.

Hint: Think about how the area of the triangle is related to the area of the parallelogram with vertices $(0,0)$, $(a_{11},a_{21})$, $(a_{11}+a_{12},a_{21}+a_{22})$, and $(a_{12},a_{22})$.

Put your answer here

✅ QUESTION 1e: (5 pts) Let $T$ be the triangle with vertices at $(x_1, y_1)$, $(x_2, y_2)$ and $(x_3, y_3)$. Show that

\[\begin{split} \text{Area of }T = \frac{1}{2} \left|\det\begin{bmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 &1 \\ x_3 & y_3 & 1 \end{bmatrix} \right| \end{split}\]

Hint: Start by translating the triangle $T$ to the origin by subtracting $(x_3,y_3)$ from each vertex. Then, use the result in Question 1d.

Put your answer here

2. Matrix representation of vector spaces (24 pts)#

Consider the matrix $$ A=\begin{bmatrix} -2 & -5 & 8 & 0 & -17\\1 &3 & -5 & 1 & 5\\3 & 11 & -19 & 7 &1 \\ 1 & 7 & -13 & 5 & -3 \end{bmatrix} $$

✅ QUESTION 2a: (4 pts) Using Python, find the reduced row echelon form (RREF) of $A$.

# Put your code here

✅ QUESTION 2b: (4 pts) Find a basis for the rowspace $\text{row}(A)$, i.e. the span of the rows of $A$.

Put your answer here

✅ QUESTION 2c: (4 pts) Find a basis for the column space $\text{col}(A)$, i.e. the span of the columns of $A$.

Put your answer here

✅ QUESTION 2d: (4 pts) Find a basis for the null space $\text{null}(A)$, i.e. the set of all solutions to $A\vec{x} = \vec{0}$.

Put your answer here

✅ QUESTION 2e: (4 pts) What is the rank of $A$? How are the rank, dimension of the null space and the size of $A$ related?

Put your answer here

✅ QUESTION 2f: (4 pts) What is $\dim\left(\text{null}(A^T)\right)$? Justify your answer.

Put your answer here

3. Eigenvalues and eigenvectors: solving difference equations (51 pts)#

In this part of the HW, we will investigate a linear difference equation using eigenvalues and eigenvectors. We consider the linear differnce equation defined by the following iterative formula: $$f_{n+1} = 1.5f_{n}-0.5f_{n-1} \quad \text{for} \quad n = 1, 2, \ldots.$$ To start the sequence we need to set initial values $$ f_0=s_0,\,\,\,\,\, f_1=s_1,\,\,\,\,\, $$ where we leave $s_0$, $s_1$ as parameters that we can change.

✅ QUESTION 3a: (4 pts) To get a feel for how this recursive sequence behaves, let’s calculate the first few terms of the sequence using the initial values of $s_0 = 1$ and $s_1 = 2$.

Since $f_0 = s_0 = 1$ and $f_1 = s_1 = 2$, the $2$nd term of the sequence is

\[\begin{split}\begin{align*} f_2 &= 1.5f_1 - 0.5f_0 \\ &= 1.5 \cdot 2 - 0.5 \cdot 1 \\ &= 2.5 \end{align*}\end{split}\]

Using this recursive formula, calculate $f_3$, $f_4$, $f_5$, $f_6$, $f_7$, $f_8$, and $f_9$.

Put your answer here

✅ QUESTION 3b: (7 pts) Write a function that takes in a value of $n$ and the initial values $s_0$ and $s_1$, and then computes $f_n$ using the recursive formula.

# function to produce n-th number of the following sequence:
# f0=s0, f1=s1 (s0, s1 -- preset parameters)
# f_n =1.5* f_{n-1} -0.5*f_{n-2} 
# Input: n, s0, s1
# Return: f_n
def get_n_value( n, s0, s1 ):

    # handle special cases for the first three elements
    if n<0:
        return 0

    elif n==0:
        return s0
    
    elif n==1:
        return s1
    

    # the general case, n>1
    else:

        # ADD YOUR CODE HERE
        # STORE THE FINAL RESULT IN fn VARIABLE

        return fn

✅ QUESTION 3c: (2 pts) Test your function by running the code below to obtain the first ten elements of the sequence. Check that the first few terms match what you calculated above. If they don’t match, either your calculation above or your code is incorrect.

What pattern did you observe from the sequence?

# first ten entries in the sequence
for n in range(0,10):
    print(get_n_value(n, 1, 2) )

Put your answer here

✅ QUESTION 3d: (5 pts) Now our goal is to get a general formula for the solution $f_n$ using linear algebra tools and explain the pattern in the solution observed from the questions above. Since our sequence employs two previous elements in the recursive formula, we construct a two-dimensional vector: $$\vec{v}_n=\begin{bmatrix}f_n \\f_{n+1}\end{bmatrix} \quad \text{for} \quad n = 0, 1, \ldots.$$

Write down the $2\times2$ matrix $T$ that relates $\vec{v}_n$ and $\vec{v}_{n-1}$, so that $\vec{v}_n= T \vec{v}_{n-1} $, i.e.,

\[\begin{split}\underbrace{\begin{bmatrix}f_n \\f_{n+1}\end{bmatrix}}_{\large\vec{v}_n} = \underbrace{\begin{bmatrix}? & ? \\ ? & ?\end{bmatrix}}_{\large T}\underbrace{\begin{bmatrix}f_{n-1} \\f_n\end{bmatrix}}_{\large \vec{v}_{n-1}}.\end{split}\]

# Put your answer to the above question here

checkanswer.matrix( T, '449787f542057152c3d74843584beacf' );

✅ QUESTION 3e: (4 pts) Use numpy to calculate the eigenvalues and eigenvectors of the matrix $T$. Store them in variables eigvals and eigvecs.

# Put your answer to the above question here

✅ QUESTION 3f: (4 pts) Separate the two eigenvectors into two variables u1, u2. (numpy subroutines typically return a matrix whose columns are eigenvectors. Here you convert them into two two-element arrays.) Print the two vectors u1, u2, and their corresponding eigenvalues.

# Put your answer to the above question here

checkanswer.matrix(u1/np.sign(u1[0,0]),'162180acaf64d3032229d18adc8119bd')
checkanswer.matrix(u2/np.sign(u2[0,0]),'6c7eb8e5a1d428b2398e2cbad14296d5')

✅ QUESTION 3g: (5 pts) Now run the code below to generate two sequences defined by the same iterative formula $f_n = 1.5f_{n-1}-0.5f_{n-2}$. The first one is what we get by setting the initial values $s_0$ and $s_1$ such that $\begin{bmatrix}s_0 \\ s_1\end{bmatrix} = \vec{u}_1$, and the second sequence is what we get by setting the initial values $s_0$ and $s_1$ such that $\begin{bmatrix}s_0 \\ s_1\end{bmatrix} = \vec{u}_2$. What pattern do you notice in the two sequences? Can you relate this pattern to each of the eigenvalues?

print('first sequence')
for k in range(0,10):
    print( get_n_value(k, u1[0,0], u1[1,0]) )
    
print('\nsecond sequence')
for k in range(0,10):
    print( get_n_value(k, u2[0,0], u2[1,0]) )

Put your answer to the above question here.

✅ QUESTION 3h: (5 pts) One can check that the two eigenvectors $\vec{u}_1$ and $\vec{u}_2$ of $T$ form a basis of $\mathbb{R}^2$.

Expand the initial vector $$\vec{v}_0=\begin{bmatrix}s_0 \\ s_1\end{bmatrix}=\begin{bmatrix}1 \\ 2\end{bmatrix}$$ in the basis of the eigenvectors $(\vec{u}_1,\vec{u}_2)$. In other words, find scalars $c_1$ and $c_2$ such that $$ \vec{v}_0=c_1\vec{u}_1+c_2\vec{u}_2. $$ Store the resulting coefficients in variables c1, c2. Note that these need to be floats (not numpy matrices) to pass the checkanswers below.

# Put your answer to the above question here

checkanswer.basic(c1/np.sign(u1[0,0]),'aa4cabdaf41026fd57a9c75861fe32c9')
checkanswer.basic(c2/np.sign(u2[0,0]),'571cf3f345e662bacbbc8835451adf5c')

✅ QUESTION 3i: (8 pts) We can now derive a general formula for the $n$-th term of the sequence. Since we defined $$ \vec{v}_n=\begin{bmatrix}f_n \\ f_{n+1}\end{bmatrix}$$ we just need to find a formula for $\vec{v}_n$ and take the first component to get the formula for $f_n$.

If we let $\lambda_1$ be the eigenvalue corresponding to the eigenvector $\vec{u}_1$ and $\lambda_2$ be the eigenvalue corresponding to the eigenvector $\vec{u}_2$, then we have $T\vec{u}_1 = \lambda_1\vec{u}_1$ and $T\vec{u}_2 = \lambda_2\vec{u}_2$. In the Question 3.9, you were able to write $\vec{v}_0$ as a linear combination of $\vec{u}_1$ and $\vec{u}_2$, i.e. you found constants $c_0$ and $c_1$ such that $$\vec{v}_0 = c_1\vec{u}_1 + c_2\vec{u}_2.$$

We can also write $\vec{v}_1$ as a linear combination of $\vec{u}_1$ and $\vec{u}_2$ by performing the following steps: $$\begin{align*} \vec{v}_1 &= T\vec{v}_0 & \text{since we defined } \vec{v}_n = T\vec{v}_{n-1} \\ &= T(c_1\vec{u}_1+c_2\vec{u}_2) & \text{using the formula for } \vec{v}_0 \\ &= c_1T\vec{u}_1+c_2T\vec{u}_2 & \text{matrix-vector multiplication is linear} \\ &= c_1\lambda_1\vec{u}_1+c_2\lambda_2\vec{u}_2 & \text{since } T\vec{u}_1 = \lambda_1\vec{u}_1 \text{ and } T\vec{u}_2 = \lambda_2\vec{u}_2 \end{align*}$$

Using almost the exact same steps, we can write $\vec{v}_2$ as a linear combination of $\vec{u}_1$ and $\vec{u}_2$: $$\begin{align*} \vec{v}_2 &= T\vec{v}_1 & \text{since we defined } \vec{v}_n = T\vec{v}_{n-1} \\ &= T(c_1\lambda_1\vec{u}_1+c_2\lambda_2\vec{u}_2) & \text{using the formula for } \vec{v}_1 \\ &= c_1\lambda_1T\vec{u}_1+c_2\lambda_2T\vec{u}_2 & \text{matrix-vector multiplication is linear} \\ &= c_1\lambda_1^2\vec{u}_1+c_2\lambda_2^2\vec{u}_2 & \text{since } T\vec{u}_1 = \lambda_1\vec{u}_1 \text{ and } T\vec{u}_2 = \lambda_2\vec{u}_2 \end{align*}$$

And now, we can write $\vec{v}_3$ as a linear combination of $\vec{u}_1$ and $\vec{u}_2$: $$\begin{align*} \vec{v}_3 &= T\vec{v}_2 & \text{since we defined } \vec{v}_n = T\vec{v}_{n-1} \\ &= T(c_1\lambda_1^2\vec{u}_1+c_2\lambda_2^2\vec{u}_2) & \text{using the formula for } \vec{v}_2 \\ &= c_1\lambda_1^2T\vec{u}_1+c_2\lambda_2^2T\vec{u}_2 & \text{matrix-vector multiplication is linear} \\ &= c_1\lambda_1^3\vec{u}_1+c_2\lambda_2^3\vec{u}_2 & \text{since } T\vec{u}_1 = \lambda_1\vec{u}_1 \text{ and } T\vec{u}_2 = \lambda_2\vec{u}_2 \end{align*}$$

At this point, you can probably see the pattern and guess that the formula for $\vec{v}_n$ is $$ \vec{v}_{n}=c_1\lambda_1^{n}\vec{u}_1+c_2\lambda_2^{n}\vec{u}_2. $$ Sidenote: This can be proven rigorously using mathematical induction, but you do not need to do so for this homework.

Finally, we just need to take the first component of $\vec{v}_n$ to obtain $f_n$.

Do This: Write a function whose inputs are an index $n$, and the initial values $s_0$ and $s_1$, and computes $f_n$ using the above formula. Remember that the coefficients $c_1$ and $c_2$ which satisfy $$\vec{v}_0=\begin{bmatrix}s_0 \\ s_1\end{bmatrix} = c_1\vec{u}_1+c_2\vec{u}_2$$ will depend on the initial values $s_0$ and $s_1$.

# function to produce n-th number of the following sequence:
# f0=s0, f1=s1(s0, s1 -- preset parameters)
# by using direct formula
# Input: n, s0, s1
# Return: f_n
def get_n_formula( n, s0, s1 ):

    if n==0:
        return s0
    
    elif n==1:
        return s1
    
    
    # calculation starts with n>1
    
    # First, compute the basis coefficients c1 and c2 using the initial values s0 and s1
    
    # Then, calculate the vector v_n using the formula above
    
    # Finally, output the first component of v_n to get f_n
    
    fn = 0
    
    return fn

✅ QUESTION 3j: (1 pts) Test your code by running the cell below to get the first ten elements of the sequence (with initial values $s_0 = 1$ and $s_1 = 2$) using the direct formula. Compare with the pen and paper calculation and the function relying on the recursive formula you have written above. Compare with the results you get from Question 3.3. Are they the same?

# first ten entries in the sequence
for n in range(0,10): 
    print( get_n_formula(n, 1, 2) )

✅ QUESTION 3k: (1 pts) Further test your code by running the cell below to generate the first ten elements of two sequences following the same iterative formula, except the first sequence has initial values $s_0 = 512$ and $s_1 = 256$, while the second sequence has initial values $s_0 = 1$ and $s_1 = 1$. If your code for get_n_formula() is working correctly, the first ten elements of the first sequence should be $512, 256, 128, 64, 32, 16, 8, 4, 2, 1$, and the first ten elements of the second sequence should be all $1$’s.

# first ten entries in the two sequences sequence
print('first sequence')
for n in range(0,10): 
    print( get_n_formula(n, 512, 256) )
    
print('second sequence')
for n in range(0,10): 
    print( get_n_formula(n, 1, 1) )

✅ QUESTION 3l: (5 pts) Assuming your code worked correctly, congratulations! You have just used eigenvalue analysis to compute an explicit solution to a linear difference equation.

Use the function get_n_formula() you have written above to calculate the $40$-th element of the sequence with initial values $s_0 = 1$ and $s_1 = 2$. Store it in x and display the value. Now based on the values of $\lambda_1$ and $\lambda_2$ can you provide an explanation for why $f_{40}$ is extremely close to $3$? (HINT: think about the values of $\lambda_1^n$ and $\lambda_2^n$ when $n$ is large.)

# Put your code for the above question here

Put your answer here

CMSE/MTH 314 Course Website

Homework 3: Determinants and bases

Contents

Homework 3: Determinants and bases#

1. Determinant, lines and areas (25 pts)#

2. Matrix representation of vector spaces (24 pts)#

3. Eigenvalues and eigenvectors: solving difference equations (51 pts)#