Complexidade da alimentação da matriz

26

Seja uma matriz inteira quadrada e seja um número inteiro positivo. Estou interessado na complexidade do seguinte problema de decisão:Mn

A entrada no canto superior direito de Mn positiva?

Observe que a abordagem óbvia do quadrado iterado (ou qualquer outro cálculo explícito) exige que lidemos potencialmente com números inteiros de magnitude duplamente exponencial, ou seja, tendo exponencialmente muitos bits. No entanto, o problema é facilmente visto na classe "PosSLP" de Allender et al. ( "Sobre a complexidade da análise numérica", SIAM J. Comput. 38 (5) ) e, portanto, no quarto nível da hierarquia de contagem .

1) É possível colocar esse problema de alimentação da matriz em uma classe de menor complexidade?

2) Se não, poderia ser difícil para o PosSLP?

3) Estou especialmente interessado no problema de alimentação da matriz para matrizes de baixa dimensão, ou seja, até e incluindo matrizes 6x6. A complexidade pode ser menor para essas matrizes?

Joel
fonte
4
O título não deve ser alterado para "Complexidade da alimentação da matriz"? A exponenciação da matriz (veja, por exemplo, en.wikipedia.org/wiki/Matrix_exponential ) é geralmente entendida como "A = exp (B)" para as matrizes A, B.
Martin Schwarz
Eu vou editar. esse é um bom ponto, @MartinSchwarz
Suresh Venkat
Se você transformar a matriz na forma PDP-1 (que para uma matriz pequena e uma potência suficientemente alta de n pode ser considerada constante), poderá conhecer trivialmente o sinal de cada entrada das entradas diagonais. Então é fácil descobrir as duas multiplicações de matrizes restantes.
Robert Mason
@ Robert Mason: Não sei exatamente o que você está sugerindo. Se D é a forma canônica de M de Jordan, de modo que M ^ n = P ^ (- 1) D ^ n P, então as entradas de D serão tipicamente números algébricos complexos, então o que você quer dizer com "sinal"? Concordo que você pode calcular D e P em tempo polinomial (assumindo representações padrão de números algébricos), mas a expressão que você obtém para a entrada superior direita de M ^ n = P ^ (- 1) D ^ n P será uma expressão envolvendo vários números algébricos elevados à potência n, e não vejo como você pode determinar o sinal dessa expressão com eficiência.
Joel
1
@ Robert Mason: Eu ainda não entendo - como / por que isso é eficiente para matrizes invertíveis? (E aliás, "a maioria das" matrizes são invertíveis, e não o contrário.)
Joel

Respostas:

12

Para matrizes de tamanhos , o Problema de Positividade de Alimentação da Matriz está em P ( consulte este artigo para aparecer no STACS 2015)k=2,3P

SamiD
fonte
Não resisti a postar isso! :-)
SamiD 12/12