Solution:

Since $a_{j j}$ has to exceed all the numbers in the top left $j \times j$ submatrix (excluding itself), and since there are $j^{2}-1$ entries, we must have $a_{j j} \geq j^{2}$. Similarly, $a_{j j}$ must not exceed each of the numbers in the bottom right $(n-j+1) \times (n-j+1)$ submatrix (other than itself) and there are $(n-j+1)^{2}-1$ such entries giving $a_{j j} \leq n^{2}-(n-j+1)^{2}+1$. Thus we see that
$$a_{j j} \in\left\{j^{2}, j^{2}+1, j^{2}+2, \ldots, n^{2}-(n-j+1)^{2}+1\right\}$$
The number of elements in this set is $n^{2}-(n-j+1)^{2}-j^{2}+2$. This implies that
$$b_{j} \leq n^{2}-(n-j+1)^{2}-j^{2}+2=(2 n+2) j-2 j^{2}-(2 n-1)$$
It follows that
$$\begin{aligned} \sum_{j=1}^{n} b_{j} & \leq (2 n+2) \sum_{j=1}^{n} j - 2 \sum_{j=1}^{n} j^{2} - n(2 n-1) \\ & = (2 n+2)\left(\frac{n(n+1)}{2}\right) - 2\left(\frac{n(n+1)(2 n+1)}{6}\right) - n(2 n-1) \\ & = \frac{n}{3}\left(n^{2}-3 n+5\right) \end{aligned}$$
which is the required bound.