MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $Q$ be an $n \times n$ real symmetric matrix and $x$ an $n \times 1$ real vector. Consider the following minimization problem:

$\min_{\pi \in S_n} ~(\pi x)^{\rm T} Q (\pi x)$,

where $S_n$ denotes the collection of all permutations on $x$.

I wonder if there is any sufficient condition on the matrix $Q$ that guarantees that the solution is given by the permutation that puts $x$ in increasing order. For instance, such a $Q$ qualifies: $Q = \left(\begin{matrix} 0 & -1 & 0 & 0 \\\ -1 & 0 & 0 & 0 \\\ 0 & 0 & 0 & -1 \\\ 0 & 0 & -1 & 0\end{matrix}\right)$. Does it have anything to do with majorization theory?

P.S., I googled a bit and it seems this is a particularization of the so-called quadratic assignment problem. There are a lot of discussions dealing with complexity of finding the solution. I wonder if we can we come up with some sufficient condition to guarantee that the optimal solution is to simply perform a sort.

share|cite|improve this question
Unless there are more conditions on $x$, a necessary condition is that $Q$ be persymmetric (both equal to its transpose and unchanged when the order of the rows and order of the columns are reversed) since $x$ and $-x$ take the same value on the quadratic form but are sorted in opposite order. – Tracy Hall Aug 3 '10 at 6:02
Did you mean for the example $Q$ to have its $1$'s on the antidiagonal, or to have $-1$'s, or for the optimization to seek the maximum? As stated, $Q$ fails for $x$ with two $0$'s and two $1$'s: the minimum is $0$, but sorting gives $2$. – Tracy Hall Aug 3 '10 at 6:17
Sorry for the typo... 1's should be -1's. – mr.gondolier Aug 3 '10 at 6:24
BTW, the x I am considering is a probability vector, or equivalently, $x \in \mathbb{R}_+^n$. – mr.gondolier Aug 3 '10 at 6:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.