¿Existe una forma rápida de verificar si una matriz tiene valores propios pequeños?

Question

Tengo cientos de millones de matrices simétricas de 0/1 de tamaño moderado (digamos 20x20 a 30x30) que (obviamente) tienen eigenvalores reales.

Deseo extraer de esta lista el diminuto número de matrices que tienen ningún eigenvalor pequeño, donde estoy llamando eigenvalor $\lambda$ pequeño si satisface $|\lambda| < 1$.

Obviamente puedo hacer esto calculando el polinomio característico de cada matriz y procediendo a partir de ahí. Sin embargo, preferiría no calcular cientos de millones de polinomios característicos si puedo evitarlo.

Por lo tanto, estoy buscando técnicas, heurísticas, etc. que se pueden utilizar para probar rápidamente una matriz en busca de la presencia de un eigenvalor pequeño para poder eliminar inmediatamente la matriz.

Por ejemplo, si una matriz tiene determinante $0$ entonces definitivamente tiene un eigenvalor pequeño (o sea, $0$) y se puede eliminar inmediatamente. Experimentos rápidos y sucios con SageMath muestran que para una muestra aleatoria de mis matrices, los determinantes se pueden calcular en aproximadamente $6$% del tiempo requerido para calcular los polinomios característicos, y que alrededor del $15$% de las matrices entrantes tienen determinante $0$. Por lo tanto, gano un poco al calcular primero los determinantes y desechar esas matrices con determinante $0$.

Parece que esta propiedad es algo especial porque solo una fracción minúscula de mis cientos de millones no tienen eigenvalores pequeños. Sin embargo, he buscado bastante y solo he encontrado algunas referencias tangencialmente relacionadas con matrices con esta propiedad, aunque un par más sobre matrices sin eigenvalores de módulo mayor que uno.

Pregunta ¿Hay alguna otra heurística, tal vez más sofisticada, que pueda detectar la presencia de un eigenvalor pequeño de una matriz simétrica?

Answer 1

La técnica de iteración de potencia se utiliza a menudo para calcular el eigenvalor/eigenvector dominante de una matriz arbitraria. La técnica de iteración de potencia es simple y eficiente, pero no siempre funciona y solo da el eigenvalor/eigenvector dominante, aunque la iteración de potencia funciona mejor para matrices simétricas. También podemos usar la iteración de potencia (u otro algoritmo iterativo) para calcular el eigenvalor mínimo de una matriz simétrica.

Supongamos que $A$ es simétrica (los eigenvalores deben ser reales para que funcione). Sea $B=A^2$. Supongamos que $B$ tiene eigenvalores $\lambda_1\geq\dots\geq\lambda_n$. Sea $\mu>0$. Sea $C=\mu\cdot I-B$. Entonces $C$ tiene eigenvalores $\mu-\lambda_1,\dots,\mu-\lambda_n$. Si $|\mu-\lambda_n|\geq|\mu-\lambda_1|$, entonces el radio espectral de $C$ será $\mu-\lambda_n$ y este radio espectral puede ser calculado utilizando la iteración de potencia. Aunque deseamos que $|\mu-\lambda_n|\geq|\mu-\lambda_1|$, es mejor si $\mu$ no es muy grande ya que queremos que la iteración de potencia converja rápidamente.

Para usar la iteración de potencia, comenzamos con un vector aleatorio $v_0$, y luego fijamos $v_{r+1}=Cv_r$ para todos los $r$. Cada paso en la iteración de potencia se puede calcular eficientemente ya que $Cv_r=\mu\cdot v_r-A(Av_r)$ donde los paréntesis indican el orden más rápido de las operaciones (no necesitamos calcular $B$ para obtener $Cv_r$). En este caso, $\|v_{r+1}\|/\|v_r\|$ convergerá hacia el radio espectral de $C$.