<table>
<tr><td>1</td><td>8</td><td>12</td><td><b>21</b></td></tr>
<tr><td>7</td><td>9</td><td>20</td><td>4</td></tr>
<tr><td>10</td><td>19</td><td>3</td><td>6</td></tr>
<tr><td>18</td><td>2</td><td>5</td><td>11</td></tr>
</table>

The lower bound is a consequence of the following slightly more general fact:
If, for some integer $n \ge 3$, on each row of an $n \times n$ array of pairwise distinct positive integers, one of the numbers is equal to the sum of the other $n-1$, then the largest number in the array is at least $\frac{1}{2}(n-1)(n^2 - n + 2)$; columns subjected to no condition whatsoever.

Let $a$ be the largest number in the array and let $a_i$ be the largest number on the $i$-th row, $i = 1, 2, \dots, n$. Since the $a_i$ are pairwise distinct positive integers not exceeding $a$,
$$\sum_{i=1}^{n} a_i \le \sum_{j=0}^{n-1} (a-j) = na - \frac{1}{2}n(n-1). \quad (*)$$
Let now $b_1, b_2, \dots, b_{n^2-n}$ be the numbers in the array different from each $a_i$. Then
$$\sum_{i=1}^{n} a_i = \sum_{j=1}^{n^2-n} b_j \ge \sum_{k=1}^{n^2-n} k = \frac{1}{2}n(n-1)(n^2-n+1), \quad (**)$$
where the first equality holds by hypothesis, and the inequality follows from the fact that the $b_j$ are pairwise distinct positive integers.
Finally, $(*)$ and $(**)$ imply $a \ge \frac{1}{2}(n-1)(n^2-n+2)$, as stated. If $n=4$, then $a \ge 21$, as desired.

In particular, if $n = 3$, then $a \ge \max(9, 8) = 9$. The case $a = 9$ can be ruled out by hand and it turns out that $a = 10$ fits the bill on columns as well:
$$\begin{array}{ccc} 4 & 5 & 9 \\ 6 & 8 & 2 \\ \mathbf{10} & 3 & 7 \end{array}$$
It should now be clear that $a = \frac{1}{2}(n-1)(n^2-n+2)$ forces $n \ge 4$. If $n = 4$, then $a = 21$ also fits the bill on columns, as the array in the solution shows.