Determinante de matrices grandes: tiene que haber una forma más rápida

Question

ADVERTENCIA este es un informe muy largo y es probable que provoque aburrimiento. ¡¡Estén advertidos!!

He oído hablar del determinante de matrices pequeñas, como:

$$\det \begin{pmatrix} a&b\\ c&d\\ \end{pmatrix} = ad-bc $$

Un ejemplo:

$$\det \begin{pmatrix} 57&48\\ 79&102\\ \end{pmatrix} = 57\times 102-48\times 79 =5814-3792 =2022 $$

Este es un ejemplo bastante pesado que encontré en uno de mis libros sobre vectores y matrices. Y hay ejemplos mucho más complejos. por ejemplo, para encontrar el determinante de una matriz de orden 3, haces esto:

$$\begin{align} &\det \begin{pmatrix} a&b&c\\ d&e&f\\ g&h&i\\ \end{pmatrix}\\ &=a\times \det \begin{bmatrix} e&f\\ h&i\\ \end{bmatrix}\\ &-b\times \det \begin{bmatrix} d&f\\ g&i\\ \end{bmatrix}\\ &+c\times \det \begin{bmatrix} d&e\\ g&h\\ \end{bmatrix} \end{align}$$

Esta secuencia parece un poco simple, pero en realidad explota (se hace cada vez más grande) después de un tiempo. por ejemplo, con un $5\times 5$ matrix alguien me pidió que modelara, así fue mi "tiempo de diversión":

$$ \begin{align} &\det \begin{Bmatrix} a&b&c&d&e\\ f&g&h&i&j\\ k&l&m&n&o\\ p&q&r&s&t\\ u&v&w&x&y\\ \end{Bmatrix}\\ &=a\times \det \begin{Bmatrix} g&h&i&j\\ l&m&n&o\\ q&r&s&t\\ v&w&x&y\\ \end{Bmatrix} -b\times \det \begin{Bmatrix} f&h&i&j\\ k&m&n&o\\ p&r&s&t\\ u&w&x&y\\ \end{Bmatrix} +c\times \det \begin{Bmatrix} f&g&i&j\\ k&l&n&o\\ p&q&s&t\\ u&v&x&y\\ \end{Bmatrix}\\ &-d\times \det \begin{Bmatrix} f&g&h&j\\ k&l&m&o\\ p&q&r&t\\ u&v&w&y\\ \end{Bmatrix} +e\times \det \begin{Bmatrix} f&g&h&i\\ k&l&m&n\\ p&q&r&s\\ u&v&w&x\\ \end{Bmatrix} \end{align} $$

Esto es un fajo complejo de cálculos para que yo lo haga completamente. así que lo dividiré en los 5 componentes: A, B, C, D, y E, respectivamente.

$$ A=a\times \det \begin{Bmatrix} g&h&i&j\\ l&m&n&o\\ q&r&s&t\\ v&w&x&y\\ \end{Bmatrix} \\ =a\left( g\times \det \begin{Bmatrix} m&n&o\\ r&s&t\\ w&x&y\\ \end{Bmatrix} -h\times \det \begin{Bmatrix} l&n&o\\ q&s&t\\ v&x&y\\ \end{Bmatrix} +i\times \det \begin{Bmatrix} l&m&o\\ q&r&t\\ v&w&y\\ \end{Bmatrix} -j\times \det \begin{Bmatrix} l&m&n\\ q&r&s\\ v&w&x\\ \end{Bmatrix} \right)\\ =a\left( g\left( m\times \det \begin{Bmatrix} s&t\\ x&y\\ \end{Bmatrix} -n\times \det \begin{Bmatrix} r&t\\ w&y\\ \end{Bmatrix} +o\times \det \begin{Bmatrix} r&s\\ w&x\\ \end{Bmatrix} \right)\\ -h\left( l\times \det \begin{Bmatrix} s&t\\ x&y\\ \end{Bmatrix} -n\times \det \begin{Bmatrix} q&t\\ v&y\\ \end{Bmatrix} +o\times \det \begin{Bmatrix} q&s\\ v&x\\ \end{Bmatrix} \right)\\ +i\left( l\times \det \begin{Bmatrix} r&t\\ w&y\\ \end{Bmatrix} -m\times \det \begin{Bmatrix} q&t\\ v&y\\ \end{Bmatrix} +o\times \det \begin{Bmatrix} q&r\\ v&w\\ \end{Bmatrix} \right) -j\left( l\times \det \begin{Bmatrix} r&s\\ w&x\\ \end{Bmatrix} -m\times \det \begin{Bmatrix} q&s\\ v&x\\ \end{Bmatrix} +n\times \det \begin{Bmatrix} q&r\\ v&w\\ \end{Bmatrix} \right) \right)\\ =a\left( g\left(m(sy-xt)-n(ry-wt)+o(rx-ws)\right)\\ -h\left(l(sy-xt)-n(qy-vt)+o(qx-vs)\right)\\ +i\left(l(ry-wt)-m(qy-vt)+o(qw-vr)\right)\\ -j\left(l(rx-ws)-m(qx-vs)+n(qw-vr)\right) \right) $$

(Si quiere ver este monstruo en forma de código, vaya a esta página pero yo no $100$ % seguro de que funcionará).

$$ B= -b\times \det \begin{Bmatrix} f&h&i&j\\ k&m&n&o\\ p&r&s&t\\ u&w&x&y\\ \end{Bmatrix}\\ -b\left( f\times \det \begin{Bmatrix} m&n&o\\ r&s&t\\ w&x&y\\ \end{Bmatrix} -h\times \det \begin{Bmatrix} k&n&o\\ p&s&t\\ u&x&y\\ \end{Bmatrix} +i\times \det \begin{Bmatrix} k&m&o\\ p&r&t\\ u&w&y\\ \end{Bmatrix} -j\times \det \begin{Bmatrix} k&m&n\\ p&r&s\\ u&w&x\\ \end{Bmatrix} \right)\\ =-b\left( f\left( m\times \det \begin{Bmatrix} s&t\\ x&y\\ \end{Bmatrix} -n\times \det \begin{Bmatrix} r&t\\ w&y\\ \end{Bmatrix} +o\times \det \begin{Bmatrix} r&s\\ w&x\\ \end{Bmatrix} \right)\\ -h\left( k\times \det \begin{Bmatrix} s&t\\ x&y\\ \end{Bmatrix} -n\times \det \begin{Bmatrix} p&t\\ u&y\\ \end{Bmatrix} +o\times \det \begin{Bmatrix} p&s\\ u&x\\ \end{Bmatrix} \right)\\ +i\left( k\times \det \begin{Bmatrix} r&t\\ w&y\\ \end{Bmatrix} -m\times \det \begin{Bmatrix} p&t\\ u&y\\ \end{Bmatrix} +o\times \det \begin{Bmatrix} p&r\\ u&w\\ \end{Bmatrix} \right) -j\left( k\times \det \begin{Bmatrix} r&s\\ w&x\\ \end{Bmatrix} -m\times \det \begin{Bmatrix} p&s\\ u&x\\ \end{Bmatrix} +n\times \det \begin{Bmatrix} p&r\\ u&w\\ \end{Bmatrix} \right) \right)\\ =-b\left( f\left(m(sy-xt)-n(ry-wt)+o(rx-ws)\right)\\ -h\left(k(sy-xt)-n(py-ut)+o(px-us)\right)\\ +i\left(k(ry-wt)-m(py-ut)+o(pw-ur)\right)\\ -j\left(k(rx-ws)-m(px-us)+n(pw-ur)\right) \right) $$

y esta es la parte b! esta es una cantidad extenuante de código para que yo coloque. $\frac{3}{5}$ Así se hace...

$$ C=c\times \det \begin{Bmatrix} f&g&i&j\\ k&l&n&o\\ p&q&s&t\\ u&v&x&y\\ \end{Bmatrix}\\ =c\left( f\times \det \begin{Bmatrix} l&n&o\\ q&s&t\\ v&x&y\\ \end{Bmatrix} -g\times \det \begin{Bmatrix} k&n&o\\ p&s&t\\ u&x&y\\ \end{Bmatrix} +i\times \det \begin{Bmatrix} k&l&o\\ p&q&t\\ u&v&y\\ \end{Bmatrix} -j\times \det \begin{Bmatrix} k&l&n\\ p&q&s\\ u&v&x\\ \end{Bmatrix} \right)\\ =c\left( f\left( l\times \det \begin{Bmatrix} s&t\\ x&y\\ \end{Bmatrix} -n\times \det \begin{Bmatrix} q&t\\ v&y\\ \end{Bmatrix} +o\times \det \begin{Bmatrix} q&s\\ v&x\\ \end{Bmatrix} \right)\\ -g\left( k\times \det \begin{Bmatrix} s&t\\ x&y\\ \end{Bmatrix} -n\times \det \begin{Bmatrix} p&t\\ u&y\\ \end{Bmatrix} +o\times \det \begin{Bmatrix} p&s\\ u&x\\ \end{Bmatrix} \right)\\ +i\left( k\times \det \begin{Bmatrix} q&t\\ v&y\\ \end{Bmatrix} -l\times \det \begin{Bmatrix} p&t\\ u&y\\ \end{Bmatrix} +o\times \det \begin{Bmatrix} p&q\\ u&v\\ \end{Bmatrix} \right)\\ -j\left( k\times \det \begin{Bmatrix} q&s\\ v&x\\ \end{Bmatrix} -l\times \det \begin{Bmatrix} p&s\\ u&x\\ \end{Bmatrix} +n\times \det \begin{Bmatrix} p&q\\ u&v\\ \end{Bmatrix} \right) \right)\\ =c\left( f\left(l(sy-xt)-n(qy-vt)+o(qx-vs)\right)\\ -g\left(k(sy-xt)-n(py-ut)+o(px-us)\right)\\ +i\left(k(qy-vt)-l(py-ut)+o(pv-uq)\right)\\ -j\left(k(qx-vs)-l(px-us)+n(pv-uq)\right) \right) $$

Esa es la cesárea. Ahora para llegar a la cesárea...

$$ D=-d\times \det \begin{Bmatrix} f&g&h&j\\ k&l&m&o\\ p&q&r&t\\ u&v&w&y\\ \end{Bmatrix}\\ =-d\left( f\times \det \begin{Bmatrix} l&m&o\\ q&r&t\\ v&w&y\\ \end{Bmatrix} -g\times \det \begin{Bmatrix} k&m&o\\ p&r&t\\ u&w&y\\ \end{Bmatrix} +h\times \det \begin{Bmatrix} k&l&o\\ p&q&t\\ u&v&y\\ \end{Bmatrix} -j\times \det \begin{Bmatrix} k&l&m\\ p&q&r\\ u&v&w\\ \end{Bmatrix} \right)\\ =-d\left( f\left( l\times \det \begin{Bmatrix} r&t\\ w&y\\ \end{Bmatrix} -m\times \det \begin{Bmatrix} q&t\\ v&y\\ \end{Bmatrix} +o\times \det \begin{Bmatrix} q&r\\ v&w\\ \end{Bmatrix} \right)\\ -g\left( k\times \det \begin{Bmatrix} r&t\\ w&y\\ \end{Bmatrix} -m\times \det \begin{Bmatrix} p&t\\ u&y\\ \end{Bmatrix} +o\times \det \begin{Bmatrix} p&r\\ u&w\\ \end{Bmatrix} \right)\\ +h\left( k\times \det \begin{Bmatrix} q&t\\ v&y\\ \end{Bmatrix} -l\times \det \begin{Bmatrix} p&t\\ u&y\\ \end{Bmatrix} +o\times \det \begin{Bmatrix} p&q\\ u&v\\ \end{Bmatrix} \right)\\ -j\left( k\times \det \begin{Bmatrix} q&r\\ v&w\\ \end{Bmatrix} -l\times \det \begin{Bmatrix} p&r\\ u&w\\ \end{Bmatrix} +m\times \det \begin{Bmatrix} p&q\\ u&v\\ \end{Bmatrix} \right) \right)\\ =-d\left( f\left(l(ry-wt)-m(qy-vt)+o(qw-vr)\right)\\ -g\left(k(ry-wt)-m(py-ut)+o(pw-ur)\right)\\ +h\left(k(qy-vt)-l(py-ut)+o(pv-uq)\right)\\ -j\left(k(qw-vr)-l(pw-ur)+m(pv-uq)\right) \right) $$

¿Ya te has aburrido? Yo sí. Por suerte, me queda una sección más...

$$ E=e\times \det \begin{Bmatrix} f&g&h&i\\ k&l&m&n\\ p&q&r&s\\ u&v&w&x\\ \end{Bmatrix} =e\left( f\times \det \begin{Bmatrix} l&m&n\\ q&r&s\\ v&w&x\\ \end{Bmatrix} -g\times \det \begin{Bmatrix} k&m&n\\ p&r&s\\ u&w&x\\ \end{Bmatrix} +h\times \det \begin{Bmatrix} k&l&n\\ p&q&s\\ u&v&x\\ \end{Bmatrix} -i\times \det \begin{Bmatrix} k&l&m\\ p&q&r\\ u&v&w\\ \end{Bmatrix} \right)\\ =e\left( f\left( l\times \det \begin{Bmatrix} r&s\\ w&x\\ \end{Bmatrix} -m\times \det \begin{Bmatrix} q&s\\ v&x\\ \end{Bmatrix} +n\times \det \begin{Bmatrix} q&r\\ v&w\\ \end{Bmatrix} \right)\\ -g\left( k\times \det \begin{Bmatrix} r&s\\ w&x\\ \end{Bmatrix} -m\times \det \begin{Bmatrix} p&s\\ u&x\\ \end{Bmatrix} +n\times \det \begin{Bmatrix} p&r\\ u&w\\ \end{Bmatrix} \right)\\ +h\left( k\times \det \begin{Bmatrix} q&s\\ v&x\\ \end{Bmatrix} -l\times \det \begin{Bmatrix} p&s\\ u&x\\ \end{Bmatrix} +n\times \det \begin{Bmatrix} p&q\\ u&v\\ \end{Bmatrix} \right)\\ -i\left( k\times \det \begin{Bmatrix} q&r\\ v&w\\ \end{Bmatrix} -l\times \det \begin{Bmatrix} p&r\\ u&w\\ \end{Bmatrix} +m\times \det \begin{Bmatrix} p&q\\ u&v\\ \end{Bmatrix} \right) \right)\\ =e\left( f\left(l(rx-ws)-m(qx-vs)+n(qw-vr)\right)\\ -g\left(k(rx-ws)-m(px-us)+n(pw-ur)\right)\\ +h\left(k(qx-vs)-l(px-us)+n(pv-uq)\right)\\ -i\left(k(qw-vr)-l(pw-ur)+m(pv-uq)\right) \right) $$

ZZZZZZZZZZZZ... ¡GAH! Vale... recapitulando:

$$ \det \begin{Bmatrix} a&b&c&d&e\\ f&g&h&i&j\\ k&l&m&n&o\\ p&q&r&s&t\\ u&v&w&x&y\\ \end{Bmatrix}\\ =a\left( g\left(m(sy-xt)-n(ry-wt)+o(rx-ws)\right)\\ -h\left(l(sy-xt)-n(qy-vt)+o(qx-vs)\right)\\ +i\left(l(ry-wt)-m(qy-vt)+o(qw-vr)\right)\\ -j\left(l(rx-ws)-m(qx-vs)+n(qw-vr)\right) \right)\\ -b\left( f\left(m(sy-xt)-n(ry-wt)+o(rx-ws)\right)\\ -h\left(k(sy-xt)-n(py-ut)+o(px-us)\right)\\ +i\left(k(ry-wt)-m(py-ut)+o(pw-ur)\right)\\ -j\left(k(rx-ws)-m(px-us)+n(pw-ur)\right) \right)\\ +c\left( f\left(l(sy-xt)-n(qy-vt)+o(qx-vs)\right)\\ -g\left(k(sy-xt)-n(py-ut)+o(px-us)\right)\\ +i\left(k(qy-vt)-l(py-ut)+o(pv-uq)\right)\\ -j\left(k(qx-vs)-l(px-us)+n(pv-uq)\right) \right)\\ -d\left( f\left(l(ry-wt)-m(qy-vt)+o(qw-vr)\right)\\ -g\left(k(ry-wt)-m(py-ut)+o(pw-ur)\right)\\ +h\left(k(qy-vt)-l(py-ut)+o(pv-uq)\right)\\ -j\left(k(qw-vr)-l(pw-ur)+m(pv-uq)\right) \right)\\ +e\left( f\left(l(rx-ws)-m(qx-vs)+n(qw-vr)\right)\\ -g\left(k(rx-ws)-m(px-us)+n(pw-ur)\right)\\ +h\left(k(qx-vs)-l(px-us)+n(pv-uq)\right)\\ -i\left(k(qw-vr)-l(pw-ur)+m(pv-uq)\right) \right) $$

Ahora que ESO ha terminado ( ¡¡DEJA DE DESPLAZARTE!! ), debo mencionar que dejé a mi amigo con la boca abierta al enseñarle esto. AHORA quiere que resuelva una matriz de orden 10. ¡¡¡¡¡¡¡AURRRRRRRRUUUUUUUUUUUUGGGGGGGGGGHHHHHHHH!!!!!!! ¡¡¡¡NO TENGO EL TIEMPO!!!! Por lo tanto, me pregunto si hay una manera más rápida de calcular el determinante de una matriz ENORME. espero que la haya. Gracias de antemano.

EDITAR estaba conversando con mi amigo, explicándole la pérdida de tiempo que supone calcular una matriz de orden 10, y le convencí para que abandonara la idea de "hacerlo a mano" y, en su lugar, lo hiciera en el ordenador.

Answer 1

No, esta no es la forma en que cualquier persona (en su sano juicio) calcularía un determinante. Ni siquiera es la forma en que un ordenador calcularía un determinante. Requiere una suma sobre $n!$ términos, lo que rápidamente se vuelve inviable incluso para un ordenador, alrededor de $n = 15$ más o menos. Una forma elemental de calcular rápidamente un determinante es mediante la eliminación de Gauss.

Conocemos algunos datos sobre el determinante:

1. Añadir un múltiplo escalar de una fila a otra no cambia el determinante.
2. Intercambiar dos filas niega el determinante.
3. Escalar una fila por una constante multiplica el determinante por esa constante.

Así pues, tomemos ahora la matriz

$$ A = \begin{bmatrix}-4 & 3 &3 \\ 8 & 7 & 3 \\ 4 & 3 & 3\end{bmatrix} $$

Por el hecho (1) anterior, puedo añadir dos veces la fila superior a la fila del medio, y también la fila superior a la fila inferior, sin afectar al determinante. Entonces:

$$ \det A = \det \begin{bmatrix}-4 & 3 &3 \\ 0 & 13 & 9 \\ 0 & 6 & 6\end{bmatrix}$$

Ahora, puedo intercambiar las dos filas inferiores, y y escalar la fila con sólo $6$ con un coste de $-6$ :

$$ \det A = - \det \begin{bmatrix}-4 & 3 &3 \\ 0 & 6 & 6 \\ 0 & 13 & 9 \end{bmatrix} = - 6 \det \begin{bmatrix}-4 & 3 &3 \\ 0 & 1 & 1 \\ 0 & 13 & 9 \end{bmatrix}$$

Ahora puedo restar 13 lotes de la fila central a la fila inferior:

$$ \det A = - 6 \det \begin{bmatrix}-4 & 3 &3 \\ 0 & 1 & 1 \\ 0 & 13 & 9 \end{bmatrix} = - 6 \det \begin{bmatrix}-4 & 3 &3 \\ 0 & 1 & 1 \\ 0 & 0 & -4 \end{bmatrix}$$

Ahora la matriz es triangular superior, por lo que el determinante es sólo el producto de las entradas diagonales. Así que tenemos

$$ \det A = -6 (-4 \times 1 \times -4) = -96 $$

Así que ya lo tienes: calcular un determinante es tan fácil como encontrar la forma fila-echelón.

Answer 2

En general, los determinantes de matrices grandes no se calculan mediante expansión cofactorial, sino factorizando la matriz en factores cuyos determinantes sean fáciles de calcular.

Por ejemplo, puede factorizar un $n$ por $n$ matriz $A$ como

$A=P^{T}LU$

donde $P$ es una matriz de permutación, $L$ es triangular inferior, y $U$ es triangular superior. Este cálculo requiere $O(n^{3})$ tiempo para un $n$ por $n$ matriz $A$ .

Desde

$\det(A)=\det(P^{T})\det(L)\det(U)$

y los determinantes de $P^{T}$ , $L$ y $U$ son fáciles de calcular (el determinante de una matriz triangular inferior o superior es el producto de los elementos diagonales y se puede hacer fácilmente la expansión cofactorial en una matriz de permutación), se puede encontrar rápidamente el determinante de $A$ .

Si quiere hacer un experimento computacional, pruebe la función det() de MATLAB con matrices generadas aleatoriamente de tamaño $n$ por $n$ para $n=1000, 2000,\ldots, 10000$ y usa tic/toc para ver cuánto tarda el cálculo.

Answer 3

A pesar de las apariencias, este ejercicio no fue una pérdida de tiempo. Denotemos la matriz en cuestión por $A_{n \times n}$ . Dado que el determinante es un invariante rotacional, para cada $n\ge 2$ es posible expresarla de forma cerrada como función de todas las demás invariantes rotacionales, es decir, trazas de potencias de esta matriz $\left( Tr[A^p] \right)_{p=1}^n$ . La fórmula en cuestión dice: \begin{equation} \det(A) = \sum\limits_{m=1}^n \frac{(-1)^{m+n}}{m!} \cdot \sum\limits_{\begin{array}{r} p_1+p_2+\cdots+p_m=n \\ p_1\ge 1,\cdots,p_m\ge 1\end{array}} \prod\limits_{q=1}^m \frac{Tr[A^{p_q}]}{p_q} \fin{ecuación}

En este caso, la segunda suma de la parte derecha recorre todas las particiones de $n$ en enteros estrictamente positivos.

Véase Calcular una suma múltiple de enteros inversos. para la derivación.

Denote ${\mathcal S}_n := n! \det(A)$ y $a(p) := Tr[A^p]$ para $p\ge 1$ entonces tenemos: \begin{eqnarray} {\mathcal S}_2 &=& a(1)^2-a(2)\\ {\mathcal S}_3 &=& a(1)^3-3 a(2) a(1)+2 a(3)\\ {\mathcal S}_4 &=& a(1)^4-6 a(2) a(1)^2+8 a(3) a(1)+3 a(2)^2-6 a(4)\\ {\mathcal S}_5 &=& a(1)^5-10 a(2) a(1)^3+20 a(3) a(1)^2+15 a(2)^2 a(1)-30 a(4) a(1)-20 a(2) a(3)+24 a(5)\\ {\mathcal S}_6 &=& a(1)^6-15 a(2) a(1)^4+40 a(3) a(1)^3+45 a(2)^2 a(1)^2-90 a(4) a(1)^2-120 a(2) a(3) a(1)+144 a(5) a(1)-15 a(2)^3+40 a(3)^2+90 a(2) a(4)-120 a(6)\\ {\mathcal S}_7 &=& a(1)^7-21 a(2) a(1)^5+70 a(3) a(1)^4+105 a(2)^2 a(1)^3-210 a(4) a(1)^3-420 a(2) a(3) a(1)^2+504 a(5) a(1)^2-105 a(2)^3 a(1)+280 a(3)^2 a(1)+630 a(2) a(4) a(1)-840 a(6) a(1)+210 a(2)^2 a(3)-420 a(3) a(4)-504 a(2) a(5)+720 a(7) \end{eqnarray}

No es difícil ver que en cada una de esas fórmulas los coeficientes delante del producto de potencias de trazas tienen la propiedad de que suman cero y que sus valores absolutos suman $n!$ . En la siguiente tabla muestro el número de términos diferentes en la parte derecha $\nu(n)$ en función de la dimensión $n$ . Tenemos: \begin{array}{rr} n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\\ \nu(n) & 2 & 3 & 5 & 7 &11 & 15 & 22 & 30 & 42 & 56 & 77 & 101 & 135 & 176 & 231 \end{array}

Por lo tanto es totalmente falso que con este método tengamos que realizar $n!$ cálculos. De hecho, para $n=49$ sólo hay $173525$ términos para resumir (véase https://oeis.org/A000041/list ).

Answer 4

Si las entradas de tu matriz pertenecen a un campo, entonces puedes calcular el determinante fácilmente utilizando la descomposición LPU o la descomposición PLU. Estos algoritmos toman $O \left(n^3\right)$ tiempo, donde $n$ es el tamaño de la matriz.

Si las entradas de su matriz pertenecen a un anillo conmutativo arbitrario, entonces todavía hay $O \left(n^4\right)$ -para calcular el determinante. Véase Günter Rote, Algoritmos sin divisiones para el determinante y el pfaffiano: Enfoques algebraicos y combinatorios §2. (Si he entendido bien, la idea general de al menos uno de los algoritmos es sustituir la matriz $A \in R^{n\times n}$ mediante la matriz $1 - At$ sobre el anillo de series de potencias $R \left[\left[t\right]\right]$ a continuación, calcular el determinante de este último a través de la descomposición LU (que siempre existe en el anillo de series de potencias), y luego obtener $\det A$ como coeficiente de este polinomio. Por supuesto, las series de potencias per se son incalculables, pero aquí sólo hay que ocuparse de los primeros coeficientes).

Por supuesto, los algoritmos no pueden hacer magia. Las estimaciones del tiempo de ejecución de $O \left(n^3\right)$ y $O \left(n^4\right)$ supongamos que las operaciones fundamentales del anillo base ( $+$ , $\cdot$ , $-$ y la toma de inversas en el caso de un campo) requieren un tiempo constante y la sobrecarga de almacenar y copiar las entradas de la matriz es insignificante. Esta suposición está justificada si el anillo base es un campo finito o (hasta cierto punto) si el "anillo" base son los reales en coma flotante (aunque éstos no forman realmente un anillo, por lo que se podría acabar con resultados completamente erróneos debido a la inestabilidad numérica), pero no si el anillo base son los números enteros (porque los enteros son más difíciles de trabajar cuanto más grandes son), los números racionales o un anillo de polinomios. Cuando las entradas de su matriz son indeterminadas algebraicamente independientes, entonces no debe esperar nada demasiado rápido, al menos si quiere el resultado en forma expandida; después de todo, el resultado será simplemente la fórmula general para el determinante de una matriz de tipo $n \times n$ -matriz, que "contiene" una lista de todos los $n!$ permutaciones de $\left\{1,2,\ldots,n\right\}$ y es evidente que dicha lista requiere al menos $O \left(n!\right)$ ¡es hora de anotar! Podría haber algunos algoritmos más rápidos que resulten en versiones no expandidas (de forma similar al esquema de Horner para la evaluación de polinomios), pero yo no esperaría nada con un tiempo de ejecución polinómico a menos que permitas que el algoritmo devuelva una recursión en lugar de una suma explícita de productos-sumas-de-productos-de-etc .

Answer 5

Una famosa fórmula dice que el determinante es el producto de los valores propios. Si usted puede encontrar los valores propios más rápido que hacer una expansión de este tipo, entonces podría ser útil

$$\det({\bf A}) = \prod_{i=1}^N \lambda_i({\bf A})$$

Una forma de hallar numéricamente los valores propios es el método de la potencia. Obtendrás una buena estimación rápidamente. En términos de complejidad $O(n^2)$ para la multiplicación matriz-vector, $n$ valores propios a encontrar, que da $O(n^3)$

En definitiva, te saldrás con la tuya con un pequeño polinomio de complejidad comparado con la horrenda combinatoria $O(n!)$ complejidad de hacer lo que estás haciendo ahora.