Question

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.

Answer 1

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 ε². (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.$$

Answer 2

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.