As many ones as possible, square zero
is a matrix whose entries are all 0 or 1, and (computed with ordinary arithmetic).
What is the largest possible number of ones in ?
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
The entries are nonnegative, so nothing can cancel: is zero only if every term is zero.
Call a “source” if row contains a one, and a “target” if column contains a one. Can an index be both?
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. With nonnegative entries, means no index can both receive and send a one. So the ones live in a block whose rows and columns use disjoint sets of indices, and such a block has at most cells.
Step 1: no cancellation. is a sum of nonnegative terms, so it is zero only if for every . Hence there is no with a one in column (some ) and a one in row (some ).
Step 2: the bound. Let be the set of rows that contain a one and the set of columns that contain a one. By Step 1, and are disjoint subsets of . Every one lies in the block , so the number of ones is at most
Step 3: a matrix with 9 ones. Put ones in rows 1 to 3 and columns 4 to 6, and zeros elsewhere: with the block of ones. Then because every one points from to , and nothing leaves .
So the answer is 9. For an matrix it is .
Remark. The nonnegativity is essential. Over the real numbers, without the 0-1 condition, allows every entry to be nonzero, for example .