Here is my solution. I hope it's correct: 1. All odd k are possible Proof: Fill in the square only 1's. Then Every number is 2n-3 times less than the sum of all the other numbers in the same cross. 2. Only odd k are possible Proof: Let a(i,j) be the the number in the i-th row and the j-th column. Then we have $ (k+3)a(i,j)=\sum_{m=1}^{n}a(i,m)+\sum_{m=1}^{n}a(m,j)$ Therefore $ \sum_{i=1}^{n}(k+3)a(i,j)=\sum_{i=1}^{n}\sum_{m=1}^{n}a(i,m)+n\sum_{m=1}^{n}a(m,j)$ And so $ \sum_{i=1}^{n}\sum_{j=1}^{n}(k+3)a(i,j)=n\sum_{i=1}^{n}\sum_{m=1}^{n}a(i,m)+n\sum_{j=1}^{n}\sum_{m=1}^{n}a(m,j)$ $ -> k =2n-3$

Max(i) wrote: Here is my solution. I hope it's correct: 1. All odd k are possible Proof: Fill in the square only 1's. Then Every number is 2n-3 times less than the sum of all the other numbers in the same cross. Sorry to disappoint you, but it is not corect. If you fill in the squares only with $1$'s you can't get any odd k, you will get exactly $2n-2$. In fact, the answer is $k=2n-2$ and $k=n-2$. Proof:Let $a_{ij}$ be the number in the cell placed in the i-th row and j-th column, $R_{i}$ the sum of the elements in the i-th row, $C_{j}$ the sum of the elements in the j-th column, and $S$ the total sum. By hypothesis, we have: $(k+2)a_{ij}=R_{i}+C_{j}$. Summing up after $i$, we get: $(k+2)C_{j} = k\sum_{i=1}^{n}a_{ij} = \sum_{i=1}^{n}(R_{i}+C{j}) = \sum_{i=1}^{n}R_{i} + \sum_{i=1}^{n}C_{j} = S + nC_{j}$ and $(k-n+2)C_{j} = S$ We split it into 2 cases: $1. k-n+2=0$ Then $k=n-2$ and $S=0$. For an example, take all the rows to have identical components on each of them, and their sum to be 0. Then $C_{i} = 0$ and $a_{ij} = \frac{R_{i}}{n}$. $2. k-n+2$ nonzero. We also get $S$ nonzero. Then we have $C_{j} = \frac{S}{k-n+2}$ and, summing up after j, we get $\sum_{j=1}^{n} C_{j} = n\frac{S}{k-n+2}$. So $S = \frac{nS}{k-n+2}$ and, from here: $n=k-n+2 , k=2n-2$ We can use the example stated at the beginning, the table filled up only with $1$'s.

Answer is $2n-2,n-2,-2$. Construction are: $2n-2$: All numbers of the table equal. $n-2$: It is not hard to get that it suffices to ensure the sum in any perfect matching is $0$. Now take all numbers of the first row to be $n-1$ and all other numbers of the table to be $-1$. $-2$: It is easy to get that it suffices to ensure the sum in each line is $0$. Just fill the inner $(n-1) \times (n-1)$ table randomly, and other numbers get determined uniquely (it is easy to ensure all numbers are non-zero by choosing the original $(n-1)^2$ numbers to be positive). Now FTSOC assume $k \ne 2n-2,n-2,-2$. Let $S$ be the sum of all numbers in the table. Using the hypothesis for all numbers of the table and using $k \ne 2n-2$ gives $S = 0$. Now consider any $a_1,\ldots,a_n$ forming a perfect matching $b_1,\ldots,b_n$ in a straight line. Using $k \ne -2,n-2$ respectively yields $\sum a_i = \sum b_i = 0$. But $\sum b_i = 0$ is enough to force $k=-2$, contradiction. $\blacksquare$