a provable upper bound on the summation - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-05-21T09:48:15Z http://mathoverflow.net/feeds/question/35487 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35487/a-provable-upper-bound-on-the-summation a provable upper bound on the summation Manan 2010-08-13T12:25:36Z 2010-08-14T11:16:16Z <p>Given the following:</p> <ul> <li><p>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. </p></li> <li><p>$a_i = [a_{i1} a_{i2} ... a_{iz}]$ where $a_{ij} \geq 0 \forall j$</p></li> <li><p>$\sum_{i=1}^{z}a_{ri} = 1, \forall r \in${$1,2,...,n$}. </p></li> <li><p>$\sum_{i=1}^{z}|a_{pi} - a_{qi}| \leq \epsilon, \forall p,q$ where $\epsilon &lt;&lt; 1$.</p></li> </ul> <p>Find a provable upper bound on:</p> <ul> <li>$\sum_{i,j=1}^{z}|(1/n)*\sum_{k=1}^{n}[a_{ki}.(a_{f(k)j} - a_{g(k)j})]|$ </li> </ul> <p>where f and g are permutations over the set {$1,2,...,n$} such that $f(i) \neq g(i) \forall i$.</p> <p>I am expecting the bound to be $\epsilon^2$ but I have no idea how to prove it.</p> http://mathoverflow.net/questions/35487/a-provable-upper-bound-on-the-summation/35513#35513 Answer by Daniel Litt for a provable upper bound on the summation Daniel Litt 2010-08-13T17:55:21Z 2010-08-13T18:51:03Z <p>EDIT: My answer is wrong, though not for the reason given by the commenter; I read the absolute values as being inside the summation. </p> <p>This is false. Consider the matrix <code>$$\begin{pmatrix} \epsilon/2 &amp; 0 \\ 1-\epsilon/2 &amp; 1 \end{pmatrix}.$$</code></p> <p>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.</p> http://mathoverflow.net/questions/35487/a-provable-upper-bound-on-the-summation/35573#35573 Answer by Tsuyoshi Ito for a provable upper bound on the summation Tsuyoshi Ito 2010-08-14T11:16:16Z 2010-08-14T11:16:16Z <p>Here is a copy-and-paste of the <a href="http://math.stackexchange.com/questions/2250/a-provable-upper-bound-on-the-summation/2380#2380" rel="nofollow">answer</a> I posted to the same question on math.stackexchange.com so that the questioner can close this question.</p> <p>The sum in question is at most ε<sup>2</sup>. (We do not need the condition that the row sum equals 1 or the condition f(i)≠g(i) to obtain this.)</p> <p><strong>Proof</strong>. 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.$$</p>