Theorem. Let u and v be partitions of the positive integer a. Then there exists
a (0,1)-matrix A with row sum vector u and column sum v if and only if u*
majorizes v.
Side comments: u* is the dual of the partition u which is obtained by adding the
columns when u is written in standard rectangular form (I am avoiding technical
terms). For example, if a=7, and u=3+2+2, then u* is 3+3+1 since the standard
rectangular form of u is
***
**
**
A partition w majorizes another partition z if the first (largest) term of z is
at most the first term of w, and the sum of the first two terms of z is at most
the sum of the first two terms of w, and the sum of the first three terms of z
is at most the sum of the first three terms of w, etecetra (we are assuming the
partitions are in descending order). For example 6+6+3+2 majorizes 5+4+3+3+2.
I do not know much about Gale, but I assume he was a contemporary of Ryser (who
passed away in 1985) shortly after having retired from Caltech. I also think the
0,1,-1 problem is harder.
Robert Mena
Antreas P. Hatzipolakis wrote:
> Richard Guy <rkg@cpsc.ucalgary.ca> wrote (in part; in math-fun list):
>
> > It arises [= the problem] from generalizing problem 124 of a book
> > which Loren Larson has translated from the Swedish of Paul Vaderlind,
> > and which we are embellishing in the hope of its appearing in the
> > MAA's Spectrum Series.
> >
> > Find an n x n matrix whose entries are all zero, plus or minus one,
> > and whose row sums and column sums are all distinct.
> >
> > This isn't too hard to do if n is even, but if n is odd, I believe
> > it to be impossible. Proof or counter-example ????
>
> Later he wrote:
>
> > Doron Zeilberger says it's reminiscent of Gales's [Gale's ?] theorem on
> > row sums and column sums. Anyone know what that is, whether it's relevant,
> > and where is there a proof?
>
> Who was Gale or Gales? And which is his theorem on matrix row/column sums?
>
> Antreas