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$
3
  • $\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$ Dec 12, 2014 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, 2014 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$ Dec 12, 2014 at 23:54

1 Answer 1

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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