Dua matriks yang terkait dengan permutasi

15

Apa kompleksitas komputasi dari masalah berikut:

diberikan dua kompleks matriks A dan B cek jika ada permutasi matriks P sehingga: B = P A P T .n×nSEBUAHBP

B=PSEBUAHPT.

Jika itu membantu, orang dapat berasumsi bahwa dan B adalah hermitian (atau bahkan A dan B itu nyata dan simetris).SEBUAHBSEBUAHB

Catatan:

Masalahnya berasal dari memeriksa apakah dua set vektor terkait oleh rotasi kesatuan, lihat Set vektor terkait oleh rotasi - MathOverflow . Dalam konteks itu, dan B adalah matriks Gramian mereka .SEBUAHB

Masalahnya setidaknya sama sulitnya dengan masalah grafik isomorfisme - ambil dan B sebagai matriks kedekatan.SEBUAHB

Piotr Migdal
sumber

Jawaban:

18

Ini sama dengan memutuskan apakah dua multigraf yang diberikan (atau graf berlabel tepi) adalah isomorfik atau tidak, yang diketahui setara dengan masalah isomorfisme graf biasa.

Tsuyoshi Ito
sumber