Solutions-to-due-2016-05-06.sagews

Math 480 - Grading due 6pm on May 13, 2016

%typeset_mode True
%html
<font color="red"><h1>HOMEWORK TOTAL: 70 POINTS</h1></font>

HOMEWORK TOTAL: 70 POINTS

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.

%html
<font color="red"><h2>10 Points Total</h2>
<h4>Part A (3 points)</h4>
<p>Award:
    <ul>
        <li>3 points for a correct solution with solve</li>
        <li>2 points for a nearly correct solution (like a typo)</li>
        <li>1 point for some incorrect work with the wrong approach</li>
    </ul>
</p>
<h4>Part B (7 points)</h4>
<p>Award:
    <ul>
        <li>7 points for all parts being correct</li>
        <li>5 points for one part being incorrect</li>
        <li>3 points for 2 parts being incorrect</li>
        <li>1 point for no parts correct but they did some work</li>
    </ul>
</p>
</font>

10 Points Total

Part A (3 points)

Award:

• 3 points for a correct solution with solve
• 2 points for a nearly correct solution (like a typo)
• 1 point for some incorrect work with the wrong approach

Part B (7 points)

Award:

• 7 points for all parts being correct
• 5 points for one part being incorrect
• 3 points for 2 parts being incorrect
• 1 point for no parts correct but they did some work

# a
%var a, b, c, d
solve((a+3*b-2*c+7*d==-12, -a-5*b-2*d==389, -5*a-2*b+3*c+d==0, 3*a+8*b-d==4), a, b, c, d)[0]

[$\displaystyle a = \left(-3485\right)$, $\displaystyle b = \left(\frac{24014}{21}\right)$, $\displaystyle c = \left(-\frac{96790}{21}\right)$, $\displaystyle d = \left(-\frac{27527}{21}\right)$]

# b
# (1)
"Part 1 b:"
A = matrix([[1,3,-2,7], [-1,-5,0,-2], [-5,-2,3,1], [3,8,0,-1]])
v = vector([-12, 389, 0, 4])
A.solve_right(v)

# (2)
show("Part 2 b:")
A.inverse()*v

# (3)
show("Part 3 b:")
B = A.augment(v)
B.rref()

Part 1 b:

$\displaystyle \left(-3485,\,\frac{24014}{21},\,-\frac{96790}{21},\,-\frac{27527}{21}\right)$

Part 2 b:

$\displaystyle \left(-3485,\,\frac{24014}{21},\,-\frac{96790}{21},\,-\frac{27527}{21}\right)$

Part 3 b:

$\displaystyle \left(\begin{array}{rrrrr} 1 & 0 & 0 & 0 & -3485 \\ 0 & 1 & 0 & 0 & \frac{24014}{21} \\ 0 & 0 & 1 & 0 & -\frac{96790}{21} \\ 0 & 0 & 0 & 1 & -\frac{27527}{21} \end{array}\right)$

Problem 2 -- compute some kernels

Let $A$ and $B$ be the following two $3\times 3$ matrices. [ A = $$\begin{bmatrix} 6 & 12 & 42 \\ 2 & 4 & 14 \\ 3 & 6 & 21 \end{bmatrix}$$ \qquad B = $$\begin{bmatrix} 7 & 6 & 13 \\ 42 & 36 & 78 \\ 14 & 12 & 26 \end{bmatrix}$$ ]

• a. Use Sage to compute the $V=\ker(A)$ and $W=\ker(B)$.

• b. Use Sage to compute $V\cap W$ and $V + W$.

• c. Create a 3d plot that illustrates each kernel (which should be a plane), and the intersection of the two kernels (which should be a line). Make sure that your range is centered about the origin.

10 Points Total

Parts A and B (3 points each)

Award:

• 3 points for a correct solution
• 2 points for a nearly correct solution (like a typo)
• 1 point for some incorrect work with the wrong approach

Part B (4 points)

Award:

• 1 point for each component of the plot (each plane and the intersection)
• 1 point for completion.

# a
A = matrix([[6,12,42], [2,4,14], [3,6,21]])
B = matrix([[7,6,13], [42,36,78], [14,12,26]])

V = kernel(A)
show(V)
W = kernel(B)
show(W)

$\displaystyle \mathrm{RowSpan}_{\Bold{Z}}\left(\begin{array}{rrr} 1 & 0 & -2 \\ 0 & 3 & -2 \end{array}\right)$

$\displaystyle \mathrm{RowSpan}_{\Bold{Z}}\left(\begin{array}{rrr} 2 & 0 & -1 \\ 0 & 1 & -3 \end{array}\right)$

# b
show(V.intersection(W))
show(V+W)

$\displaystyle \mathrm{RowSpan}_{\Bold{Z}}\left(\begin{array}{rrr} 14 & 9 & -34 \end{array}\right)$

$\displaystyle \mathrm{RowSpan}_{\Bold{Z}}\left(\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right)$

# c
a = vector([1,0,-2])
b = vector([0,3,-2])
%var s,t
X = parametric_plot3d(s*a + t*b, (s,-1.65,1.65), (t,-1,1), color='yellow', opacity=0.3)

c = vector([2,0,-1])
d = vector([0,1,-3])
Y = parametric_plot3d(s*c + t*d, (s,-1.3,1.3), (t,-1,1), color='lightgreen', opacity=0.9)

v = vector([14,9,-34])
Z = parametric_plot3d(s*v, (s,-0.14,0.14), color='red')
show(X + Y + Z)

3D rendering not yet implemented

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.

10 Points Total

Part A (7 points)

Award:

• 4 points for correctly generating the matrices.
• 3 points for correclty using %timeit

Part B (3 points)

Award:

• 2 points for some data
• 1 point for an appropriate guess based on their data

# a
A = random_matrix(ZZ, 10, 10, x=0, y=2)
B = random_matrix(ZZ, 100, 100, x=0, y=2)
C = random_matrix(ZZ, 500, 500, x=0, y=2)
D = random_matrix(ZZ, 1000, 1000, x=0, y=2)

reset('timeit')
%timeit A.determinant()

625 loops, best of 3: 101 ns per loop

reset('timeit')
%timeit B.determinant()

625 loops, best of 3: 99.2 ns per loop

reset('timeit')
%timeit C.determinant()

5 loops, best of 3: 191 ns per loop

reset('timeit')
%timeit D.determinant()

5 loops, best of 3: 0 ns per loop

For an nxn matrix, the approximate number of digits in the determinant seems to be about N Approximately linear.

# Computed for part b.
# They should have some computed data here.

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$.

10 Points Total

All parts (2 points each)

Award points based on correct output.

#  a.
M = matrix(QQ, 4, [1/2, 0, -1, 0, 1, 1/2, 1, 1, 0, 1, -1, -1, 2, 1, -2, 1])
f = M.charpoly()
f

$\displaystyle x^{4} - x^{3} - \frac{19}{4} x^{2} + 6 x - \frac{5}{4}$

# b.
f(M)

$\displaystyle \left(\begin{array}{rrrr} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right)$

# c
r = f.roots(SR)
show(r[0])

($\displaystyle -\frac{1}{2} \, {\left(\frac{1}{36} i \, \sqrt{773} \sqrt{6} - \frac{5}{8}\right)}^{\frac{1}{3}} {\left(i \, \sqrt{3} + 1\right)} - \frac{-19 i \, \sqrt{3} + 19}{24 \, {\left(\frac{1}{36} i \, \sqrt{773} \sqrt{6} - \frac{5}{8}\right)}^{\frac{1}{3}}}$, $\displaystyle 1$)

# d
E = M.eigenvalues()
show(E)

[$\displaystyle 1$, $\displaystyle -2.300719103558421?$, $\displaystyle 0.2671728756506578?$, $\displaystyle 2.033546227907764?$]

# e
show(E[0]*E[1]*E[2]*E[3])
show(M.determinant())
show(E[0]*E[1]*E[2]*E[3] == M.determinant())

$\displaystyle -1.250000000000000?$

$\displaystyle -\frac{5}{4}$

$\displaystyle \mathrm{True}$

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.

20 Points Total

Part A (12 points)

Award:

• 12 points if their soloution works for N = 1, 2, 3, 4, 5.
• 10 points if they just missed a negative sign in their formula.
• 8 points if their solution seems like it's going towards the given solution.
• 1 - 6 points depending on how much of an attempt they made.

Part B (4 points)

Award:

• 4 points if they correctly count the correct number of timesa 1x1 matrix is computed.
• 2 points if they count the number of times `my_det` is called instead.

Part C (2 points)

Award:

• 2 points for N!
• 1 point for anything else with a reasonable argument

Part D (2 points)

Award:

• 2 points for "no" and and a short explanation.
• 1 point for just a no.

# Solution - 5
from collections import Counter
count = 0
def my_det(M):
	global count
	if M.nrows() == 1:
		count += 1
		return M[0][0]
	total = 0
	for col in range(M.ncols()):
		minor = M.delete_rows([0]).delete_columns([col])
		total += (-1)**(col) * M[0][col] * my_det(minor)
	return total

for n in [1..5]:
    count = 0
    A = random_matrix(QQ, n)
    z = my_det(A)
    print n, count

1 1 2 2 3 6 4 24 5 120

The computational complexity is N!

reset ('timeit')
# Part D
%timeit random_matrix(ZZ, 10).determinant()
%timeit random_matrix(ZZ, 100).determinant()
%timeit random_matrix(ZZ, 500).determinant()

625 loops, best of 3: 29.1 µs per loop 25 loops, best of 3: 8.49 ms per loop 5 loops, best of 3: 1 s per loop

No; it would be way slower.

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.

10 Points Total

For parts A, B, and C, you just need to check that they gave a solution.

Part A (3 points)

Award:

• 1 point per call.

Part B (3 points)

Award:

• 1 point per explanation.

Part C (3 points)

Award:

• 1 point per example.

Part D (1 point)

No output is necessary

Award:

• 1 point if they said yes for all of them.
• 0.5 points if they missed one
• 0 otherwise.

F = matrix([[-1,-1,-1,-2],[-1,-7,-5,-1],[-3,0,0,0],[1,-1,2,9]])
F

$\displaystyle \left(\begin{array}{rrrr} -1 & -1 & -1 & -2 \\ -1 & -7 & -5 & -1 \\ -3 & 0 & 0 & 0 \\ 1 & -1 & 2 & 9 \end{array}\right)$

# 6a.
show(F.gram_schmidt())
show(F.rref())
show(F.LU())

($\displaystyle \left(\begin{array}{rrrr} -1 & -1 & -1 & -2 \\ \frac{8}{7} & -\frac{34}{7} & -\frac{20}{7} & \frac{23}{7} \\ -\frac{762}{307} & \frac{15}{307} & \frac{63}{307} & \frac{342}{307} \\ 0 & -\frac{153}{254} & \frac{221}{254} & -\frac{17}{127} \end{array}\right)$, $\displaystyle \left(\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ \frac{15}{7} & 1 & 0 & 0 \\ \frac{3}{7} & -\frac{24}{307} & 1 & 0 \\ -\frac{20}{7} & \frac{209}{307} & \frac{809}{762} & 1 \end{array}\right)$)

$\displaystyle \left(\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array}\right)$

($\displaystyle \left(\begin{array}{rrrr} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{array}\right)$, $\displaystyle \left(\begin{array}{rrrr} 1 & 0 & 0 & 0 \\ \frac{1}{3} & 1 & 0 & 0 \\ -\frac{1}{3} & \frac{1}{7} & 1 & 0 \\ \frac{1}{3} & \frac{1}{7} & -\frac{2}{19} & 1 \end{array}\right)$, $\displaystyle \left(\begin{array}{rrrr} -3 & 0 & 0 & 0 \\ 0 & -7 & -5 & -1 \\ 0 & 0 & \frac{19}{7} & \frac{64}{7} \\ 0 & 0 & 0 & -\frac{17}{19} \end{array}\right)$)

• Use Gram-Schmidt in projecting vectors onto subspaces

• Use rref to find kernels of matrices, and solve systems of equations

• Wikipedia says "LU is also a key step when inverting a matrix"... so many students will say that.

%typeset_mode False
#6d.
# yes, they all work for 100x100 matrices over ZZ.  See:
B = random_matrix(ZZ, 100, x=0, y=2)
B.gram_schmidt()
B.rref()
B.LU()

(100 x 100 dense matrix over Rational Field, 100 x 100 dense matrix over Rational Field) 100 x 100 dense matrix over Rational Field (100 x 100 sparse matrix over Integer Ring, 100 x 100 dense matrix over Rational Field, 100 x 100 dense matrix over Rational Field)