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.



a provable upper bound on the summation
Here is a copy-and-paste of the [answer](https://math.stackexchange.com/questions/2250/a-provable-upper-bound-on-the-summation/2380#2380) 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.$$


