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

Given the following:

  • an $(n \times z)$ matrix $A = {(a_1,a_2, ... ,a_n)}^{T}$ where $z \geq n$ and every $a_i$ is a $z$-dimensional row vector.

  • $a_i = [a_{i1} a_{i2} ... a_{iz}]$ where $a_{ij} \geq 0 \forall j$

  • $\sum_{i=1}^{z}a_{ri} = 1, \forall r \in ${$1,2,...,n$}.

  • $\sum_{i=1}^{z}|a_{pi} - a_{qi}| \leq \epsilon, \forall p,q$ where $\epsilon << 1$.

Find a provable upper bound on:

  • $\sum_{i,j=1}^{z}|(1/n)*\sum_{k=1}^{n}[a_{ki}.(a_{f(k)j} - a_{g(k)j})]|$

where f and g are permutations over the set {$1,2,...,n$} such that $f(i) \neq g(i) \forall i$.

I am expecting the bound to be $\epsilon^2$ but I have no idea how to prove it.

share|improve this question

closed as no longer relevant by Andrea Ferretti, S. Carnahan Aug 14 '10 at 14:59

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

Dear Manan, you already posted your question on math.stackexchange. I'm not sure there is an official policy about this yet, but doubling the effort of people who are doing this for free is not nice. You should have at least linked the other question: math.stackexchange.com/questions/2250/… –  Andrea Ferretti Aug 13 '10 at 12:29
Moreover the question you posted looks a lot like homework, which is not the point of the present site. Hence I'm voting to close. –  Andrea Ferretti Aug 13 '10 at 12:30
I am sorry for the repetition. Actually I am new at both these websites and I wasn't sure which was the correct website for it. In future I'll definitely keep this in mind. Thanks for pointing it out and sorry again. –  Manan Aug 13 '10 at 12:32
Ok, no problem. Still, if you want it not to be closed, you should give some more information why you interested in this. As stated, the question looks like copied verbatim from a problem book, and homework is explicitly discouraged on this site. –  Andrea Ferretti Aug 13 '10 at 12:35
Actually this came up during my research (albeit at a young stage) on Secure Communication that I am pursuing here at IIIT as a B.Tech + M.S. student. I haven't copied this from anywhere. I just tried to frame my problem as formally as I could (as stated in FAQ). The conditions that are given to hold come from the definition of secrecy from Mathew Franklin's Paper (springerlink.com/content/p0624333842u8120). To prove the solution to my problem I have to show that the expression (in the problem statement) is bounded by $\epsilon^2$. –  Manan Aug 13 '10 at 12:46

1 Answer 1

up vote 1 down vote accepted

Here is a copy-and-paste of the answer I posted to the same question on math.stackexchange.com so that the questioner can close this question.

The sum in question is at most ε2. (We do not need the condition that the row sum equals 1 or the condition f(i)≠g(i) to obtain this.)

Proof. Since $$\sum_{k=1}^n(a_{f(k)j}-a_{g(k)j})=\sum_{k=1}^na_{f(k)j}-\sum_{k=1}^na_{g(k)j}=0,$$ we have $$\left|\sum_{k=1}^na_{ki}(a_{f(k)j}-a_{g(k)j})\right| =\left|\sum_{k=1}^n(a_{ki}-a_{1i})(a_{f(k)j}-a_{g(k)j})\right|$$ $$\le\sum_{k=1}^n|a_{ki}-a_{1i}||a_{f(k)j}-a_{g(k)j}|.$$ Therefore, the sum in question is at most $$\frac1n\sum_{i,j=1}^z\sum_{k=1}^n|a_{ki}-a_{1i}||a_{f(k)j}-a_{g(k)j}| =\frac1n\sum_{k=1}^n\left(\sum_{i=1}^z|a_{ki}-a_{1i}|\right)\left(\sum_{j=1}^z|a_{f(k)j}-a_{g(k)j}|\right)$$ $$\le\frac1n\sum_{k=1}^n\epsilon^2=\epsilon^2.$$

share|improve this answer
But next time please do not post your question to more than one site at the same time. –  Tsuyoshi Ito Aug 14 '10 at 11:17
@Tsuyoshi: I'll definitely keep that in mind in future. Thanks again. –  Manan Aug 14 '10 at 16:44

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