¿Cuál es la forma más eficaz de determinar si una matriz es invertible?

Question

Estoy aprendiendo álgebra lineal con el Open Courseware del MIT Curso 18.06

A menudo, el profesor dice "... suponiendo que la matriz es invertible...".

En alguna parte de la conferencia dice que usar un determinante en un $n \times n$ es del orden de $O(n!)$ operaciones, donde una operación es una multiplicación y una sustracción.

¿Existe una forma más eficiente? Si el objetivo es obtener la inversa, y no sólo determinar la invertibilidad, ¿cuál es la forma más eficaz de hacerlo?

Answer 1

Una matriz es invertible si su determinante es distinto de cero.

Existen algoritmos que encuentran el determinante en ligeramente peor que O(n 2 )

Answer 2

El libro de Lazarsfeld Positividad en la geometría algebraica parece encajar en la categoría ``Cualquier persona de mi campo que no haya leído este artículo ha llevado una existencia empobrecida''.

Estoy de acuerdo con Scott sobre "cualquier cosa de Serre". Su FAC y GAGA son joyas; te cambiarán la vida.

Answer 3

El cálculo del determinante y la eliminación de Gauss están bien si se utilizan cálculos exactos, por ejemplo, si las entradas de la matriz son números racionales y sólo se utilizan números racionales durante los cálculos. La desventaja es que el numerador y el denominador pueden ser muy grandes. Así que el número de operaciones puede ser O(n 2.376 ) o O(n 3 ), pero el coste de cada suma y multiplicación es mayor a medida que n crece porque los números son más grandes.

Esto no es un problema si se utilizan números en coma flotante, pero entonces se tiene el problema de que los cálculos en coma flotante no son exactos. Algunos métodos son más sensibles a esto que otros. En particular, la comprobación de la invertibilidad mediante el cálculo del determinante es una mala idea en esta configuración. La eliminación gaussiana es mejor. Aún mejor es utilizar la descomposición del valor singular, que se tratará hacia el final del curso del MIT.