For $i = 1, \dots, 4$, let $a_i$ be the maximum number in column $i$, and let $b_1, b_2, \dots, b_{12}$ be the remaining 12 numbers written on the board (different from $a_1, a_2, a_3, a_4$). Then, for every $i$, $a_i$ is the sum of the other three numbers in column $i$; therefore,
$$a_1 + a_2 + a_3 + a_4 = b_1 + b_2 + \dots + b_{12}. \qquad (2)$$
Since $b_1, b_2, \dots, b_{12}$ are different positive integers, we have that
$$b_1 + b_2 + \dots + b_{12} \ge 1 + 2 + \dots + 12 = 78. \qquad (3)$$
On the other hand, since $a_1, a_2, a_3, a_4$ are also different positive integers, and $M$ is the largest number on the board, then
$$a_1 + a_2 + a_3 + a_4 \le M + (M-1) + (M-2) + (M-3) \le 4M - 6. \qquad (4)$$
From (2), (3) and (4), it follows that
$$4M - 6 \ge a_1 + a_2 + a_3 + a_4 = b_1 + b_2 + \dots + b_{12} \ge 78,$$
which implies that $M \ge 21$.
The following is an example with $M = 21$: