[GAP Forum] A question about matrices

[Dima Pasechnik]

Dear Forum,

this is edge-weighted graph isomorphism problem, so no efficient
(polynomial-time wrt dimension) procedure is known, at all.
One can convert the problem into finding an isomorphism between two
vertex-weighted graphs, by constructing line graphs of A and B and using
GRAPE's IsIsomorphicGraph function. canonicalLabelling can then be used to
recover P, if needed.


On 5/12/06 11:33 AM, "D N" <dn2447 at yahoo.com> wrote:

>  Suppose A and B are two square matrices of the same dimension (say 1000). Is
> there an efficient way to check whether A = PBP^t
>  for some permutation matrix P (P^t = transpose of P).
>  
>  Thanks,
>  Deepak Naidu
-- 
Dima Pasechnik
http://www.ntu.edu.sg/home/dima/