Question

Como implementar um programa para calcular o determinante de uma matriz usando cofatores?

Answer 1

Em python:

import math
import numpy as np

def determinant(A):
    n=np.shape(A)[0]
    if(n==2):
        det=A[0,0]*A[1,1]-A[0,1]*A[1,0]
    else:    
        det=0
        for i in range(n):
            # Expansion by first line
            newMatrix=A[1:,:]
            newMatrix=np.delete(newMatrix,i,axis=1)
            det=det+math.pow(-1,1+i+1)*A[0,i]*(determinant(newMatrix))
    return det

if __name__ == '__main__':

    print "Matrix 1"
    A=((1, 2, 3),(4, 5 , 6),(7,8,9))
    print "Numpy: ", np.linalg.det(A)
    A=np.array(A)
    print "Ours: ",determinant(A)

    print "Matrix 2"
    A=((1, 2, 3),(4, 5 , 6),(7,8,13))
    print "Numpy: ",np.linalg.det(A)
    A=np.array(A)
    print "Ours: ",determinant(A)

    print "Matrix 3"
    A=((2, -2, 0, 3),(-5, 2 , 2, 1),(1,-1,0,-3),(2, 0, 0, -1))
    print "Numpy: ",np.linalg.det(A)    
    A=np.array(A)
    print "Ours: ",determinant(A)

Comments

Nesse caso a complexidade computacional seria da ordem de O(n!)? Para cada elemento da primeira linha, calcula-se n determinantes de uma ordem inferior, e além disso multiplica-se cada elemento da primeira linha por um valor e soma todos esses valores, tendo (n-1) somas. Logo, a relação de recorrência ficaria T(n) = nT(n-1) + 2n -1. Pode-se mostrar por indução que essa complexidade é da ordem de n!. Isto está certo para essa implementação? Ou o fato de você gerar os slices de uma nova matriz aumenta a complexidade?

Answer 2

Acho que nessa modificação o python nunca precisaria de fato criar uma nova variável sendo um slice da matriz original (não tenho certeza se isso resolveria o problema que eu levantei no comentário).

import math
import numpy as np

def determinant(A):
    n=np.shape(A)[0] #linhas 
    if(n==2):
        det=A[0,0]*A[1,1]-A[0,1]*A[1,0]
    else:    
        det=0
        for i in range(n):
            # Expansion by first line
            #newMatrix=A[1:,:]
            #newMatrix=np.delete(newMatrix,i,axis=1) # Deleta a i-ésima coluna
            det=det+math.pow(-1,1+i+1)*A[0,i]*(determinant(np.delete(A[1:,:],i,axis=1)))
    return det