¿Existe una manera fácil de encontrar el signo del determinante de una matriz ortogonal?

Question

Acabo de aprender que si una matriz es ortogonal, su determinante sólo puede tener valor 1 o -1. Ahora bien, si se me presentara una matriz grande en la que me costara mucho esfuerzo calcular su determinante, pero sé que es ortogonal, ¿hay alguna forma más sencilla de averiguar si el determinante es positivo o negativo que la forma estándar de calcular el determinante?

Answer 1

Depende de lo que signifique "manera fácil". No hay ningún atajo conocido para los determinantes de las matrices ortogonales, pero la mayoría de los algoritmos conocidos se ejecutarán más rápido para ellos. Esto no lo detectan las simples estimaciones de complejidad en términos de tamaño de la matriz únicamente. Dichas estimaciones suponen que las operaciones aritméticas se realizan en tiempo constante, independientemente del tamaño de los números implicados. Esto ignora exactamente la ventaja que tienen las matrices ortogonales sobre las peor condicionadas.

Si se tiene en cuenta el tamaño de los números que aparecen en los cálculos utilizando el coste del bit, entonces en lugar de $O(n^3)$ se obtiene más matizado $O^{\sim}\big(n^3(1+\log(\Delta(A)\|A\|))\big)$ , donde $\Delta(A)$ es el defecto de ortogonalidad de $A$ (suave $O^{\sim}$ significa que los términos logarítmicos no se muestran). Esto muestra una clara ventaja para las matrices ortogonales, en general $\log(\Delta(A)\|A\|)$ puede ser $O^{\sim}(n\log\|A\|)$ .

El $O(n^3)$ La línea de base procede de algoritmos que utilizan métodos estándar y puede mejorarse. Strassen demostró que la complejidad del cálculo de determinantes es equivalente a la de la multiplicación de matrices. El algoritmo de multiplicación más conocido es Le Gall's con complejidad $O(n^{2.3728639})$ mejor que el clásico $O(n^3)$ . Pero parece que no se sabe si el mejor exponente para las matrices ortogonales es estrictamente menor que para las generales. Incluso si no lo es, el cálculo para ellas sigue siendo más fácil en cuanto al coste en bits.

Answer 2

Lo que sigue parece ser una encuesta de resultados en este ámbito: http://www4.ncsu.edu/~kaltofen/bibliografía/02/KaVi02.pdf Así que revisar eso y las referencias sería bueno. Un rápido vistazo al documento indica que los métodos funcionan mejor con matrices cercanas a las ortogonales, así que espero que esto signifique que los métodos y los límites de error para una matriz ortogonal conocida son relativamente agradables y predecibles.

Answer 3

Una forma ligeramente más rápida que el método de fuerza bruta sería calcular el producto cruzado (léase: dual de Hodge del producto cuña) del primer $n-1$ y comparar el resultado con la última columna.

Esto, lamentablemente, sólo reduce $O(n)$ operaciones, por lo que no altera significativamente el $O(n^3)$ complejidad.

Answer 4

Usando la desigualdad de Hadamard:

$$\det(M)\leq\prod_{i=1}^{N} m_{ii}.$$

al menos se puede afirmar que el signo de los determinantes es negativo si la suma del producto de los elementos diagonales es como máximo cero. Sin embargo, estoy luchando por mí mismo encontrar el límite inferior.

Suyo

tcsh