For what values of n, does there exist an n x n array of entries 0, ±1 such that all rows and columns have different sums?

**Answer**
n even.

**Solution**

For n = 2m we may take:

1 1 1 1 1 1 -1 1 1 1 1 1 -1 -1 1 1 1 1 -1 -1 -1 0 1 1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 0Thus rows 1, 2, ... , m have sums 2m, 2m-2, 2m-4, ... , 2, and the rows m+1, m+2, ... , 2m have sums -1, -3, ... , -(2m-1). Columns 1, 2, ... , m have sums -(2m-2), -(2m-4), ... , 0, and columns m+1, ... , 2m have sums 1, 3, 5, ... , 2m-1. So we get each of the sums -(2m-1), -(2m-2), ... , -1, 0, 1, 2, ... , 2m just once.

Now suppose that we have a solution a_{ij} for n. Let the row sums be r_{i} and the column sums be c_{j}. The r_{i} and c_{j} are all different and all lie in the range -n to n. There are 2n+1 values in that range. Let the value in the range -n to n not taken by any row or column sum be N.

Suppose that N = 0. Suppose there are k positive row sums. Then there are n-k negative row sums, n-k positive column sums and k negative column sums.

Suppose N > 0. Then n of the sums are negative and n are non-negative. So if there are k non-negative row sums, then there are n-k negative row sums, n-k non-negative column sums and k negative column sums.

Similarly, if N < 0, then n of the sums are positive and n are non-positive. So if there are k positive row sums, then there are n-k non-positive row sums, n-k positive column sums and k non-positive column sums.

Thus whatever the value of N, we may assume that there are k row sums ≥ 0, n-k row sums ≤ 0, n-k column sums ≥ 0, and k column sums ≤ 0. Let L be the set of row indices for which the row sum is ≥ 0, and R the set for which it is ≤ 0. Similarly, let L' be the set of column indices for which the column sum is ≥ 0, and R' the set for which it is ≤ 0.

Then we have ∑ |r_{i}| + ∑ |c_{j}| = ∑_{L} r_{i} - ∑_{R} r_{i} + ∑_{L'} c_{j} - ∑_{R'} c_{j} = ∑_{LL'} + ∑_{LR'} - ∑_{RL'} - ∑_{RR'} + ∑_{LL'} + ∑_{RL'} - ∑_{LR'} - ∑_{RR'}, where ∑_{LL'} denotes the sum of a_{ij} for i in L and j in L' (and similarly for the other terms) = 2 ∑_{LL'} - 2 ∑_{RR'}. But ∑_{LL'} and ∑_{RR'} each have k(n-k) terms, each of which is at most 1, so 2 ∑_{LL'} - 2 ∑_{RR'} ≤ 4k(n-k). Hence ∑ |r_{i}| + ∑ |c_{j}| ≤ 4k(n-k). But ∑ |r_{i}| + ∑ |c_{j}| = 2(1 + 2 + ... + n) - |N| = n(n+1) - |N| ≥ n^{2}, so n^{2} <= 4k(n-k). But n^{2} - 4k(n-k) = (n - 2k)^{2}, so if n is odd then n^{2} > 4k(n - k). Contradiction.

© John Scholes

jscholes@kalva.demon.co.uk

16 Dec 2002