09 In-Class Assignment: Determinants¶
Image from:http://www.mathnstuff.com/
2. 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.:
where \(C_{ij}\) is the cofactor of \(a_{ij}\) and is given by:
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)
---------------------------------------------------------------------------
ModuleNotFoundError Traceback (most recent call last)
<ipython-input-1-4a6cc377cfd5> in <module>
1 ## Import our standard packages packages
----> 2 get_ipython().run_line_magic('matplotlib', 'inline')
3 import numpy as np
4 import matplotlib.pyplot as plt
5 import sympy as sym
~/REPOS/MTH314_Textbook/MakeTextbook/envs/lib/python3.9/site-packages/IPython/core/interactiveshell.py in run_line_magic(self, magic_name, line, _stack_depth)
2342 kwargs['local_ns'] = self.get_local_scope(stack_depth)
2343 with self.builtin_trap:
-> 2344 result = fn(*args, **kwargs)
2345 return result
2346
~/REPOS/MTH314_Textbook/MakeTextbook/envs/lib/python3.9/site-packages/decorator.py in fun(*args, **kw)
230 if not kwsyntax:
231 args, kw = fix(args, kw, sig)
--> 232 return caller(func, *(extras + args), **kw)
233 fun.__name__ = func.__name__
234 fun.__doc__ = func.__doc__
~/REPOS/MTH314_Textbook/MakeTextbook/envs/lib/python3.9/site-packages/IPython/core/magic.py in <lambda>(f, *a, **k)
185 # but it's overkill for just that one bit of state.
186 def magic_deco(arg):
--> 187 call = lambda f, *a, **k: f(*a, **k)
188
189 if callable(arg):
~/REPOS/MTH314_Textbook/MakeTextbook/envs/lib/python3.9/site-packages/IPython/core/magics/pylab.py in matplotlib(self, line)
97 print("Available matplotlib backends: %s" % backends_list)
98 else:
---> 99 gui, backend = self.shell.enable_matplotlib(args.gui.lower() if isinstance(args.gui, str) else args.gui)
100 self._show_matplotlib_backend(args.gui, backend)
101
~/REPOS/MTH314_Textbook/MakeTextbook/envs/lib/python3.9/site-packages/IPython/core/interactiveshell.py in enable_matplotlib(self, gui)
3511 """
3512 from IPython.core import pylabtools as pt
-> 3513 gui, backend = pt.find_gui_and_backend(gui, self.pylab_gui_select)
3514
3515 if gui != 'inline':
~/REPOS/MTH314_Textbook/MakeTextbook/envs/lib/python3.9/site-packages/IPython/core/pylabtools.py in find_gui_and_backend(gui, gui_select)
278 """
279
--> 280 import matplotlib
281
282 if gui and gui != 'auto':
ModuleNotFoundError: No module named 'matplotlib'
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
3. 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:
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.
Written by Dr. Dirk Colbry, Michigan State University
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.