El determinante calculado de forma recursiva

Cargamos las librerías necesarias para trabajar con matrices

In [9]:

from sympy import Matrix, randMatrix, pprint

def det(M):
    """Calcula el determinante de la matriz M (el método está optimizado calculando la RREF primero)"""
    return M.det()

def matriz(n):
    """Devuelve una matrix n x n con entradas enteras entre -9 y 9"""
    return randMatrix(n,n,-9,9)

Ahora creamos una matriz aleatoria $n \times n$ con entradas enteras entre -9 y 9 para hacer nuestro test. Por defecto n=9 pero puede cambiarse en la celda.

In [10]:

n = 100
M = matriz(n)

Vamos a probar el tiempo que se tarda al calcular el determinante con el método de Gauss (optimizado, pues primero calcula la RREF(M)). El prefijo %time simplemente le dice a Python que cronometre el tiempo de ejecución del comando.

In [11]:

%time det(M)

CPU times: user 20.1 s, sys: 267 ms, total: 20.4 s
Wall time: 21.6 s

45650067574632456043479615757829323944863328421226863846762682117722844949426416669881370420826371311602178594024867559213308254563509964254157909027092

Ahora vamos a calcular el mismo determinante por la definición recurrente, para ello cargamos el programa det_clasico y una subrutina para calcular la submatriz $M_{ij}$ de la matriz $M$ .

In [11]:

def submatriz(M, i, j):
    """Calcula la submatriz M_ij de la matriz M resultado de eliminar la fila i y la columna j"""
    idx, idy = list(range(M.rows)), list(range(M.cols))
    idx.remove(i)
    idy.remove(j)
    return M[idx,idy]

def det_clasico(M, fila = 0, nrecur = [0]):
    """Calcula el determinante desarrollándolo por la primera fila (por defecto)"""
    
    # Esta parte es para ver que el programa no se ha quedado colgado cuando tarda mucho.
    nrecur[0] += 1
    if nrecur[0] % 100000 == 0:
        print("Realizando la llamada a det_clasico número:", nrecur[0])
    
    # Aquí empieza el programa propiamente dicho, si no es 1x1 desarrollamos y si lo es el determinante es ese valor.
    if M.rows != 1:
        result = 0
        for col in range(M.cols):
            if M[fila,col] != 0:  # Si M[fila,col]=0 evitamos recursiones innecesarias
                result += M[fila,col] * (-1)**(fila + col) * det_clasico(submatriz(M,fila,col), fila, nrecur)
    else:
        result = M[0,0]
    return result

In [21]:

%time det_clasico(M)

Realizando la llamada a det_clasico número: 3900000
Realizando la llamada a det_clasico número: 4000000
Realizando la llamada a det_clasico número: 4100000
Realizando la llamada a det_clasico número: 4200000
Realizando la llamada a det_clasico número: 4300000
Realizando la llamada a det_clasico número: 4400000
Realizando la llamada a det_clasico número: 4500000
Realizando la llamada a det_clasico número: 4600000
Realizando la llamada a det_clasico número: 4700000
Realizando la llamada a det_clasico número: 4800000
Realizando la llamada a det_clasico número: 4900000
Realizando la llamada a det_clasico número: 5000000
Realizando la llamada a det_clasico número: 5100000
Realizando la llamada a det_clasico número: 5200000
Realizando la llamada a det_clasico número: 5300000
Realizando la llamada a det_clasico número: 5400000
Realizando la llamada a det_clasico número: 5500000
Realizando la llamada a det_clasico número: 5600000
Realizando la llamada a det_clasico número: 5700000
Realizando la llamada a det_clasico número: 5800000
Realizando la llamada a det_clasico número: 5900000
Realizando la llamada a det_clasico número: 6000000
Realizando la llamada a det_clasico número: 6100000
Realizando la llamada a det_clasico número: 6200000
Realizando la llamada a det_clasico número: 6300000
Realizando la llamada a det_clasico número: 6400000
Realizando la llamada a det_clasico número: 6500000
Realizando la llamada a det_clasico número: 6600000
Realizando la llamada a det_clasico número: 6700000
Realizando la llamada a det_clasico número: 6800000
Realizando la llamada a det_clasico número: 6900000
Realizando la llamada a det_clasico número: 7000000
Realizando la llamada a det_clasico número: 7100000
Realizando la llamada a det_clasico número: 7200000
Realizando la llamada a det_clasico número: 7300000
Realizando la llamada a det_clasico número: 7400000
Realizando la llamada a det_clasico número: 7500000
Realizando la llamada a det_clasico número: 7600000
Realizando la llamada a det_clasico número: 7700000
Realizando la llamada a det_clasico número: 7800000
Realizando la llamada a det_clasico número: 7900000
Realizando la llamada a det_clasico número: 8000000
Realizando la llamada a det_clasico número: 8100000
Realizando la llamada a det_clasico número: 8200000
Realizando la llamada a det_clasico número: 8300000
Realizando la llamada a det_clasico número: 8400000
Realizando la llamada a det_clasico número: 8500000
Realizando la llamada a det_clasico número: 8600000
Realizando la llamada a det_clasico número: 8700000
Realizando la llamada a det_clasico número: 8800000
Realizando la llamada a det_clasico número: 8900000
Realizando la llamada a det_clasico número: 9000000
Realizando la llamada a det_clasico número: 9100000
Realizando la llamada a det_clasico número: 9200000
Realizando la llamada a det_clasico número: 9300000
Realizando la llamada a det_clasico número: 9400000
Realizando la llamada a det_clasico número: 9500000
Realizando la llamada a det_clasico número: 9600000
Realizando la llamada a det_clasico número: 9700000
Realizando la llamada a det_clasico número: 9800000
Realizando la llamada a det_clasico número: 9900000
Realizando la llamada a det_clasico número: 10000000
Realizando la llamada a det_clasico número: 10100000
Realizando la llamada a det_clasico número: 10200000
Realizando la llamada a det_clasico número: 10300000
Realizando la llamada a det_clasico número: 10400000
Realizando la llamada a det_clasico número: 10500000
Realizando la llamada a det_clasico número: 10600000
Realizando la llamada a det_clasico número: 10700000
Realizando la llamada a det_clasico número: 10800000
Realizando la llamada a det_clasico número: 10900000
Realizando la llamada a det_clasico número: 11000000
Realizando la llamada a det_clasico número: 11100000
Realizando la llamada a det_clasico número: 11200000
Realizando la llamada a det_clasico número: 11300000
Realizando la llamada a det_clasico número: 11400000
Realizando la llamada a det_clasico número: 11500000
Realizando la llamada a det_clasico número: 11600000
Realizando la llamada a det_clasico número: 11700000
Realizando la llamada a det_clasico número: 11800000
Realizando la llamada a det_clasico número: 11900000
Realizando la llamada a det_clasico número: 12000000
Realizando la llamada a det_clasico número: 12100000
Realizando la llamada a det_clasico número: 12200000
Realizando la llamada a det_clasico número: 12300000
Realizando la llamada a det_clasico número: 12400000
Realizando la llamada a det_clasico número: 12500000
Realizando la llamada a det_clasico número: 12600000
Realizando la llamada a det_clasico número: 12700000
Realizando la llamada a det_clasico número: 12800000
Realizando la llamada a det_clasico número: 12900000
Realizando la llamada a det_clasico número: 13000000
Realizando la llamada a det_clasico número: 13100000
Realizando la llamada a det_clasico número: 13200000
Realizando la llamada a det_clasico número: 13300000
Realizando la llamada a det_clasico número: 13400000
Realizando la llamada a det_clasico número: 13500000
Realizando la llamada a det_clasico número: 13600000
Realizando la llamada a det_clasico número: 13700000
Realizando la llamada a det_clasico número: 13800000
Realizando la llamada a det_clasico número: 13900000
Realizando la llamada a det_clasico número: 14000000
Realizando la llamada a det_clasico número: 14100000
Realizando la llamada a det_clasico número: 14200000
Realizando la llamada a det_clasico número: 14300000
Realizando la llamada a det_clasico número: 14400000
Realizando la llamada a det_clasico número: 14500000
Realizando la llamada a det_clasico número: 14600000
Realizando la llamada a det_clasico número: 14700000
Realizando la llamada a det_clasico número: 14800000
Realizando la llamada a det_clasico número: 14900000
Realizando la llamada a det_clasico número: 15000000
Realizando la llamada a det_clasico número: 15100000
Realizando la llamada a det_clasico número: 15200000
Realizando la llamada a det_clasico número: 15300000
Realizando la llamada a det_clasico número: 15400000
Realizando la llamada a det_clasico número: 15500000
Realizando la llamada a det_clasico número: 15600000
Realizando la llamada a det_clasico número: 15700000
Realizando la llamada a det_clasico número: 15800000
Realizando la llamada a det_clasico número: 15900000
Realizando la llamada a det_clasico número: 16000000
Realizando la llamada a det_clasico número: 16100000
Realizando la llamada a det_clasico número: 16200000
Realizando la llamada a det_clasico número: 16300000
Realizando la llamada a det_clasico número: 16400000
Realizando la llamada a det_clasico número: 16500000
Realizando la llamada a det_clasico número: 16600000
Realizando la llamada a det_clasico número: 16700000
Realizando la llamada a det_clasico número: 16800000
Realizando la llamada a det_clasico número: 16900000
Realizando la llamada a det_clasico número: 17000000
Realizando la llamada a det_clasico número: 17100000
Realizando la llamada a det_clasico número: 17200000
Realizando la llamada a det_clasico número: 17300000
Realizando la llamada a det_clasico número: 17400000
Realizando la llamada a det_clasico número: 17500000
Realizando la llamada a det_clasico número: 17600000
Realizando la llamada a det_clasico número: 17700000
Realizando la llamada a det_clasico número: 17800000
Realizando la llamada a det_clasico número: 17900000
Realizando la llamada a det_clasico número: 18000000
Realizando la llamada a det_clasico número: 18100000
Realizando la llamada a det_clasico número: 18200000
Realizando la llamada a det_clasico número: 18300000
Realizando la llamada a det_clasico número: 18400000
Realizando la llamada a det_clasico número: 18500000
Realizando la llamada a det_clasico número: 18600000
Realizando la llamada a det_clasico número: 18700000
Realizando la llamada a det_clasico número: 18800000
Realizando la llamada a det_clasico número: 18900000
Realizando la llamada a det_clasico número: 19000000
Realizando la llamada a det_clasico número: 19100000
Realizando la llamada a det_clasico número: 19200000
Realizando la llamada a det_clasico número: 19300000
Realizando la llamada a det_clasico número: 19400000
Realizando la llamada a det_clasico número: 19500000
Realizando la llamada a det_clasico número: 19600000
Realizando la llamada a det_clasico número: 19700000
Realizando la llamada a det_clasico número: 19800000
Realizando la llamada a det_clasico número: 19900000
Realizando la llamada a det_clasico número: 20000000
Realizando la llamada a det_clasico número: 20100000
Realizando la llamada a det_clasico número: 20200000
Realizando la llamada a det_clasico número: 20300000
Realizando la llamada a det_clasico número: 20400000
Realizando la llamada a det_clasico número: 20500000
Realizando la llamada a det_clasico número: 20600000
Realizando la llamada a det_clasico número: 20700000
Realizando la llamada a det_clasico número: 20800000
Realizando la llamada a det_clasico número: 20900000
Realizando la llamada a det_clasico número: 21000000
Realizando la llamada a det_clasico número: 21100000
Realizando la llamada a det_clasico número: 21200000
Realizando la llamada a det_clasico número: 21300000
Realizando la llamada a det_clasico número: 21400000
Realizando la llamada a det_clasico número: 21500000
Realizando la llamada a det_clasico número: 21600000
Realizando la llamada a det_clasico número: 21700000
Realizando la llamada a det_clasico número: 21800000
Realizando la llamada a det_clasico número: 21900000
Realizando la llamada a det_clasico número: 22000000
Realizando la llamada a det_clasico número: 22100000
Realizando la llamada a det_clasico número: 22200000
Realizando la llamada a det_clasico número: 22300000
Realizando la llamada a det_clasico número: 22400000
Realizando la llamada a det_clasico número: 22500000
Realizando la llamada a det_clasico número: 22600000
Realizando la llamada a det_clasico número: 22700000
Realizando la llamada a det_clasico número: 22800000
Realizando la llamada a det_clasico número: 22900000
Realizando la llamada a det_clasico número: 23000000
Realizando la llamada a det_clasico número: 23100000
Realizando la llamada a det_clasico número: 23200000
Realizando la llamada a det_clasico número: 23300000
Realizando la llamada a det_clasico número: 23400000
Realizando la llamada a det_clasico número: 23500000
Realizando la llamada a det_clasico número: 23600000
Realizando la llamada a det_clasico número: 23700000
Realizando la llamada a det_clasico número: 23800000
Realizando la llamada a det_clasico número: 23900000
Realizando la llamada a det_clasico número: 24000000
Realizando la llamada a det_clasico número: 24100000
Realizando la llamada a det_clasico número: 24200000
Realizando la llamada a det_clasico número: 24300000
Realizando la llamada a det_clasico número: 24400000
Realizando la llamada a det_clasico número: 24500000
Realizando la llamada a det_clasico número: 24600000
Realizando la llamada a det_clasico número: 24700000
Realizando la llamada a det_clasico número: 24800000
Realizando la llamada a det_clasico número: 24900000
Realizando la llamada a det_clasico número: 25000000
Realizando la llamada a det_clasico número: 25100000
Realizando la llamada a det_clasico número: 25200000
Realizando la llamada a det_clasico número: 25300000
Realizando la llamada a det_clasico número: 25400000
Realizando la llamada a det_clasico número: 25500000
Realizando la llamada a det_clasico número: 25600000
Realizando la llamada a det_clasico número: 25700000
Realizando la llamada a det_clasico número: 25800000
Realizando la llamada a det_clasico número: 25900000
Realizando la llamada a det_clasico número: 26000000
Realizando la llamada a det_clasico número: 26100000
Realizando la llamada a det_clasico número: 26200000
Realizando la llamada a det_clasico número: 26300000
Realizando la llamada a det_clasico número: 26400000
Realizando la llamada a det_clasico número: 26500000
Realizando la llamada a det_clasico número: 26600000
Realizando la llamada a det_clasico número: 26700000
Realizando la llamada a det_clasico número: 26800000
Realizando la llamada a det_clasico número: 26900000
Realizando la llamada a det_clasico número: 27000000
Realizando la llamada a det_clasico número: 27100000
Realizando la llamada a det_clasico número: 27200000
Realizando la llamada a det_clasico número: 27300000
Realizando la llamada a det_clasico número: 27400000
Realizando la llamada a det_clasico número: 27500000
Realizando la llamada a det_clasico número: 27600000
Realizando la llamada a det_clasico número: 27700000
Realizando la llamada a det_clasico número: 27800000
Realizando la llamada a det_clasico número: 27900000
Realizando la llamada a det_clasico número: 28000000
Realizando la llamada a det_clasico número: 28100000
Realizando la llamada a det_clasico número: 28200000
Realizando la llamada a det_clasico número: 28300000
Realizando la llamada a det_clasico número: 28400000
Realizando la llamada a det_clasico número: 28500000
Realizando la llamada a det_clasico número: 28600000
Realizando la llamada a det_clasico número: 28700000
Realizando la llamada a det_clasico número: 28800000
Realizando la llamada a det_clasico número: 28900000
Realizando la llamada a det_clasico número: 29000000
Realizando la llamada a det_clasico número: 29100000
Realizando la llamada a det_clasico número: 29200000
Realizando la llamada a det_clasico número: 29300000
Realizando la llamada a det_clasico número: 29400000
Realizando la llamada a det_clasico número: 29500000
Realizando la llamada a det_clasico número: 29600000
Realizando la llamada a det_clasico número: 29700000
Realizando la llamada a det_clasico número: 29800000
Realizando la llamada a det_clasico número: 29900000
Realizando la llamada a det_clasico número: 30000000
Realizando la llamada a det_clasico número: 30100000
Realizando la llamada a det_clasico número: 30200000
Realizando la llamada a det_clasico número: 30300000
Realizando la llamada a det_clasico número: 30400000
Realizando la llamada a det_clasico número: 30500000
Realizando la llamada a det_clasico número: 30600000
Realizando la llamada a det_clasico número: 30700000
Realizando la llamada a det_clasico número: 30800000
Realizando la llamada a det_clasico número: 30900000
Realizando la llamada a det_clasico número: 31000000
Realizando la llamada a det_clasico número: 31100000
Realizando la llamada a det_clasico número: 31200000
Realizando la llamada a det_clasico número: 31300000
Realizando la llamada a det_clasico número: 31400000
Realizando la llamada a det_clasico número: 31500000
Realizando la llamada a det_clasico número: 31600000
Realizando la llamada a det_clasico número: 31700000
Realizando la llamada a det_clasico número: 31800000
Realizando la llamada a det_clasico número: 31900000
Realizando la llamada a det_clasico número: 32000000
Realizando la llamada a det_clasico número: 32100000
Realizando la llamada a det_clasico número: 32200000
Realizando la llamada a det_clasico número: 32300000
Realizando la llamada a det_clasico número: 32400000
Realizando la llamada a det_clasico número: 32500000
Realizando la llamada a det_clasico número: 32600000
Realizando la llamada a det_clasico número: 32700000
Realizando la llamada a det_clasico número: 32800000
Realizando la llamada a det_clasico número: 32900000
Realizando la llamada a det_clasico número: 33000000
Realizando la llamada a det_clasico número: 33100000
Realizando la llamada a det_clasico número: 33200000
Realizando la llamada a det_clasico número: 33300000
Realizando la llamada a det_clasico número: 33400000
Realizando la llamada a det_clasico número: 33500000
Realizando la llamada a det_clasico número: 33600000
Realizando la llamada a det_clasico número: 33700000
Realizando la llamada a det_clasico número: 33800000
Realizando la llamada a det_clasico número: 33900000
Realizando la llamada a det_clasico número: 34000000
Realizando la llamada a det_clasico número: 34100000
Realizando la llamada a det_clasico número: 34200000
Realizando la llamada a det_clasico número: 34300000
Realizando la llamada a det_clasico número: 34400000
Realizando la llamada a det_clasico número: 34500000
Realizando la llamada a det_clasico número: 34600000
Realizando la llamada a det_clasico número: 34700000
CPU times: user 25min 55s, sys: 3.89 s, total: 25min 59s
Wall time: 27min 22s

-128325749783

Ahora vuelve a ejecutar esta hoja con $n=9$ que tardará entre medio minuto y dos minutos, y luego ¡con calma! usa por ejemplo $n=12$ y espera... (no hace falta ejecutar todas las celdas, ya se han cargado las funciones pero ante la duda ejecuta todas).