0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Dear Manan, you already posted your question on math.stackexchange. I'm not sure there is an official policy about this yet, but doubling the effort of people who are doing this for free is not nice. You should have at least linked the other question: math.stackexchange.com/questions/2250/… $\endgroup$ Aug 13, 2010 at 12:29
  • $\begingroup$ Moreover the question you posted looks a lot like homework, which is not the point of the present site. Hence I'm voting to close. $\endgroup$ Aug 13, 2010 at 12:30
  • $\begingroup$ I am sorry for the repetition. Actually I am new at both these websites and I wasn't sure which was the correct website for it. In future I'll definitely keep this in mind. Thanks for pointing it out and sorry again. $\endgroup$
    – Manan
    Aug 13, 2010 at 12:32
  • $\begingroup$ Ok, no problem. Still, if you want it not to be closed, you should give some more information why you interested in this. As stated, the question looks like copied verbatim from a problem book, and homework is explicitly discouraged on this site. $\endgroup$ Aug 13, 2010 at 12:35
  • 2
    $\begingroup$ Actually this came up during my research (albeit at a young stage) on Secure Communication that I am pursuing here at IIIT as a B.Tech + M.S. student. I haven't copied this from anywhere. I just tried to frame my problem as formally as I could (as stated in FAQ). The conditions that are given to hold come from the definition of secrecy from Mathew Franklin's Paper (springerlink.com/content/p0624333842u8120). To prove the solution to my problem I have to show that the expression (in the problem statement) is bounded by $\epsilon^2$. $\endgroup$
    – Manan
    Aug 13, 2010 at 12:46

1 Answer 1

1
$\begingroup$

Here is a copy-and-paste of the answer I posted to the same question on math.stackexchange.com so that the questioner can close this question.

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

$\endgroup$
2
  • 1
    $\begingroup$ But next time please do not post your question to more than one site at the same time. $\endgroup$ Aug 14, 2010 at 11:17
  • $\begingroup$ @Tsuyoshi: I'll definitely keep that in mind in future. Thanks again. $\endgroup$
    – Manan
    Aug 14, 2010 at 16:44

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