¿En términos de complejidad, existe una manera más rápida de comprobar si una matriz es nonsingular que computar el determinante?

Question

Para repetir la pregunta, vamos a $A$ ser una matriz cuadrada. Queremos determinar si $A$ es nonsingular, que es invertible. Una forma es calcular su determinante, y comprobar si es distinto de cero. Sin embargo, si $A$ es invertible, calcular su determinante nos da estrictamente más información que sabiendo que es distinto de cero.

A pesar de la ingenuidad de la complejidad para calcular el determinante es $O(n!)$, más rápido $O(n^3)$ algoritmos de existir. No parece razonable suponer que su podría ser un algoritmo que comprueba nonsingularity que ha estrictamente menor complejidad de la forma más rápida de algoritmos conocidos para calcular el determinante. Es un algoritmo que se conoce su existencia? Es posible que un algoritmo de existir? (Yo soy bastante ignorante en estas áreas de la complejidad computacional)

Estoy interesado principalmente en el caso de que $A$ es real o compleja matriz, pero en el caso de los racionales matrices, o matrices sobre campos finitos son también de interés. Siéntase libre de hablar de las matrices sobre un anillo arbitrario si usted piensa que puede aclarar esta discusión.

Gracias de antemano por cualquier visión de repuesto!

Answer 1

Hay dos métodos que son muy buenos métodos para verificar la singularidad:

1. Como se señaló en los comentarios, la eliminación Gaussiana es un método muy eficiente para su comprobación.

2. Otra forma es usando el condicional número de la matriz. Como sabemos, Si condicional número de es$\infty$, entonces la matriz es no singular. Para calcular la condición de su matriz y comparar con $\frac {1}{\text{e.p.s.}}$ . Ahora el problema se reduce a encontrar la condición. Hasta donde yo sé, la búsqueda de número condicional es más fácil que encontrar los determinantes.

EDITAR:

Todo lo que sé sobre la búsqueda de la Condición...

1. Si la matriz es triangular, se puede aproximar la condición por $\kappa(A) \geq \frac{\max_i(|a_{ii}|)}{\min_i(|a_{ii}|)}$, es una aproximación razonable, pero que da unos resultados equivocados. Tenga en cuenta que si utilizamos la factorización QR, podemos decir que el $\kappa (A)=\kappa(Q) \text{ if } A=QR$. Aunque para triangular superior de la matriz, podemos encontrar condicional no. en $O(n)$.

2. Para la matriz tridiagonal se puede encontrar en $O(n).

3. Para otras matrices, ya sea en primer lugar, realizar QR, a continuación, utilizar 1, o tratar de encontrar los valores propios de la matriz como de la condición número es la relación de mayor valor singular a la más pequeña. Ahora una manera de hacerlo es utilizar la descomposición SVD o directamente búsqueda de los valores singulares. A pesar de la descomposición SVD tarda $O(n^3)$. Creo algoritmos para la acaba de encontrar valores singulares de existir y (o debería ser) más rápido. Usted tendrá que buscar para ellos..

Restante es mi punto de vista personal, y usted es libre de estar en desacuerdo, por lo tanto he escondido :-)

También creo que la practicidad de los algoritmos deben ser tomados en consideración. Sí, es cierto que se puede encontrar determinante en $O(n^3)$, lo mismo que la eliminación Gaussiana, pero la eliminación Gaussiana es fácil de implementar, mientras que el determinante no es tan fácil de implementar. (Por ejemplo, puedo implementar eliminación Gaussiana, pero aún no sé cuál es el algoritmo para el factor determinante en $O(n^3)$ es?