# a provable upper bound on the summation [closed]

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.

-

## 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

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.$$