finding permutation matrix I which minimizes TRACE( I* C*( I^T)* D) matrix

I have a problem that is really important for my thesis and i am not studding math so i will be very glad if you help me in this case... thanks for your help in advance

I want to find permutation matrix $P$ which minimizes $\mathrm{trace}(P C P^T D)$, when $C$ and $D$ are given quadratic symmetric matrices.

sorry if its not clear enough

in the link below i found a similar question but there is a bit difference and that is that here we work with permutation matrices.but sorrily i can not come to conclusion:(

https://math.stackexchange.com/q/239352/200836

• What does that minimization problem mean? Are you minimizing some kind of a matrix norm? Take a look at this formatting guide to make the question clearer: meta.math.stackexchange.com/q/5020/166535 – Joonas Ilmavirta Dec 12 '14 at 20:44
• thanks for your comment, we have C and D matrices and we want to find permutation which minimizes the Trace. is there any better way than checking all permutation matrices? – math2014 Dec 12 '14 at 21:42
• I edited your question into a more standard form. For one thing, never use $I$ for any matrix other than an identity matrix unless you want to confuse every mathematician who is watching. I think your question is quite hard. – Brendan McKay Dec 12 '14 at 23:54

1 Answer

This is the well-known problem: http://en.wikipedia.org/wiki/Quadratic_assignment_problem

In general there is no efficient algorithm known for this problem. A much more famous Travelling Salesman Problem is a particular case...

• is there any better way than checking all possible permutations? – math2014 Dec 14 '14 at 8:52
• well, there was a lot of research done on this problem. it would not be necessary to check a fraction of all permutations of n symbols, but still nobody knows how to check less than exponentially (in terms of n) many of them. – Dima Pasechnik Dec 14 '14 at 9:21
• i.e. instead of n! permutations you might still need to check something like $2^n$ of them. – Dima Pasechnik Dec 14 '14 at 9:24
• you might like to check out arxiv.org/abs/1403.7721 for up to date references etc – Dima Pasechnik Dec 14 '14 at 9:39