@Robert

It seems that I overlooked the fine print, though I had a suspicious feeling about this. You have convinced me that I had better look for a workaround, which luckily is available for my problem. Thanks.

@acer

You are of course right. Thanks again.

@Robert

That it is harder I knew, though not by how much. A viable method is described here

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

under "solving for P". I just thought naively, diagonalizing A and B seems rather brute force, so I thought there

might be something better.

@acer

Similarity is certainly necessary, though not sufficient. Thanks, though.

A related but slightly different question would be to ask if A and B are related via

B=P A P^-1

where P is a permutation matrix. I'd be really interested in efficient ways to test that.

At the same time, I'm new to this forum and am uncertain whether this warrants a new thread.

Please let me know if it does.

Thanks