Show $\sum_{iI'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
 A: 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.
