NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/sci/math/18788

Internet Message Format | 1993-01-27 | 3.4 KB

Path: sparky!uunet!portal!lll-winken!uwm.edu!spool.mu.edu!hri.com!noc.near.net!nic.umass.edu!umassd.edu!ipgate.umassd.edu!martin
From: [e-mail] (Gary Martin)
Newsgroups: sci.math
Subject: Re: Matrices (problem)
Message-ID: <[e-mail]>
Date: 26 Jan 93 15:22:04 GMT
References: <[e-mail]>
Sender: [e-mail] (USENET News System)
Organization: University of Massachusetts Dartmouth
Lines: 65
In-Reply-To: [e-mail]'s message of 25 Jan 93 03:14:32 GMT

In article <[e-mail]> [e-mail] (Bittu) writes:

   A simple question about the rank of a special matrix (this is not a
   homework problem; I already know a solution, want something better).
   In fact, this was probably on the Math Olympiad a few years ago.

   Let A be a matrix with the following properties:

   1. A is 2n+1 x 2n+1 for a positive integer n.

   2. A has 0's on the diagonal.

   3. The remaining entries are either 1's or -1's.

   4. Every row has exactly n 1's and n -1's.

   We want to show that the rank of this matrix is 2n (over complex
   numbers, say). Clearly the rank is <= 2n (all columns sum to the zero
   vector).

   Let I_m be the m x m identity matrix and J_m be the all 1's matrix.
   The solution I know involves showing that the matrix J_m - I_m has
   rank m if m is even and m-1 if m is odd (over GF[2]; done by showing
   that its determinant is (-1)^(m-1) . (m-1)). We are only interested
   in the case where m is odd. We now use the well-known result that if
   the rank is m-1 over GF[2], it is m-1 over rationals, reals, complexes
   etc. Note that J_{2n+1} - I_{2n+1} is the same as A over GF[2].

   I am sure there is a much easier and elegant proof of this (for the
   field of complexes). Any takers?

This is a generalization of a Putnam problem from the 70s:
Let  S  be a multiset containing an odd number of integers with the
property that no matter which element is deleted, the rest can
be partitioned into two pieces having equal sum.  Then all the elements
of  S  are equal.

I had a paper on this in the Monthly back around '86 or '87 (can't
find that issue right now).

Forget for a moment that the elements of S are integers.  Note that
hypothesis and conclusion are invariant under translation and dilation.
Translate so one element is zero.  Note that the elements of  S (if integers)
are congruent mod 2.  Divide by 2.  Repeat.  Since the elements were
integers infinitely divisible by 2, they are 0, so the original ones were
equal.

The extension to Q is easy: just clear denominators.  R  and  C  follow
from the simple observation that if a S is a set of vectors satisfying
the hypothesis, then the projections on any 1-dim subspace do too.

If the elements of  S  come from an abelian group  G, then the problem
generalizes to G iff G has no odd torsion.

I also generalized in a different direction:  if  S  has  km+1 elements
such that whichever element is omitted the rest can be partitioned into
k classes of size m with equal sums, then the elements of  S  are equal.
My memory of the exact result is now foggy, but it was something like:
the statement is true iff the elements of S come from an abelian group
whose only torsion is p-torsion where p is a prime dividing m.  This
doesn't sound quite right, but that's the flavor.

--
Gary A. Martin, Assistant Professor of Mathematics, UMass Dartmouth
[e-mail]