# Show $\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}$

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

• 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. – Hagen von Eitzen Jul 7 '13 at 21:53
• @HagenvonEitzen having looked at it again, I don't think negative $b_{ij}$ is allowed – 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.