Complejidad de la potencia de la matriz.

Sea una matriz entera cuadrada, y sea un entero positivo. Estoy interesado en la complejidad del siguiente problema de decisión: $M$ $n$

¿Es positiva la entrada superior derecha de ? $M^n$

Tenga en cuenta que el enfoque obvio de la cuadratura iterada (o cualquier otro cálculo explícito) requiere que manejemos potencialmente enteros de magnitud doblemente exponencial, es decir, que tengan exponencialmente muchos bits. Sin embargo, el problema se ve fácilmente en la clase "PosSLP" de Allender et al. ( "Sobre la complejidad del análisis numérico", SIAM J. Comput. 38 (5) ) y, por lo tanto, en el cuarto nivel de la jerarquía de conteo .

1) ¿Es posible colocar este problema de alimentación de matriz en una clase de menor complejidad?

2) Si no, ¿podría ser posiblemente PosSLP-hard?

3) Estoy especialmente interesado en el problema de alimentación de matrices para matrices de baja dimensión, es decir, hasta matrices de 6x6 inclusive. ¿Podría la complejidad ser menor para tales matrices?

cc.complexity-theory linear-algebra matrices Joel
fuente

¿No debería cambiarse el título a "Complejidad de la alimentación de matrices"? La exponenciación de matrices (véase, por ejemplo, en.wikipedia.org/wiki/Matrix_exponential ) se entiende generalmente como "A = exp (B)" para las matrices A, B.

Martin Schwarz

Lo editaré ese es un buen punto, @MartinSchwarz

Suresh Venkat

Si transforma la matriz en forma PDP-1 (que para una matriz pequeña y una potencia suficientemente alta de n puede considerarse constante), puede conocer el signo de cada entrada de las entradas diagonales de manera trivial. Entonces es fácil descubrir las dos multiplicaciones matriciales restantes.

Robert Mason

@ Robert Mason: No estoy exactamente seguro de lo que estás sugiriendo. Si D es la forma canónica de Jordan de M, de modo que M ^ n = P ^ (- 1) D ^ n P, entonces las entradas de D serán típicamente números algebraicos complejos, entonces, ¿qué quiere decir con su "signo"? Estoy de acuerdo en que puedes calcular D y P en tiempo polinómico (suponiendo representaciones estándar de números algebraicos), pero la expresión que obtienes para la entrada superior derecha de M ^ n = P ^ (- 1) D ^ n P será una expresión involucrando varios números algebraicos elevados a la potencia n, y no veo cómo puedes determinar el signo de esta expresión de manera eficiente.

Joel

@Robert Mason: Todavía no entiendo, ¿cómo / por qué es esto eficiente para las matrices invertibles? (Y, por cierto, "la mayoría" de las matrices son invertibles, en lugar de lo contrario.)

Joel

Complejidad de la potencia de la matriz.

Respuestas: