Две матрицы, связанные перестановкой

15

Какова вычислительная сложность следующей задачи:

с учетом двух комплексных матриц A и B проверить, есть ли матрица перестановок Р таким образом, что: В = Р Р Т .N×NAВп

Взнак равнопAпT,

Если это помогает, можно предположить, что и B эрмитовы (или даже что A и B действительные и симметричные).AВAВ

Примечания:

Проблема связана с проверкой, связаны ли два набора векторов унитарным вращением, см. Наборы векторов, связанных вращением - MathOverflow . В этом контексте и В являются грамианскими матрицами .AВ

Задача, по крайней мере, такая же сложная, как и проблема изоморфизма графов - возьмите и B в качестве матриц смежности.AВ

Петр Мигдаль
источник

Ответы:

18

Это эквивалентно решению, являются ли два заданных мультиграфа (или гранично-помеченных графа) изоморфными или нет, что, как известно, эквивалентно обычной проблеме изоморфизма графов.

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