Сложность питания матрицы

26

Пусть - квадратная целочисленная матрица, а n - положительное целое число. Меня интересует сложность решения следующей проблемы:Mn

Является ли запись в верхнем правом углу положительной?Mn

Обратите внимание, что очевидный подход повторного возведения в квадрат (или любого другого явного вычисления) требует, чтобы мы потенциально обрабатывали целые числа с удвоенной экспоненциальной величиной, то есть имели экспоненциально много битов. Однако проблема легко видна в классе «PosSLP» Аллендера и др. ( «О сложности численного анализа», SIAM J. Comput. 38 (5) ), и, следовательно, в четвертом уровне иерархии счета. ,

1) Можно ли поместить эту проблему питания матрицы в более низкий класс сложности?

2) Если нет, то может ли это быть PosSLP-сложным?

3) Меня особенно интересует проблема питания матриц для низкоразмерных матриц, то есть вплоть до матриц 6x6 включительно. Может ли сложность быть ниже для таких матриц?

Joel
источник
4
Не следует ли изменить название на «Сложность питания матрицы»? Возведение в степень матрицы (см., Например, en.wikipedia.org/wiki/Matrix_exponential ) обычно понимается как «A = exp (B)» для матриц A, B.
Мартин Шварц
Я отредактирую это. это хороший момент, @MartinSchwarz
Suresh Venkat
Если вы преобразуете матрицу в форму PDP-1 (которую для маленькой матрицы и достаточно высокой степени n можно считать постоянной), то вы можете узнать знак каждой записи диагональных элементов тривиально. Тогда легко вычислить оставшиеся две матричные умножения.
Роберт Мейсон
@ Роберт Мейсон: Я не совсем уверен, что вы предлагаете. Если D является йордановой канонической формой M, так что M ^ n = P ^ (- 1) D ^ n P, то элементы D, как правило, будут комплексными алгебраическими числами, так что вы подразумеваете под их «знаком»? Я согласен, что вы можете вычислить D и P за полиномиальное время (при условии стандартного представления алгебраических чисел), но выражение, которое вы получите для записи в верхнем правом углу M ^ n = P ^ (- 1) D ^ n P, будет выражением с участием различных алгебраических чисел, возведенных в степень n, и я не понимаю, как вы можете эффективно определить знак этого выражения.
Джоэл
1
@ Роберт Мейсон: Я до сих пор не понимаю - как / почему это эффективно для обратимых матриц? (И, между прочим, «большинство» матриц являются обратимыми, а не противоположными.)
Джоэл

Ответы:

12

k=2,3п

SamiD
источник
Не могу удержаться от публикации этого! :-)
SamiD