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

Obviamente, es fácil tomar el determinante de una matriz de 2x2. Hay una manera rápida de hacer un 3x3 también.

$\newcommand\RED{\color{red}} \newcommand\BLUE{\color{blue}} \newcommand\GREEN{\color{green}} A= \begin{bmatrix} \ a & b & c\\ d & e & f\\ g & h & i\\ \end{bmatrix}$

Empieza por la fila superior y multiplica las tres diagonales mostradas en rojo, azul y verde y súmalas.

$\newcommand\RED{\color{red}} \newcommand\BLUE{\color{blue}} \newcommand\GREEN{\color{green}} A= \begin{bmatrix} \ \RED a & \BLUE b & \GREEN c\\ \GREEN d & \RED e & \BLUE f\\ \BLUE g & \GREEN h & \RED i\\ \end{bmatrix}$

Ahora ,empieza a lo largo de la fila inferior y multiplica el segundo conjunto de tres diagonales como se muestra abajo en rojo, verde y azul, y réstalas.

$\newcommand\RED{\color{red}} \newcommand\BLUE{\color{blue}} \newcommand\GREEN{\color{green}} A= \begin{bmatrix} \ \BLUE a & \GREEN b & \RED c\\ \GREEN d & \RED e & \BLUE f\\ \RED g & \BLUE h & \GREEN i\\ \end{bmatrix}$

El resultado es $det(A)=aei+bfg+cdh-gec-hfa-idb$

Básicamente, esto te permite escribir la respuesta al determinante de cualquier matriz de 3x3 que veas con el mínimo esfuerzo. Si conoces la regla de Cramers, te permite escribir inmediatamente las respuestas a cualquier sistema de ecuaciones lineales de 3x3.

Por desgracia, se trata de una coincidencia matemática. NO es cierto que el determinante de una matriz cuadrada sea simplemente la suma y la diferencia de todos los productos de las diagonales. Para una matriz 4x4, se expande a través de la primera columna por cofactores, y luego se toma el determinante de las matrices 3x3 resultantes como se ha indicado anteriormente. De nuevo, si conoces la regla de Cramers, puedes escribir las respuestas a un sistema 4x4 de ecuaciones lineales con sólo un poco más de esfuerzo.

Para algo más grande, sin embargo, se vuelve absurdamente complejo (usa un ordenador, que para eso están) Hay dos términos cuando se calcula el determinante de una matriz de 2x2. Para una matriz de 3x3 hay seis términos. Para una matriz de 4x4 hay 24 términos. Para una matriz de 5x5 hay 120 términos. (expande por cofactores, luego expande cada una de las 5 matrices 4x4 resultantes por cofactores y luego toma el determinante de las matrices 3x3 resultantes por diagonales. Si se tiene mucho cuidado, se puede llegar a una matriz de 5x5, pero una matriz de 6x6 da 720 términos y una matriz de 7x7 da 5040 términos. Para una matriz de n x n, se necesitan ¡n! términos. El ordenador utiliza algoritmos mucho más eficientes.