Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
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|cite|improve this answer
Looks correct to me. Thanks a lot Tsuyoshi. – Manan Aug 14 '10 at 5:30

Your Answer


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.