Post Closed as "no longer relevant" by Andrea Ferretti, S. Carnahan
2 all entries positive

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.

1

# a provable upper bound on the summation

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}]$

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