Math 480 - Homework 5: Due 6pm on May 6, 2016

There are SIX problems. All problems have equal weight except probelem 5 which has twice the weight of the others

Solve each problem using Sage unless otherwise indicated. In particular, if there is some linear algebra question, which you could easily do by hand or in your head, you should still show exactly how to solve it using Sage if possible. Of course, do always think with your brain!

Useful facts:

Sage quickref for linear algebra: https://wiki.sagemath.org/quickref?action=AttachFile&do=get&target=quickref-linalg.pdf
See sections 1.5, 4.4, 4.16, of Sage For Undergraduates.
You can make a 5x5 random 0,1 matrix in Sage by typing random_matrix(ZZ, 5, x=0, y=2).

Problem 1 -- solve a linear system in four variables both symbolically and using matrices

Consider the following system of linear equations

\begin{align*} a + 3b - 2c + 7d &= -12 \\ -a - 5b - 2d &= 389 \\ -5a - 2b + 3c + d &= 0 \\ 3a + 8b - d &= 4 \end{align*}

Solve this equation for rational numbers $a$ , $b$ , $c$ and $d$ in several ways using Sage:

a. Solve symbolically, using the solve command and symbolic variables (created using %var)
b. Solve using matrices, in the following three ways:
- (1) Create a 4x4 matrix $A$ and a vector $v$ and use A.solve_right(v). (As a double check, note that $\det(A)=-21$ .)
- (2) Multiply $v$ by the inverse of $A$ ,
- (3) Compute the reduced row echelon form of the augmented matrix [A|v] and read off the solution.

# a

# b

# a

# b

# c

Problem 3 -- how fast is linear algebra over $\ZZ$ ?

a. For $n=10, 100, 500, 1000$ , how long does it take Sage to compute the determinant of an $n\times n$ random $\{0,1\}$ -matrix over $\ZZ$ ?
b. Roughly how many digits does the determinant of a $n\times n$ random $\{0,1\}$ -matrix with over $\ZZ$ have? Compute some data and make a guess based on your data.

# a

# b

# Computed for part b.

Problem 4 -- Eigenvalues and eigenvectors of matrices $\QQ$

Let $M$ be the following matrix with rational entries $M = \left(\begin{array}{rrrr} \frac{1}{2} & 0 & -1 & 0 \\ 1 & \frac{1}{2} & 1 & 1 \\ 0 & 1 & -1 & -1 \\ 2 & 1 & -2 & 1 \end{array}\right)$

a. Use Sage to compute the characteristic polynomial $f(x)$ of $M$ .
b. Use Sage to verify that $f(M)=0$ . (This is a consequence of the Cayley-Hamilton theorem.)
c. Compute the roots of $f$ symbolically. Display one of them using the show command. You should see a big formula involving radical signs.
d. Use A.eigenvalues() to compute the roots of $f$ .
e. Verify that the product of the roots of the characteristic polynomial $f$ is equal to the determinant of $M$ .

#  a.
# ... Your code


# Define your function f above here.
# Do not change these two lines below.
f
show(f)

# b.

# c



show(root) # You'll need root defined correctly above.

# d

# e

Problem 5 -- Implement the horrible recursive "expansion by cofactors" algorithm to compute determinants

a. Implement a function called my_det that calculates the determinant of a matrix using the recursive "expansion by cofactors" algorithm (this is probably the way you learned to compute determinants in a Linear Algebra class). The Matrix methods delete_columns and delete_rows may come in handy. You can assume that your input is a square matrix. (Note: Do not cache intermediate results in your implementation.)
b. Count how many times your algorithm computes the determinant of a 1x1 matrix when you give as input...
- A 1x1 matrix
- A 2x2 matrix
- A 3x3 matrix
- A 4x4 matrix
- A NxN matrix (Here you should guess based on what you observe above.)
- (hint: you could make a counter and use the global python keyword)
c. What does this tell you about how the algorithm's compute time might scale based on the size of N? (computational complexity)
d. Time the computation of determinants of some random matrices using Sage (NOT your function); based on the compute times you observe, do you think Sage is using a version of your algorithm? Give a short (2-3 sentence) explanation.

# Solution - 5
def my_det(M):
	# do something with M here!
    pass # Delete this line when you write your solution

Problem 6 -- explore some matrix functions

Let $F$ be the following matrix over the rational numbers $\QQ$ : $F = \left(\begin{array}{rrrr} -1 & -1 & -1 & -2 \\ -1 & -7 & -5 & -1 \\ -3 & 0 & 0 & 0 \\ 1 & -1 & 2 & 9 \end{array}\right)$

For each of the following functions: F.gram_schmidt(), F.rref(), F.LU()

a. Evaluate the function on $F$ and see what you get.
b. Explain in your own words what the function does (you don't have to say anything about how it is implemented or works). E.g., why do you think it has the name it has?
c. How might you use this function to solve some problem in mathematics? I.e., what sort of problem might you solve?
d. Would the function "work" (finish in a few seconds) when given a $100\times 100$ random $\{0,1\}$ -matrix over $\ZZ$ ? No explanation is necessary for this part.