2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Joonas Ilmavirta Dec 12 '14 at 20:44
  • $\begingroup$ 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? $\endgroup$ – math2014 Dec 12 '14 at 21:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Brendan McKay Dec 12 '14 at 23:54
4
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ is there any better way than checking all possible permutations? $\endgroup$ – math2014 Dec 14 '14 at 8:52
  • $\begingroup$ 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. $\endgroup$ – Dima Pasechnik Dec 14 '14 at 9:21
  • 1
    $\begingroup$ i.e. instead of n! permutations you might still need to check something like $2^n$ of them. $\endgroup$ – Dima Pasechnik Dec 14 '14 at 9:24
  • $\begingroup$ you might like to check out arxiv.org/abs/1403.7721 for up to date references etc $\endgroup$ – Dima Pasechnik Dec 14 '14 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.