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