похожие матрицы

16

Для двух матриц A и B задача принятия решения о том, существует ли матрица перестановок P такая, что B = P - 1 A P , эквивалентна (граф изоморфизма). Но если мы расслабим P как просто обратимую матрицу, то в чем сложность? Существуют ли какие-либо другие ограничения на обратимую матрицу P , помимо перестановки, которые связывают эту проблему с другими сложными проблемами?n×nABPB=P1APGIPPGI

DurgaDatta
источник
Может быть, я должен был спросить это, прежде чем публиковать ответ, но что вы пробовали, прежде чем публиковать этот вопрос здесь?
Цуёси Ито
@TsuyoshiIto Я пробовал в wikipdia и mathworld, также пытался найти поисковый запрос в Google, этот вопрос слишком элементарный, чтобы задавать его здесь? Мне было более интересно, если какой-то вариант этой проблемы даст некоторое представление о GI.
DurgaDatta
Благодарю. Я думаю, что уровень вопроса в порядке, но я просто удивился, почему вы не пришли к такому же выводу, как я. То, что я сделал, чтобы написать ответ, - это просто поиск «сходства матриц» в Википедии, чтобы найти нормальную форму, которую можно легко вычислить (в отличие от нормальной формы Джордана, которая требует алгебраически замкнутое поле). Я думаю, что вы могли бы найти ту же информацию, если бы вы смотрели на Википедию более внимательно.
Цуёси Ито
Я буду осторожен в следующий раз. Спасибо.
DurgaDatta

Ответы:

11

Матрицы A и B , элементы которых находятся в поле F , похожи (в F ) тогда и только тогда, когда они имеют одинаковую нормальную форму Фробениуса . Согласно быстрому поиску, кажется, что нормальная форма Фробениуса матрицы n × n может быть вычислена с помощью полевых операций O ( n 3 ) [Sto98], и что это можно улучшить до уровня, сравнимого со сложностью умножения матриц [ Sto01].

[Sto98] Арне Сторджоханн. Алгоритм O ( n 3 ) для нормальной формы Фробениуса. В материалах Международного симпозиума по символическим и алгебраическим вычислениям (ISSAC) 1998 года , стр. 101–105, август 1998 года. DOI: 10.1145 / 281508.281570 .

[Sto01] Арне Сторджоханн. Детерминированные вычисления формы Фробениуса. В 42-м Симпозиуме IEEE по основам информатики (FOCS) , с. 368–377, октябрь 2001 г. DOI: 10.1109 / SFCS.2001.959911 .

Цуёси Ито
источник
5

Есть действительно другие ограничения на которые связывают эту проблему с GI. Например, если требуется, чтобы P было произведением Кронекера (тензора) P 1P 2P 3 , то возникающая в результате проблема столь же сложна, как эквивалентность трехвалентных тензоров, что примерно такой же сложности, как и эквивалентность линейного кода, который, в свою очередь, известен как GI-жесткий (но не известен как эквивалент GI).PPP1P2P3

GnXnnx,yXnGnGnVnGnXn=Vn(Vn)

Gn=SnVn=RnGn=GLn(F)Vn=FnGn=GLa×GLb×GLcVn=FaFbFc

Джошуа Грохов
источник