18.2: Algorithm to calculate the determinant — Read

From LibreTexts, under CC BY-NC 4.0, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

Consider the following recursive algorithm (algorithm that calls itself) to determine the determinate of a \(n \times n\) matrix \(A\) (denoted \(\left| A \right|\)), 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} \nonumber \]

\[j\text{th column expansion: } |A| = a_{1j}C_{1j} + a_{2j}C_{2j} + \ldots + a_{nj}C_{nj} \nonumber \]

where \(C_{ij}\) is the cofactor of \(a_{ij}\) and is given by:

\[ C_{ij} = (-1)^{i+j}|M_{ij}| \nonumber \]

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.

Question

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

This page titled 18.2: Algorithm to calculate the determinant was last modified on Sat, 17 Sep 2022 15:14:32 GMT and is shared under a CC BY-NC 4.0 license and was authored, remixed, and/or curated by Dirk Colbry via source content that was edited to the style and standards of the LibreTexts platform.

Contents

Text

Do This

Question

Question