# a conclusive 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 also 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$.

Locate a conclusive 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 also $g$ are permutations over the set $\{1,2,\ldots,n\}$ such that $\forall i\colon f(i) \neq g(i)$.

I am anticipating the bound to be $\epsilon^2$, yet I have no suggestion just how to confirm it.

0
2019-05-09 11:32:35
Source Share
Evidence . Given that $$\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}|.$$ Consequently, the amount concerned goes to the majority of $$\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.$$