I'm having trouble proving the inequality holds $$ \sum_{i<j} |a_i a_j| b_{ij} \leq \sum_{i=1}^{n} a_i^2 \max_{1 \leq i \leq n} \sum_{j=1}^{n}b_{ij} \quad b_{ij}\geq 0 $$ Thanks

  • $\begingroup$ It still doesn't hold, now it claims (with $b_{ij}=-1$, $a_i=1$) that $-{n\choose 2}\le -n^2$. I'd suspect that non-negative values are postulated, but the absolute value bars make that less likely. $\endgroup$ – Hagen von Eitzen Jul 7 '13 at 21:53
  • $\begingroup$ @HagenvonEitzen having looked at it again, I don't think negative $b_{ij}$ is allowed $\endgroup$ – Mandy Jul 7 '13 at 22:02

Claim. Assume everything is positive. Suppose $b_{ij} = b_{ij}$ are the entries of the symmetric matrix $B$. We will show that $a^T B a \leq 2 M[B] \; ||a||_2^2$ where $M[B] = \max_{1\leq i \leq n} \sum_{j=1}^n b_{ij}$.

[The original inequality will follow from this since any quadratic form with no squares can be put in the form of $a^TBa$ as mentioned. I'll explain at the end.]

Step 1. We have $$a^TBa \leq 2\sum_{j \leq i} a_i a_j b_{ij} = 2 \sum_{i=1}^n a_i \sum_{j=1}^i a_j b_{ij} \leq 2 \sum_i \left[ a_i \; (\max_{j\leq i} a_j) \sum_{j=1}^i b_{ij} \right].$$

The last inequality is just the typical $||fg||_1 \leq ||f||_\infty ||g||_1$ Holder estimate applied to the inner sum. Continuing, we get

$$ a^TBa \leq 2 \sum_i \left[ a_i \; (\max_{j\leq i} a_j) \sum_{j=1}^n b_{ij} \right]\leq 2 \left( \max_{1\leq i \leq n} \sum_{j=1}^n b_{ij} \right) \left( \sum_{i=1}^n a_i (\max_{i\leq j} a_j) \right) \\= 2 M(B) \left( \sum_{i=1}^n a_i \max_{i\leq j} a_j \right).$$

If the $a_i$'s are increasing in $i$, then our claim is shown.

Step 2. Otherwise, suppose not. Let $P$ be the permutation matrix such that $Pa$ lists the elements of $a$ in increasing order. Then $$a^T B a = (Pa)^T (P^{-1})^T B P^{-1} (Pa) \leq 2 M[(P^{-1})^T B P^{-1}] \;||Pa||_2^2,$$ using the inequality in the first step. Note this is valid since $(P^{-1})^T B P^{-1}$ is still symmetric.

It is obvious $||Pa||_2^2 = ||a||_2^2$. We now want to show $M[(P^{-1})^T B P^{-1}] = M[B]$. If $T_{ij}$ interchanges two rows, then $M[T_{ij}^{T} B T_{ij}] = M[B]$. This is because of the following. We have $T_{ij} = T_{ij}^T$, $T_{ij}B$ swaps the $i$th and $j$th rows of $B$ and $BT_{ij}$ swaps the $i$th and $j$th columns of $B$. One observes that with $M[B] = \max_{1\leq i \leq n} \sum_{j=1}^n b_{ij}$ row swapping does not change the max, and column swapping does not change the sum. So $M[T_{ij}^TBT_{ij}] = M[B]$. Because $P$ can be written as the product of row transpositions, $M[(P^{-1})^T B P^{-1}] = M[B]$.

Original Problem. We choose $b_{ij}=b_{ji}=\frac{1}{2} c_{ij}$ for $i<j$ and $b_{ii}=\frac{1}{2} (0)$. Then $$\sum_{i<j} a_i a_j c_{ij} = \sum_{1\leq i, j \leq n} a_i a_j b_{ij} = a^T B a \leq 2 M[B] ||a||^2_2.$$

One now easily sees that $$M[B] = \max_{1\leq i \leq n} \sum_{j=1}^n b_{ij} \leq \frac{1}{2} \max_{1\leq i \leq n} \sum_{j=1}^n c_{ij},$$ which makes everything clear.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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