MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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.

-
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 2010 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 2010 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 2010 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 2010 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 2010 at 12:46

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

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

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

EDIT: My answer is wrong, though not for the reason given by the commenter; I read the absolute values as being inside the summation.

This is false. Consider the matrix $$\begin{pmatrix} \epsilon/2 & 0 \\ 1-\epsilon/2 & 1 \end{pmatrix}.$$

Letting $f$ be the identity and $g$ the only other permutation, the sum is on the order of $\epsilon$, not $\epsilon^2$. Furthermore, rearranging sums easily gives $\epsilon$ as an upper bound in the general case, assuming the entries are all positive.

-
 This is not a counterexample because each row must sum to 1. In fact, it is easy to show that the sum in question is equal to ε^2/2 if n=2. I posted my answer to math.stackexchange.com/questions/2250/… – Tsuyoshi Ito Aug 13 2010 at 18:40 Actually I suppose I meant the transpose; regardless, I have the absolute values in the wrong place. – Daniel Litt Aug 13 2010 at 18:50 The answer given by Tsuyoshi at math.stackexchange.com looks correct to me. Can anyone tell me what should I do here. Should I leave it as it is, or should I paste that answer here or should I delete this question? – Manan Aug 14 2010 at 5:33