antimagic matrices of 0,1,-1: For which values of n does there exist an n times n matrix A with the following properties: (i) All entries of A are from {-1,0,1}, (ii) The row sums and column sums are pairwise distinct. SPOILER: (Dan Hoey after Fred Galvin) Theorem: If an nxn matrix whose entries are all 0, 1, and -1 has 2n different column and row sums (which we collectively call line sums), then: 1. n is even, 2. The number in {-n, 1-n, 2-n ..., n} that does not appear as a line sum is either -n or n, and 3. Of the n largest line sums, half are column sums and half are row sums. Proof: We start with Lemma: Suppose an nxn matrix has entries 0, 1, and -1, and choose any n of the line sums. If T is the total of all the entries of the matrix, and S is the total of the chosen line sums, then 2(S-T) <= n^2 with equality only when the chosen line sums consist of n/2 row sums and n/2 column sums. Proof: Suppose the n line sums are the sums of r rows and c columns. Partition the entries of the matrix as B, the entries occuring on both a chosen row and column, E, the entries occuring on either a chosen row or column but not both, and N, the entries occuring on neither a chosen row nor column. Clearly B has rc elements and N has (n-r)(n-c) = rc elements. Then T = Sum(B) + Sum(E) + Sum(N) and S = 2 Sum(B) + Sum(E), so S-T = Sum(B) - Sum(N). This is maximized when all elements of B are plus one and all elements of N are minus one, so S-T <= 2 rc. The product rc is maximized only when r = c = n/2, so that S-T <= 2(n/2)(n/2), proving the lemma. In a -1 - 0 - 1 matrix with 2n different line sums, exactly one element x of {-n, 1-n, 2-n, ..., n} does _not_ occur as a line sum. We may ensure that x <= 0 by negating all entries of the matrix if necessary. Adding all the line sums counts each matrix entry twice, so the sum of the matrix entries is -x/2. The n largest line sums of the matrix are 1,2,...,n, which sums to n(n+1)/2. So by the lemma, 2( n(n+1)/2 - (-x/2) ) <= n^2, implying that x <= -n. But we defined x >= -n, so equality must hold, and those n line sums must be of n/2 rows and n/2 columns, and in particular, n must be even, QED. Construction: antimagic 0,1,-1 squares for n even I think you'll see the pattern from the following, n = 10: + + + + + + + + + + 10 + + + + + + + + + o 9 + + + + + + + + o o 8 + + + + + + + o o o 7 + + + + + + o o o o 6 o o o o o - - - - - -5 o o o o - - - - - - -6 o o o - - - - - - - -7 o o - - - - - - - - -8 o - - - - - - - - - -9 5 4 3 2 1 0 -1 -2 -3 -4 5 Missing sum -n Total row sums or col sums n/2 Open Problem: Try recangular matrices. Conjecture: Only n times n+1 rectangles are possible (in addition to the square onces). References: Rainer Bodendiek, Gustav Burosch; Streifz"uge durch die Kombinatorik, Aufgaben und L"osungen aus dem Schatz der Mathematik-Olympiaden, (Excursions into Combinatorics) Spektrum Akademischer Verlag, Heidelberg, 1995, ISBN 3-86025-393-X Kapitel: Aufgaben zu Invarianten, Aufgabe 5.30 p250-253 - Solution to the antimagic 0,1,-1 matrix problem Fred Galvin; Subject: Re: Combinatorial matrix puzzle Newsgroup: sci.math Date: 1999-09-25 - Solution to the antimagic 0,1,-1 matrix problem