¿Se puede comprobar más rápido alguna prueba de que $\det(A) \ne 0$ que la multiplicación de matrices?

Question

Podemos calcular un determinante de una matriz de $n \times n$ en $O(n^3)$ operaciones de varias formas, por ejemplo mediante la descomposición LU. También se sabe (ver, por ejemplo, Wikipedia) que si podemos multiplicar dos matrices de $n \times n$ en $M(n)$ pasos, entonces también podemos calcular el determinante en $O(M(n))$ pasos.

Sin embargo (y esta es la observación motivadora aquí), como en esta pregunta, si $\det(A) = 0$, entonces puedo encontrar un vector $\mathbf x$ tal que $A \mathbf x = \mathbf 0$, y decirte: "$A$ es una matriz singular. Aquí tienes un vector $\mathbf x$ tal que $A \mathbf x = \mathbf 0". Puede que haya hecho mucho trabajo para encontrar $\mathbf x$, pero puedes verificar mi trabajo en solo $O(n^2)$ pasos calculando $A \mathbf x$: más rápido de lo que podrías calcular $\det(A)$ sin ayuda.

¿Es posible, de manera similar, que tome una matriz $A$ con $\det(A) \ne 0$ y escriba una prueba de este hecho que tú también puedas verificar más rápido que calculando $\det(A)$? (Una solución perfecta verificaría la prueba en $O(n^2)$ pasos; esto es lo mejor posible, ya que necesitamos tantos pasos incluso para leer $A".)

---

Observaciones:

• Existe un argumento probabilístico basado en el algoritmo de Freivalds: te doy $A^{-1}$, y te dejo verificar que $AA^{-1} = I'. Hasta donde sabemos, esto todavía requiere $O(M(n))$ tiempo para hacerlo determinísticamente, pero un algoritmo probabilístico puede tomar $O(n^2)$ pasos para lograr una tasa de error unilateral del $\frac12": si $A^{-1}$ es correcto, siempre dirá "sí", y si $A^{-1}$ está equivocado, dirá "no" con una probabilidad de a lo sumo $\frac12$. Como resultado, puedes tomar $O(n^2\log n)$ pasos para lograr una tasa de error unilateral de $n^{-k}$ para cualquier $k$.

• Más generalmente, podríamos pedir una prueba de que $\det(A) = x$ para cualquier valor específico distinto de cero de $x$. Esta fue la pregunta original, pero no hay esperanza de resolver eso para $x$ general si ni siquiera podemos resolver el caso $\det(A) \ne 0". (Después de todo, una prueba de que $\det(A)$ tiene un valor distinto de cero específico $x$ es en particular una prueba de que $\det(A)$ tiene algún valor distinto de cero.)

Answer 1

Solo para compartir otra posible alternativa, un algoritmo aleatorio expandido desde Weidemann proporciona un método para muestrear soluciones del espacio solución (afín) $Ax =b$ donde $A$ es una matriz cuadrada y $b$ está en el espacio de columnas de $A$. Así que en este caso, uno puede elegir $b = 0$ y el algoritmo debería muestrear de forma uniforme del núcleo de $A$ para campos finitos. La idea es ejecutar el algoritmo unas cuantas veces para la misma entrada $A$ y dejar que $b= 0$. Te devolverá algún $x$ y si $x$ no es un vector nulo para ninguno de esos intentos, entonces sabemos que $A$ no es invertible.

La situación en campos infinitos no es tan clara; pero debería arrojar resultados relativamente comparables si eliges un conjunto de muestreo lo suficientemente grande.

Este algoritmo afirma tomar $O(n^2 \log n \log \log n)$ cálculos en el campo base y requiere que el campo base sea lo suficientemente grande, de lo contrario, tomar una extensión de campo. La probabilidad de éxito de este algoritmo es bastante alta, así que con solo repeticiones finitas, creo que es posible determinar si la matriz es invertible más rápido que con $O(n^3)$.

Editar: Otra alternativa es considerar el polinomio mínimo de la secuencia linealmente recurrente $\{u^\top A^i b\}$. (Una secuencia $s_i$ en un espacio vectorial $F$ es linealmente recurrente si existe $n \in \mathbb{N}$ y $a_0,\dots,a_{n-1} \in F$ tal que $\sum_{i=0}^{n-1} a_is_{j+i}$ para todo $j \in \mathbb{N}$. Un ejemplo de una secuencia linealmente recurrente sería la secuencia $A^i$ donde $A$ es una matriz $n\times n$, y no es difícil ver por qué $\{u^\top A^ib\}$ también es linealmente recurrente. El polinomio mínimo de una secuencia linealmente recurrente es simplemente el polinomio $\sum_{i=0}^{n-1} a_ix^i$.)

Ahora, otro resultado en el papel de Kaltofen y Saunders (el mismo papel mencionado anteriormente) es que uno puede 'adivinar' el polinomio mínimo de $A$ lo suficientemente bien utilizando el polinomio mínimo de la secuencia $u^\top A^i b$ eligiendo $u$ y $b$ al azar, siempre que el campo base sea lo suficientemente grande. (Pero de hecho, siempre se obtendría un factor del polinomio de $A$).

Uno podría preguntarse por qué siquiera es relevante la secuencia $u^\top A^i b$. Esto se debe a que es fácil encontrar el polinomio mínimo de esta secuencia de elementos en el campo base a través de un algoritmo dinámico, el algoritmo de Berlekamp - Massey. Uno simplemente puede elegir aleatoriamente $u,b$ y encontrar el polinomio mínimo de la secuencia $u^\top A^i b$.

Pero ahora el problema es que se requiere una secuencia de longitud $2d$ donde $d$ es el grado del polinomio mínimo de $A$, que es desconocido y una suposición razonable es $d = n$. Dudo si este método está incluso por debajo de $O(n^3)$ ya que el algoritmo se basa en Berlekamp Massey.