18.2: Algoritmo para calcular el determinante

Última actualización
Guardar como PDF

Page ID: 114948

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Considera el siguiente algoritmo recursivo (algoritmo que se llama a sí mismo) para determinar el determinado de una\(n \times n\) matriz\(A\) (denotada\(\left| A \right|\)), que es la suma de los productos de los elementos de cualquier fila o columna. 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 \]

donde\(C_{ij}\) es el cofactor de\(a_{ij}\) y viene dado por:

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

y\(M_{ij}\) es la matriz que queda después de eliminar fila\(i\) y columna\(j\) de\(A\).

Aquí hay algún código que intenta implementar este algoritmo.

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

El siguiente código genera una\(n \times n\) matriz con valores aleatorios de 0 a 10.

Ejecute el código varias veces para obtener diferentes 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)

Hacer esto

Utilice la matriz generada aleatoriamente (\(A\)) para probar la función mydet anterior y comparar su resultado con la función numpy.linalg.det.

# Put your test code here

Pregunta

¿Las respuestas a mydet y numpuy.linalg.det son exactamente las mismas cada vez que generas una matriz aleatoria diferente? Si no, explica por qué.

Pregunta

En la línea 26 del código anterior, se puede ver que el algoritmo se llama a sí mismo. Explique por qué esto no se ejecuta para siempre.