Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Given a data matrix $D\in\mathbb{R}^{N \times N}$

Can one construct another matrix $M$ that for all permutation matrices $Q^A$,$Q^B$,

if $[\sum_i\sum_j (Q^A_{ij}D_{ij})]^2 \geq [\sum_i\sum_j (Q^B_{ij}D_{ij})]^2$ then $\sum_i\sum_j (Q^A_{ij}M_{ij}) \geq \sum_i\sum_j (Q^B_{ij}M_{ij})$?

p.s. Sorry I don't know how to name the problem so the title is just "Question about inearization". If you have any good idea please tell me.

share|cite|improve this question
Do you have a simple interpretation of the condition $\big(\sum_i\sum_j (Q^A_{ij}D_{ij})\big)^2 \geq \big(\sum_i\sum_j (Q^B_{ij}D_{ij})\big)^2$? That would (i) make it easier for others to understand the problem, and (ii) help you choose a better title. :) – Rahul Jan 25 '13 at 6:53
@RahulNarain I am not sure but maybe it can be represented in terms of Hadamard product $||Q^A\circ D||^2_F \geq ||Q^B\circ D||^2_F$? – Rein Jan 26 '13 at 5:49
I don't know it will be useful but but another formulation for the sums is $\sum_i\sum_j(Q_{ij}^AD_{ij})=Tr[Q^{A\,T}D]$, where the $T$ denotes the transpose and $Tr$ the trace of a matrix. – Sebastien B Jan 27 '13 at 13:09
@SebastienB Thanks for the suggestion. – Rein Jan 28 '13 at 11:50

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.