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" <[EMAIL PROTECTED]> 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/ _______________________________________________ Forum mailing list [email protected] http://mail.gap-system.org/mailman/listinfo/forum
