0
$\begingroup$

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.

  • 0
    What does it mean for a sum of vectors to be equal to 1?2010-08-12
  • 0
    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.2010-08-12
  • 0
    @Qiaochu Yuan: I guess he is referring to the matrix A and not the elements2010-08-12

1 Answers 1

2

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

  • 0
    Looks correct to me. Thanks a lot Tsuyoshi.2010-08-14