Deck the Halls
by cjquines0, Dec 26, 2016, 10:58 AM
Canada 2006/3 wrote:
In a rectangular array of nonnegative reals with
rows and
columns, each row and each column contains at least one positive element. Moreover, if a row and a column intersect in a positive element, then the sums of their elements are the same. Prove that
.



Solution
Consider the bipartite graph
with bipartite sets
and
, where the elements of
are rows, the elements of
are columns, and an edge is drawn between
and
if the intersection of
and
is positive.
Assume there exists some subset
such that
. Let the sums of the rows in
be
and the sums of the columns in
be
. Consider the entries in the intersection of the rows in
and the columns in
, and let the sum of these entries be
.
Note that, if we consider the rows,
as all the other elements in the rows of
that aren’t in
have to be zero. (If there was an entry that was positive, then the column would be in
.) Now if we consider the columns, we see that
because the other entries in the columns are nonnegative anyway. Combining these yields
But note that each of the
s is equal to one of the
s. Since these numbers are all nonnegative, this implies that
, contradicting
.
Thus
for all subsets
, and a matching exists from
to
by Hall’s Marriage Theorem, so
. By symmetry,
, so
, which was what we wanted.









Assume there exists some subset









Note that, if we consider the rows,










Thus







Tidbit
I don