Solution:

Suppose that $a_{i j}$ and $a_{k l}$ are among the chosen numbers and suppose that $i < k$ and $j < l$. It is straightforward to show that $a_{i j} + a_{k l} \geqslant a_{i l} + a_{k j}$. Hence, whenever $a_{i j}$ and $a_{k l}$ with $i < k$ and $j < l$ are among chosen numbers, we can lower the sum by replacing these two numbers with $a_{i l}$ and $a_{k j}$. Hence the smallest possible sum is when we choose $a_{1 n}, a_{2, n-1}, \ldots, a_{n 1}$—and in that case the sum is $1$.