# 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.:

$i^{th}\text{ row expansion: } |A| = a_{i1}C_{i1} + a_{i2}C_{i2} + \ldots + a_{in}C_{in}$
$j^{th}\text{ 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)

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

QUESTION: On line 26 of the above code, you can see that algorithm calls itself. Explain why this doesn’t run forever.

## 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:

$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 = []

return x


QUESTION: Test your cramersRule function on the following system of linear equations:

$x_1 + 2x_2 = 3$
$3x_1 + x_2 = -1$
#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:

$x_1 + 2x_2 +x_3 = 9$
$x_1 + 3x_2 - x_3 = 4$
$x_1 + 4x_2 - x_3 = 7$
#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?