In order to successfully complete this assignment you need to participate both individually and in groups during class. If you attend class in-person then have one of the instructors check your notebook and sign you out before leaving class. If you are attending asyncronously, turn in your assignment using D2L no later than 11:59pm on the day of class. See links at the end of this document for access to the class timeline for your section.
In-Class Assignment: Determinants¶
Image from:http://www.mathnstuff.com/
Agenda for today's class (80 minutes)¶
</p>
3. Algorithm to calculate the determinant¶
Consider the following recursive algorithm (algorithm that calls itself) to determine the determinate of a $n\times n$ matrix $A$ (denoted $|A|$), which is the sum of the products of the elements of any row or column. i.e.:
$$i\text{th row expansion: } |A| = a_{i1}C_{i1} + a_{i2}C_{i2} + \ldots + a_{in}C_{in} $$$$j\text{th column expansion: } |A| = a_{1j}C_{1j} + a_{2j}C_{2j} + \ldots + a_{nj}C_{nj} $$where $C_{ij}$ is the cofactor of $a_{ij}$ and is given by:
$$ C_{ij} = (-1)^{i+j}|M_{ij}|$$and $M_{ij}$ is the matrix that remains after deleting row $i$ and column $j$ of $A$.
Here is some code that tries to implement this algorithm.
## Import our standard packages packages
%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
import sympy as sym
sym.init_printing(use_unicode=True)
import copy
import random
def makeM(A,i,j):
''' Deletes the ith row and jth column from A'''
M = copy.deepcopy(A)
del M[i]
for k in range(len(M)):
del M[k][j]
return M
def mydet(A):
'''Calculate the determinant from list-of-lists matrix A'''
if type(A) == np.matrix:
A = A.tolist()
n = len(A)
if n == 2:
det = (A[0][0]*A[1][1] - A[1][0]*A[0][1])
return det
det = 0
i = 0
for j in range(n):
M = makeM(A,i,j)
#Calculate the determinant
det += (A[i][j] * ((-1)**(i+j+2)) * mydet(M))
return det
The following code generates an $n \times n$ matrix with random values from 0 to 10.
Run the code multiple times to get different matrices:
#generate Random Matrix and calculate it's determinant using numpy
n = 5
s = 10
A = [[round(random.random()*s) for i in range(n)] for j in range(n)]
A = np.matrix(A)
#print matrix
sym.Matrix(A)
✅ **DO THIS:** Use the randomly generated matrix ($A$) to test the above mydet function and compare your result to the numpy.linalg.det function.
# Put your test code here
✅ **QUESTION:** Are the answers to mydet and numpuy.linalg.det exactly the same every time you generate a different random matrix? If not, explain why.
Put your answer here
✅ **QUESTION:** On line 26 of the above code, you can see that algorithm calls itself. Explain why this doesn't run forever.
Put your answer here
4. Using Cramer's rule to solve $Ax=b$¶
Let $Ax = b$ be a system of $n$ linear equations in $n$ variables such that $|A| \neq 0$. the system has a unique solution given by:
$$x_1 = \frac{|A_1|}{|A|}, x_2 = \frac{|A_2|}{|A|}, \ldots, x_n = \frac{|A_n|}{|A|}$$where $A_i$ is the matrix obtained by replacing column $i$ of $A$ with $b$. The following function generates $A_i$ by replacing the $i$th column of $A$ with $b$:
def makeAi(A,i,b):
'''Replace the ith column in A with b'''
if type(A) == np.matrix:
A = A.tolist()
if type(b) == np.matrix:
b = b.tolist()
Ai = copy.deepcopy(A)
for j in range(len(Ai)):
Ai[j][i] = b[j][0]
return Ai
✅ **DO THIS:** Create a new function called cramersRule, which takes $A$ and $b$ and returns $x$ using the Cramer's rule. Note: Use numpy and NOT mydet to find the required determinants. mydet is too slow.
# Stub code. Replace the np.linalg.solve code with your answer
def cramersRule(A,b):
detA = np.linalg.det(A)
x = []
#####Start of your code here#####
#####End of your code here#####
return x
✅ **QUESTION:** Test your cramersRule function on the following system of linear equations:
#Put your answer to the above quesiton here
✅ **QUESTION:** Verify the above answer by using the np.linalg.solve function:
#Put your answer to the above quesiton here
✅ **QUESTION:** Test your cramersRule function on the following system of linear equations and verify the answer by using the np.linalg.solve function:
#Put your answer to the above quesiton here
✅ **QUESTION:** Cramer's rule is a $O(n!)$ algorithm and the Gauss-Jordan (or Gaussian) elimination is $O(n^3)$. What advantages does Cramer's rule have over elimination?
Put your answer here.
Congratulations, we're done!¶
If you attend class in-person then have one of the instructors check your notebook and sign you out before leaving class. If you are attending remote, turn in your assignment using D2L.
Course Resources:¶
Written by Dirk Colbry, Michigan State University
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.