# a provable upper bound on the summation

Given the following:

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

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

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

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

Find a provable upper bound on:

$$\sum_{i,j=1}^{z}\left\lvert\frac1n\cdot\sum_{k=1}^{n}[a_{ki}(a_{f(k)j} - a_{g(k)j})]\right\rvert$$

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

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

-
What does it mean for a sum of vectors to be equal to 1? –  Qiaochu Yuan Aug 12 '10 at 16:38
it is not the sum of vectors. it is the summation over the components of the vector $a_r$. $a_r = (a_{r1}, a_{r2}, ..., a_{rz})$ and a_{r1} + a_{r2} + ... + a_{rz} = 1 for all r. –  Manan Aug 12 '10 at 16:54
@Qiaochu Yuan: I guess he is referring to the matrix A and not the elements –  anonymous Aug 12 '10 at 16:55

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