Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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

 
discard

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

Browse other questions tagged or ask your own question.