Hi ! Can somebody prove that it`s impossible for odd $ n$ ? I have a solution for even numbers (all even $ n$ have this property ) . I will post my solution.

I have seen the solution from an external source. Shall I post it ?

rahulakaneo wrote: I have seen the solution from an external source. Shall I post it ? Please post it . Thanks in advance .

Here you go. Consider a matrix M[1..N][1..N] that satisfies the given property and let the arrays Row[1..N] and Col[1..N] denote the Row sums and the Col sums. Since the maximum value a row sum or a col sum can take is N and the minimum value is -N and there are only 2N+1 values that all the sums can take, exactly one value from the set {-N,-N+1,...,N-1,N} is missing. Since there are N+1 non-negative values and N+1 non-positive values in the set {-N,-N+1,...,N-1,N}, the set of 2N sums contain at least N non-negative and N non-positive values. Now, note that exchanging any two rows or any two columns does not affect the set of distinct 2N sums. By permuting the rows and columns, we can obtain a matrix for which the row sums R[1],R[2],...,R[k] and C[1],C[2],...,C[N-k] are non-negative. Clearly, (Sum for i=1 to N) |R| + (Sum for j=1 to N) |C[j]| >= (Sum for k=-N to N) |k| - N = N^2 But, the same summation can be rewritten as, (Sum for i=1 to N) |R| + (Sum for j=1 to N) |C[j]| = (Sum for i=1 to k) R - (Sum for i=k+1 to N) R + (Sum for j=1 to N-k) C[j] - (Sum for j=N-k+1 to N) C[j] = (Sum for all i such that i<=k) M[j] - (Sum for all i such that i>k) M[j] + (Sum for all j such that j<=N-k) M[j] - (Sum for all j such that j>N-k) M[j] = 2.( (Sum for i=1 to k) (Sum for j=1 to N-k) ) M[j] - 2.( (Sum for i=k+1 to N) (Sum for j=N-k+1 to N) ) M[j] <=4k(N-k) This yields N^2 <= 4k(N-k) ie (N-2k)^2 <= 0 which proves that N has to be even and k exactly half of it. The latter part of the solution contains more mathematical signs and it isn't going to be easier for me to write it continuing in this way. Could someone please tell as to from where do I learn about Latex etc to be able to post with mathematical signs properly.

See http://www.artofproblemsolving.com/Forum/viewtopic.php?t=123690 and LaTeX. (Note that you don't need to download anything to use LaTeX in the forums -- just enclose your code between dollar signs.)

I have an inductive proof for the existence for even $n$.I will prove a stronger result: For any even $n$ there exist a $n*n$ matrix so that the sum of all its columns and rows produce numbers $-n,-(n-1),\dots , n-1$.The base of induction is trivial just check the below matrix: $\begin{bmatrix}1&0\\-1&-1\\ \end{bmatrix}$ For the inductive step put the $n+2$-th row all $-1$'s.For the first column of $n+1$-th row put $0$ and for other entries of $n+1$-th row put all $1$'s.For the remaining entries of first column put $-1$'s and for the remaining entries of the $n+2$-th column put $1$'s.Now put the $n*n$ matrix obtained by induction in the remaining part.Here is an example of a constructed matrix for $n=4,6$ using induction: $\begin{bmatrix}-1&1&0&1\\-1&-1&-1&1\\0&1&1&1\\-1&-1&-1&-1\\ \end{bmatrix}$ $\begin{bmatrix}-1&-1&1&0&1&1\\-1&-1&-1&-1&1&1\\-1&0&1&1&1&1\\-1&-1&-1&-1&-1&1\\0&1&1&1&1&1\\-1&-1&-1&-1&-1&-1\\ \end{bmatrix}$ I have no proofs for impossiblity for odd numbers I will post it as soon as I find it.

I couldn't find a solution for the second part myself so I just put @rahulakaneo solution in $LATEX$ rahulakaneo wrote: Here you go. Consider a matrix $M(n*n)$ that satisfies the given property and let the arrays $R_1,R_2 \dots R_n$ and $C_1,C_2,\dots C_n$ denote the Row sums and the Col sums. Since the maximum value a row sum or a col sum can take is $n$ and the minimum value is $-n$ and there are only $2n+1$ values that all the sums can take, exactly one value from the set $\{ -n,-n+1,\dots ,n-1,n \}$ is missing. Since there are $n+1$ non-negative values and $n+1$ non-positive values in the set $\{ -n,-n+1,\dots ,n-1,n \}$, the set of $2n$ sums contain at least $n$ non-negative and $n$ non-positive values. Now, note that exchanging any two rows or any two columns does not affect the set of distinct $2n$ sums. By permuting the rows and columns, we can obtain a matrix for which the row sums $R_1,R_2,\dots ,R_k$ and $C_1,C_2,...,C_{n-k}$ are non-negative. Clearly, $\sum\limits_{i=1}^n |R_i| + \sum\limits_{j=1}^n |C_j| \ge \sum\limits_{k=-n}^n |k| - n = n^2$ But, the same summation can be rewritten as, $\sum\limits_{i=1}^n |R_i| + \sum\limits_{j=1}^n |C_j|= \sum\limits_{i=1}^k R_i - \sum\limits_{i=k+1}^n R_i + \sum\limits_{j=1}^{n-k} C_j - \sum\limits_{j=n-k+1}^n C[j]= \sum\limits_{i \le k} M_{ij} - \sum\limits_{i>k} M_{ij} + \sum\limits_{j \le n-k} M_{ij} - \sum\limits_{j>n-k} M_{ij}= 2*\sum\limits_{i=1}^k(\sum\limits_{j=1}^{n-k} M_{ij}) - 2*\sum\limits_{i=k+1}^n(\sum\limits_{j=n-k+1}^n M_{ij}) \le 4k(n-k)$ This yields $n^2 \le 4k(n-k)$ ie $(n-2k)^2 \le 0$ which proves that $n$ has to be even and $k$ exactly half of it.

Well I have another construction for even n. Maybe it's actually the same as Taha1381's(just swapping some rows and columns or mutiply -1 to everything) but i think it's easier to understand. for $n=2$ we take $\begin{bmatrix}1&-1\\1&0\end{bmatrix}$ for $n=4$ we take $\begin{bmatrix}1&0&-1&-1\\1&1&-1&-1\\1&1&0&-1\\1&1&0&0\end{bmatrix}$ for $n=6$ we take $\begin{bmatrix}1&0&0&-1&-1&-1\\1&1&0&-1&-1&-1\\1&1&1&-1&-1&-1\\1&1&1&0&-1&-1\\1&1&1&0&0&-1\\1&1&1&0&0&0\end{bmatrix}$ and so on. generally,for $n=2k$ for cell $(i,j)$ we put $-1+[j\le i]+[j\le k]$ here $[P]$ is $1$ if $P$ is true and $0$ otherwise. then we can easily get sum of the columns are $2k,2k-1,\cdots,k+1,-k,-k-1,\cdots,1-2k$ and sum of the rows are $1-k,2-k,\cdots,0,1,2,\cdots,k$. and they are pairwise distinct so we are done.

The answer is $n$ even only. Here is a construction for $n=6$ which readily generalizes: $$\begin{bmatrix}\textcolor{red}{1}&-1&-1&-1&-1&-1\\1&\textcolor{red}{0}&-1&-1&-1&-1\\1&1&\textcolor{red}{1}&-1&-1&-1\\1&1&1&\textcolor{red}{0}&-1&-1\\1&1&1&1&\textcolor{red}{1}&-1\\1&1&1&1&1&\textcolor{red}{0}\end{bmatrix}$$It's not hard to verify that this works. Now we prove that $n$ even fail. By multiplying every element of the matrix by $-1$ if necessary we may assume that the missing row entry is $m\geq 0$; note that $n \in [-n,n]$. We may readily swap whole rows and columns, so WLOG assume that the $k$ leftmost columns have nonnegative sum, and the $n-k$ rightmost columns have negative sum. W may further assume that the $n-k$ top columns have nonnegative sum and the $k$ bottom columns have negative sum. Truthfully, there's not an actual reason we do this, but it makes the rest of this solution easier to think about. Split the grid into four regions: A top-left $n-k \times k$ region with $A$ with sum $a$ A top-right $n-k \times n-k$ region $B$ with sum $b$ A bottom-right $k \times k$ region $C$ with sum $c$ A bottom-left $k \times n-k$ region $D$ with sum $d$ Then double-counting over regions and rows, $$2a+b+d=\frac{n(n+1)}{2}-m\text{ and } 2c+b+d=-\frac{n(n+1)}{2}.$$Hence we require $$2a-2c=n^2+n-m.$$On the other hand, the LHS is bounded above by $4k(n-k)$ because the total area covered by regions $A$ and $C$ is $2k(n-k)$. Since $n$ is odd, this quantity is at most $$4\cdot \frac{n-1}{2}\cdot \frac{n+1}{2}=n^2-1,$$but $n^2+n-m\geq n^2$ which is a contradiction. Thus all $n$ odd fail. $\blacksquare$