Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

up vote 2 down vote accepted

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

share|improve this answer
    
Looks correct to me. Thanks a lot Tsuyoshi. –  Manan Aug 14 '10 at 5:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.