A Combinatorial Problem on Abelian Groups
Author(s): Marshall Hall, Jr.
Source: Proceedings of the American Mathematical Society, Vol. 3, No. 4 (Aug., 1952), pp.
584-587
Published by: American Mathematical Society
Stable URL: http://www.jstor.org/stable/2032592
Accessed: 07-05-2016 15:20 UTC
Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at
http://about.jstor.org/terms
JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide range of content in a trusted
digital archive. We use information technology and tools to increase productivity and facilitate new forms of scholarship. For more information about
JSTOR, please contact support@jstor.org.
American Mathematical Society is collaborating with JSTOR to digitize, preserve and extend access to
Proceedings of the American Mathematical Society
This content downloaded from 143.89.105.150 on Sat, 07 May 2016 15:20:59 UTC
All use subject to http://about.jstor.org/terms
A COMBINATORIAL PROBLEM ON ABELIAN GROUPS
MARSHALL HALL, JR.
1. Introduction. Suppose we are given a finite abelian group A of
order n, the group operation being addition. If
/al, a2v *.*.* an
\Cl, C2, * - * Cn
is a permutation of the elements of A, then the differences cl-al
= bi, c* - an , - bn are n elements of A, not in general distinct,_
such that ?.I b;= D i c,- En 1 a,=O, since the sum of the c's
and the sum of the a's are each the sum of all the elements of A. The
problem is to show that conversely given a function ?(i) = bi,
i= 1, - -, n, with values bi in A subject only to the condition that
D-i bi=0, then there exists a permutation
\Cl, ... t Cn/
of the elements of A such that ci-ai=bi, i= 1, * * *, n, if the b's are
appropriately renumbered. This problem' is solved in this paper.
2. Solution of the problem.
THEOREM. Given a function d)(i) =bi, i= 1, * ,n, with bi in A,
an additive abelian group of order n, subject to the condition , b, = 0,
there exists a permutation
/a,, * I * an\
\ l ... I Cn/
of the elements of A such that c,-a =bi, i= 1, * ,n, the b's being
appropriately renumbered.
PROOF. If we take a,, a2, * * ,an as the elements of A in an arbitrary
but fixed order, the problem consists in renumbering the b's so that
al+bi=cl, a2+b2=c2, * * *, an+bn=cn are all distinct.
It is sufficient to prove that given a permutation whose differences
are bi, b2, * * , bn-2, b'_1, bn , we can find another whose differences
b1, b2, * * ,bn-2, bn_1, bn are the same except that two of them,
b'_1 and bn', have been replaced by two others, bn-I and bn, with the
Presented to the Society, October 27, 1951; received by the editors July 24, 1951.
1 For the cyclic group this shows the truth of a conjecture of Dr. George Cramer.
584
This content downloaded from 143.89.105.150 on Sat, 07 May 2016 15:20:59 UTC
All use subject to http://about.jstor.org/terms
A COMBINATORIAL PROBLEM ON ABELIAN GROUPS 585
same sum bn_l+bn=bt_-+b,. For the identical permutation has dif-
ferences 0, 0, , 0 and we may replace these differences two at a
time to give differences b1, W2, 0, , * 0; bit b2, W3, O . . . O; 0 ; ;
bi, b2, , * bn_-1, wn where w2=-bi, W3= -b1-b2, . . . wn=-b
- b2- * * * -bn_l =bn.
Thus we suppose given an incomplete permutation
{alf . . .*, an-2, * *
\ l C1 * * * Cn_2, * *
with differences b1, b2, , * bn2 which we represent by a table:
al a2 ... an-2 an-I an
(2.1) b1 b2* .. bn_2 bn-1 bn
C1 C2 . . . Cn-2 U_1 UO.
In this table ai+bi=ci, i=1, * *, n-2, and we have left over two
a's, two b's, and the two elements uo and u-, which together with
cl, C2, * * *, cn-2 make up all the elements of A. Here we have
n-2 n-2 n-2
(2.2) Eai+ an-I+ an+ b + bn_I+ bn = ci+ u_1 + uo
i- i- s il
since each of 2 ai and D'-2 ci+u-1+uo is the sum of all the ele-
ments of A and by hypothesis D1 bi=O. But since a,+bi=ci,
i=1, * * *, n-2, we shall have from (2.2)
(2.3) an-l + an + bn_. + bn = u-1 + Uo.
In (2.3) if one a plus one b is one of the u's, then the other a plus the
other b is the remaining u and we can complete (2.1) to a full permu-
tation with differences b1, - - *, bn as was to be done. If not, then the
equation x+bn_l=u-1 has as its solution x=ar,, 1< ri<n-2. Now
in (2.1) let us replace b7, and c,, by bn-l and u-1 leading to the follow-
ing table:
a **.* arl **.*an2an, _an
(2.4) b1 ... bn_- ... bn_2 bribn
cl . . *u.U1 . . . Cn-2 Uo Cr1
and as from (2.1) we have
(2.5) an-1 + an + brl + bn = uo + Crlj
In (2.5) if one a plus one b is uo or cr,, the same holds for the other
a, b, and cr1 or uo and we have found a solution to the problem. If
This content downloaded from 143.89.105.150 on Sat, 07 May 2016 15:20:59 UTC
All use subject to http://about.jstor.org/terms
586 MARSHALL HALL, JR. [August
not, the equation x+br,i=Uo has a solution x-=a,2 with 1 <r2?n-2.
Let us then replace b,2 and c,2 by bI4 and uo in (2.4) leading to another
incomplete permutation. If we continue this process for i steps, we
have (if a,., * * *, a,j are all different)
a, ... ar, ar2 ar.3 ... ar, ... an2a2 an an
(2.6) bi ... bn-, bri br2 . . . bri-1 ... bn_2 br, bn
Cl . . . U-1 Uo Cri . . . Cri-2 . . . Cn-2 Cr,_l Cr,.
At the ith stage we solve the equation x+br. = Cr,.j1 If this x is an-1
or an, the relation
(2.7) an-1 + an + b,i + bn = Cr,., + cr,
leads to a solution of the problem. If not, x = a,, with 1 < rj+1 < n -2
and we proceed to the (i+l)th stage by replacing b,i, and cr,+1 by
br, and c,i,1. Hence either (1) we reach a solution of the problem or
(2) the process continues indefinitely. We shall show that the second
alternative cannot arise. In the second alternative since arl, ar2, . . .
are drawn from the finite set a,, * , an-2, there will be indices i and
j_i such that a,., *, a,, , ar, are all distinct, but arj,1 = ari.
Then at the jth stage we have
a, ari* a,. * a,_.... _ an
(2.8) b1... ---.br_.- br_-1... bn_2 b,. bn
Cl . . . Cri-2 . . . Cr_-2 . . . Cn_2 Cr;_l C ri
and the solution of x+brj = cri- I is x =ar,. At the (j+1)th stage the
b's and c's left over are
(2.9) br..,bn
Cr,* Cr;_s
whence
(2. 10) an.1 + an + bri-j + bn = cr, + Cri-2,
But at the (i.-l)th stage we had (from (2.7) or (2.3) if i=1)
(2. 11) an-l + an + br,.. + bn = cri-. + Cr,...
Comparing (2.10) and (2.1 1) we find that
(2.12) Cr; =Cr,-l
But this is a contradiction since j>i- 1 and cr, and cr,., are distinct
elements in (2.8). Thus the second alternative does not arise and we
This content downloaded from 143.89.105.150 on Sat, 07 May 2016 15:20:59 UTC
All use subject to http://about.jstor.org/terms
19521 A COMBINATORIAL PROBLEM ON ABELIAN GROUPS 587
find a solution to the problem in not more than n -2 steps.
3. Application to Latin squares. Consider a Latin square which is
the Cayley table for an abelian group of order n
all, a12, , ain
(3.1) a2l, a22, , a2n
ani1 an2, ' ann-
Here if a,=0, a2, , an are the elements of A, then in the table
above a,i =ai+aj. If
- {~~~~~~~a,, * I anX
uCI, . . . I Cn/
is a permutation of the elements of A, then c7 is below a, in the kth
row if c,-a,=b,=ak. We say that cl, c2, * * *, C,, * * *, cn agrees
with the kth row in position r. Thus the theorem asserts that there
exists a permutation agreeing with the ith row ki times if and only if
(3.2.1) k1+k2+ +kn=n,
and
(3.2.2) k1a, + k2a2 + * + knan = 0,
where (3.2.1) is a count of the k's and (3.2.2) is an equation in A.
The sum of all the elements of an abelian group A is known to be 0
unless A contains a unique element of order 2, in which case the sum
is this unique element. In the special case in which ki = *= .
=kn = 1 we say that c1, * * *, cn is a transversal of the Latin square.
Here (3.2.2) does not hold if A contains a unique element of order 2
and there is no transversal. But if A does not contain a unique ele-
ment of order 2, then (3.2.2) does hold and there is a transversal of
the Latin square. This special case of the theorem above was proved
by Lowell Paige in his doctoral dissertation at the University of
Wisconsin.
OHIO STATE UNIVERSITY
This content downloaded from 143.89.105.150 on Sat, 07 May 2016 15:20:59 UTC
All use subject to http://about.jstor.org/terms
