Hey,

I have a little mathematical question here.

Suppose we have two matrices A and B (both of the dimension N x N). Now we want to check whether or not another matrix P (permutation matrix) exists, so that

P*A*(P^T) = B

Does anyone have a good algorithm (with detailed explanation)?

I checked wikipedia, but I don't quite understand which algorithm is

appropriate here... First time I'm dealing with such a problem.

And I cant use any lib (like GSL), because I'd like to use the algorithm

with parallel processing (A and B might get large 10000 x 10000 and more).

Any advice for a good algorithm would be great.

Thanks in advance

Mathes

I have a little mathematical question here.

Suppose we have two matrices A and B (both of the dimension N x N). Now we want to check whether or not another matrix P (permutation matrix) exists, so that

P*A*(P^T) = B

Does anyone have a good algorithm (with detailed explanation)?

I checked wikipedia, but I don't quite understand which algorithm is

appropriate here... First time I'm dealing with such a problem.

And I cant use any lib (like GSL), because I'd like to use the algorithm

with parallel processing (A and B might get large 10000 x 10000 and more).

Any advice for a good algorithm would be great.

Thanks in advance

Mathes

http://en.wikipedia.org/wiki/Permutation_matrix#Solving_for_P

Though you should start with checking traces of A and B (they should be equal). Note, P^T = P^-1 for a permutation matrix.

Also, I suggest that in the future you use http://math.stackexchange.com/ for that sort of questions.

Though you should start with checking traces of A and B (they should be equal). Note, P^T = P^-1 for a permutation matrix.

Also, I suggest that in the future you use http://math.stackexchange.com/ for that sort of questions.

Last edited on

Thanks hamsterman.

Maybe I should check the English version of Wikipedia more often. Much more informative

than the German one...

And thanks for the site. Next math question will go there ;-)

Maybe I should check the English version of Wikipedia more often. Much more informative

than the German one...

And thanks for the site. Next math question will go there ;-)

Topic archived. No new replies allowed.